Number Theory

Question

What is the minimum number of multiplications required to compute a^27 ? In general, what is the minimum number of multiplications to compute a^n if n is not a power of 2. 

Answer 1

a²⁷ = a¹⁶ * a¹¹

      = a¹⁶ * a⁸ * a³

      = a¹⁶ * a⁸ * a² * a

Now for a¹⁶ we require log 16 = 4 multiplication

Now this multiplications also include a⁸ and a² so dont need to count

So min number of multiplication = 4 + 1 + 1 + 1 = 7

Comments

Thank you :)