Exponentiation by squaring facts for kids

Exponentiating by squaring is a clever algorithm (a set of steps) that helps you quickly figure out really big powers of a number. Imagine you need to calculate 2 multiplied by itself 100 times! This method makes it much faster than doing it the usual way. It's also known as the square-and-multiply algorithm or binary exponentiation. It uses the binary (base-2) way of writing the exponent (the small number that tells you how many times to multiply). This technique is super useful in many areas, like in modular arithmetic, which is a type of math used in computer science and cryptography.

People believe this algorithm was first written down in an ancient Sanskrit book called Chandah-sûtra, around 200 BC.

How the Squaring Algorithm Works

Calculating a number raised to a power, like xⁿ (which means x multiplied by itself n times), can take a long time if n is a very large number. For example, to find 2¹⁰, you could do 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2. That's 9 multiplications.

The squaring algorithm is much quicker! Instead of multiplying x by itself n times, it uses a trick. It works by repeatedly squaring the number and then multiplying only when needed.

Here's the basic idea:

• If you want to find xⁿ, and n is an even number, you can think of it as (x²)^n/2. For example, 2¹⁰ is the same as (2²)⁵, which is 4⁵. This reduces the problem.
• If n is an odd number, you can write it as x × x^n-1. Since n-1 is now an even number, you can use the trick from above. For example, 2⁵ is 2 × 2⁴. Then you can calculate 2⁴ as (2²)², which is 4².

This method drastically cuts down the number of multiplications you need to do. Instead of n multiplications, you only need about log₂(n) multiplications. This means for a huge power like 2¹⁰⁰, you'd only need around 7 multiplications instead of 99! This makes calculations much faster for computers.

See also

• Binary number
• Algorithm
• 
• In Spanish: Exponenciación binaria para niños