Hi,
I am trying to understand the solution of the question 4.7 but probably I am missing something. The problem asks to compute x^y and on top of my head I could just remember the brute force solution, for example 3^13 could be described as:
3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 = 1594323
Ok, the book states that the algorithm can be improved trying to get more work done with each multiplication and in the case above this could be obtained multiplying the squares such as below:
(3^2) * (3^2) * (3^2) * (3^2) * (3^2) * (3^2) * 3 = 1594323 // in this case the expoent is odd so we had to multiply the squares by the remaining 3.
The book states that a better performance (less multiplications) can be obtained if we group the terms by a higher expoent such as:
(3^3) * (3^3) * (3^3) * (3^3) * 3 = 1594323
I think that the paragraph
- “Generalizing, if the least significant bit of y is 0, the result is (x^y/2)^2”, means that if the LSB is 0 we have an even number so there is no need to perform the addtional multiplication mentioned above …
- “Otherwise, it is x*(x^y/2)^2”, it’ similar 3^13 that I’ve mentioned (odd expoent)
Let’s go to the question … I saw the following snippet:
// x = 3;
// y = 13;
double result = 1.0;
long power = y;
while (power != 0) { // 13 = 00001101
if ((power & 1) != 0) {
result *= x; // why is it computing result only when a 1 is found?
}
x *= x;
power >>>= 1;
}
return result;
Question: Why is the routine computing the variable result only when a “1” is found in the binary representation of the exponent?.
I “think” a possible explanation would be that the maximum y in such case would be 00001111 (all ones) “15” in decimal and as we’re calculating the power of 13 (00001101) (a missing one) we couldn’t take this zero into account … Another thing that emerged in my mind was that each position of the binary representation represents a “power” such as:
0 0 0 0 1 1 0 1
| | |
^3 ^2 ^0
8 + 4 +1 = 13
I noticed that the value accumulated in x will be:
(3*3)=9 result(1*3) = “3”
\
9*9=81 result(skip not one) = “3”
\
81*81=6561 result(3*81) = “243”
\
6561*6561=43046721 result(243*6561) = “1594323”
I’ve found that this is a really interesting problem … am I thinking the right way?, I mean is my approach correct?
Thank you very much!
Marcos