(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Let a be an integer and n be a non-negative integer.

Without changing the values of a and n, produce an algorithm, of O(log n) complexity, which computes a^n.

2. Relevant equations

For integers a, n and i, where n >= 0 and is even, where i >= 1 and where a has no further constraints:

a^n = (a^[2i])^(n/[2i])

For integers a, n and i, where n >= 0 and is odd, where i >= 1 and where a has no further constraints:

a^n = a^(n-i) * a^i

3. The attempt at a solution

The following is the solution I attempted by myself, as well as the one provided by a book I'm using.:

Code (Text):

public static void myWay(int a, int n) {

int b = a;

int k = n;

while( k != 0 ) {

if(k % 2 == 0) {

b = b * b;

k = k / 2;

}

else {

b = b * a;

k = k - 1;

}

}

System.out.println(b);

}

public static void wayOfBook(int a, int n) {

int k = n, b = 1, c = a;

while(k != 0) {

if(k % 2 == 0) {

k = k / 2;

c = c * c;

}

else {

k = k - 1;

b = b * c;

}

}

System.out.println(b);

}

I understand what the algorithm of the book is doing, but what I don't understand is why what I am doing is wrong.

Could someone please point out the flaw with my logic?

For instance, if I pass a = 3 and n = 7, my algorithm prints 3^11 = 177147 (which is incorrect), whereas the book's algorithm prints out 3^7 = 2187 (which is correct).

Any input would be GREATLY appreciated!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Question about O(log n) algorithm for computing a^n

Have something to add?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**