- #1

s3a

- 818

- 8

## Homework Statement

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.

## Homework 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

## 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:

```
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!