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

• s3a
In summary, the conversation discusses creating an algorithm, with a complexity of O(log n), that computes a^n without changing the values of a and n. Two different solutions are provided, one by the individual and one from a book. The book's solution is correct, while the individual's solution produces incorrect results. The flaw in the individual's logic is that it does not follow the method of exponentiation by repeated squaring.
s3a

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

The method is called exponentiation by repeated squaring. One variable is squared every loop, the result variable is multiplied by the repeatedly squared variable for each 1 bit in the exponent, starting with the least significant bit.

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

## 1. What is an O(log n) algorithm?

An O(log n) algorithm is a type of algorithm that has a logarithmic time complexity, meaning that its runtime increases at a slower rate as the input size increases. In other words, as the input size doubles, the runtime of the algorithm only increases by a constant amount.

## 2. How does an O(log n) algorithm work?

An O(log n) algorithm works by dividing the input size in half at each step. This allows the algorithm to quickly narrow down the search space and find the solution in a time-efficient manner.

## 3. Why is an O(log n) algorithm useful for computing a^n?

An O(log n) algorithm is useful for computing a^n because it can quickly handle large input sizes without significantly increasing the runtime. This is important for computing large exponents, as the input size (n) can be very large.

## 4. What are some common examples of O(log n) algorithms?

Some common examples of O(log n) algorithms include binary search, finding the maximum or minimum element in a sorted array, and some tree traversal algorithms such as binary search tree traversal.

## 5. Are there any downsides to using an O(log n) algorithm for computing a^n?

One potential downside of using an O(log n) algorithm for computing a^n is that it may require additional space or memory to store the intermediate results. Additionally, it may be more complex to implement compared to other simpler algorithms with higher time complexities.

• Engineering and Comp Sci Homework Help
Replies
7
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
4
Views
1K
• Engineering and Comp Sci Homework Help
Replies
18
Views
1K
• Engineering and Comp Sci Homework Help
Replies
7
Views
2K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Engineering and Comp Sci Homework Help
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
14
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K