Question

Rewrite the LeftRightBinaryExponentiation algorithm on bottom to work for ? = 0 as well as any positive integer.

No credit will be given for answers that simply start with an if statement for n = 0.

ALGORITHM LefiRightBinary Exponentiation(a, b(n)) Computes a" by the left-to-right binary exponentiation algorithm I/Input: A number a and a list b(n) of binary digits bj, , bo in the binary expansion of a positive integer n l/Output: The value of a" producta for i ← 1-1 downto 0 do product - product product if b 1 productproduct a return product

I already tried the work that start with if statement. is there anyway can work without it?

Thanks

Answer 1

let I be the length of list b(n) which represents the number n.

First we will have to check if all the digits in b(n) is 0 for it to work for n=0

LeftRightBinaryExponentiation(a, b(n))

product <---- a;

flag<--0

for i<-0 to I do

     if bi=1 flag=1 //flag will become 1 if any 1 is encountered thereby concluding n!=0

if flag<--0 //if flag is still 0 it means there is not a single 1 in the list thereby concluding that n=0

   product<--1 //because if n=0, a^n=a^0=1

else

      for i <--I -1 downto 0 do

            product <-- product * product;

            if bi ==1 product <-- product *a

return product