CODEWITHSUNDEEP
algorithmmultiplication
Baradwaj Aryasomayajula
Baradwaj Aryasomayajula

Reputation: 1204

Could some one explain how the algorithm binary exponentiation from right to left works

I am looking into the Binary exponentiation and how they work from left to right and right to left. I am able to figure out the "Left to Right" method. But not able to figure out the "Right to Left" method.

Here is the link I have followed. Link

Upvotes: 1

Views: 675

Answers (2)

user1196549
user1196549

Reputation:

Left to right: square previous and possibly multiply by x

x^1 = x
x^11 = x²x
x^110 = (x²x)²
x^1100 = ((x²x)²)²
x^11001 = ((x²x)²)²x

Right to left: possibly multiply previous by a power of x

x^1 = x, p = x
x^01 = x, p = x²
x^001 = x, p = (x²)²
x^1001 = (x²)²x, p = ((x²)²)²
x^11001 = ((x²)²)²(x²)²x

Upvotes: 1

Scott Hunter
Scott Hunter

Reputation: 49896

The idea is that in each iteration of the loop, y is the place value of the next digit; if that digit is 1, then what is left of n will be odd, so it gets included in the result r. Setting n = floor(n/2) in each iteration effectively removes the least-significant digit from n.

Upvotes: 1

Related Questions