Square and Multiply Algorithm

Squaring by large exponents can take a long time and use a lot of computer resources. But the Square and Multiply Algorithm dramatically reduces that time. It does this by looking at the binary value of the exponent and creating an equation out of it. The first 1, of the binary value, starts the equation off with a x. Every 1 we see after the first 1, squares what we have, then multiplies by x. Every 0 we see after the first 1, just squares what we have.

(Also Known As: "Exponentiating by Squaring", "Binary Exponentiation", and "Double-and-Add".)