Why does this algorithm (about computing a^n) work?

In summary: To clarify: c := c * c; replaces the old value of c (which is no longer needed) with the square of the old value of c, so at the end of the first pass through the loop, c contains a^2. b := b * c; replaces the old value of b with the product of the old values of b and c, so at the end of the first pass through the loop, b contains just a as the algorithm steps through the while loop, b is multiplied by "a" once for each time the k value is odd (the "if" statement's "else" clause), and c is squared each time the k value is even (the "if" statement's "then
  • #1
s3a
818
8

Homework Statement


Here is the algorithm (which works perfectly) for computing a^n for any integer a and a nonnegative integer n in Pascal-style pseudocode.:
Code:
k := n; b := 1; c:= a;
{a^n  = b * (c^k)}
while k <> 0 do begin
    if k mod 2 = 0 then begin
        k := k div 2;
        c := c * c;
    end else begin
        k := k - 1;
        b := b * c;
    end;
end;

Homework Equations


The given algorithm for computing a^n, where a is any integer and n is a nonnegative integer.

The Attempt at a Solution


I just wanted to know why this code works.

In particular, could someone please help me understand the roles that
Code:
c := c * c;
and
Code:
b := b * c;
play in the algorithm (because I'm trying to also understand the algorithm and not just memorize it)?

Any input would be GREATLY appreciated!
 
Physics news on Phys.org
  • #2
I don't see how it returns the result, but the idea is simple - half of the algorithm is covered by the comment {a^n = b * (c^k)} (that's what b:=b*c; does), the other half relies on the fact a2n = an*an (that's what c:=c*c; does).
 
Last edited:
  • #3
Trace how it works step by step, for say k = 37. You should be able to see how it calculates b = a^37, and what c contains at each step. (Note, there are a lot fewer that 37 iterations round the loop, so this shouldn't take too long).
 
  • #4
AlephZero said:
Trace how it works step by step, for say k = 37.
Note - since a is an integer, you'd need a 64 bit environment to calculate even in the case of a = 2, (2^37). For a 32 bit environment, a smaller value of k would be needed.
 
  • #5
s3a said:

Homework Statement


Here is the algorithm (which works perfectly) for computing a^n for any integer a and a nonnegative integer n in Pascal-style pseudocode.:
Code:
k := n; b := 1; c:= a;
{a^n  = b * (c^k)}
while k <> 0 do begin
    if k mod 2 = 0 then begin
        k := k div 2;
        c := c * c;
    end else begin
        k := k - 1;
        b := b * c;
    end;
end;
The only thing missing from this description is the output. When the loop ends, the final result is in b.

Take 2^10 as an example.
Before looping: k=10; b=1; c=2
At end of 1st pass: k=5; b=1; c=4
At end of 2nd pass: k=4; b=4; c=4
At end of 3rd pass: k=2; b=4; c=16
At end of 4th pass: k=1; b=64; c=16
At end of 5th pass: k=0; b=1024; c=16

The comment "a^n = b * (c^k)" is the clue. For each pass through the loop a^n is still equal to "b * (c^k)".
 
  • #6
rcgldr said:
Note - since a is an integer, you'd need a 64 bit environment to calculate even in the case of a = 2, (2^37). For a 32 bit environment, a smaller value of k would be needed.

The question says it is pseudocode, not real Pascal code to be executed. Some languages have arbitrary-precision arithmetic as a part of the language standard - see http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Stand-alone_application_software for a list.

The statement
Here is the algorithm (which works perfectly) for computing a^n for any integer a and a nonnegative integer n
couldn't possibly be correct otherwise.
 
  • #7
Everyone:
Thank you for your answers.

Borek:
About the result, it is in the final value of b. What you said made me understand the
Code:
c := c * c;
part, so thanks for that.

Everyone:
However, I'm still confused about the
Code:
b := b * c;
part, because I have trouble with intuitively understanding how b “knows” which value to have prior to being multiplied by c.

Please tell me if that doesn't make sense, so I could find another way of explaining it.

AlephZero, .Scott:
I probably should have said this, but I have already worked out the algorithm several times before posting this thread.

rcgldr:
As AlephZero said, the code in my opening post is (Pascal-style) pseudocode (instead of “real” Pascal code).

Everyone:
Also, is it just me, or does the comment given in the opening post's pseudocode only hold true if the code is modified to be as follows?:
Code:
k := n; b := 1; c:= a;
{a^n  = b * (c^k)}
while k <> 0 do begin
    if k mod 2 = 0 then begin
        c := c * c;
        k := k div 2;
    end else begin
        b := b * c;
        k := k - 1;
    end;
end;
 
  • #8
s3a said:
Everyone:
However, I'm still confused about the
Code:
b := b * c;
part, because I have trouble with intuitively understanding how b “knows” which value to have prior to being multiplied by c.
Please tell me if that doesn't make sense, so I could find another way of explaining it.
b doesn't "know" what value to have - it just has a value. The assignment statement above says to multiply the current values of b and c, and put the resulting product back in b, thereby overwriting the previous value. For example, if at the start b is 20 and c is 3, b's new value will be 60.
 
  • #9
s3a said:
Also, is it just me, or does the comment given in the opening post's pseudocode only hold true if the code is modified to be as follows?
The order of operations doesn't matter, the statement only holds true after both c and k or both b and k are updated.
 
  • #10
s3a said:
Everyone:
However, I'm still confused about the
Code:
b := b * c;
part, because I have trouble with intuitively understanding how b “knows” which value to have prior to being multiplied by c.

Please tell me if that doesn't make sense, so I could find another way of explaining it.[/code]
OK, here is how the code works:
1) You start with one condition where a^n = b c^k, specifically when b=1, c=a, and k=n.
2) When k is odd, you decrement k and multiply b by c. So a^n is still equal to b c^k.
3) When k is even, you have k and square c. So a^n is still equal to b c^k.
4) By continuous checking cases 2 and 3, you eventually get to k=1. At that point, you have a^n = bc.
5) Since 1 is odd, you will decrement k and set b=b*c. At that point a^n = b c^k, but the value of k is zero, so c^k is 1 and you have a^n = b.

If you don't understand this, let me know and I will try to explain it better.
Basically, you set a^n = b c^k, and then keep on driving k down towards zero. When it reaches 0, b must have the result.
 
  • #11
Mark44 (and everyone else):
I meant:
What about the logic behind the algorithm ensures that, in the end, b is the exact multiplicand that, when multiplied with c, yields a^n?

In other words, what about the logic ensures that b compounds to the exact value needed for the next time k is odd?

rcgldr:
Oh, that makes sense.

Edit:
.Scott, I just saw that you posted something, I will check it out now.
 
  • #12
.Scott, I think I get it now!

Okay, so what the algorithm does is it defines a^n by the product b * c^k, and it works on accumulating “numeric weight” in the c variable by continually squaring the value that c holds and raising that new value held in the c variable by half the exponent (such that the algorithm keeps the a^n = b * c^k equation true, but has yet to shift the “numeric weight” to the b variable), as long as k is even, and, then, when k is odd, works on shifting that “numeric weight” to the b variable, by making use of the fact that a^n = (b * c) * c^(k – 1).

Does it seem like I understand it now?
 
  • #13
The insight needed is to recognize that if the exponent is expressed as a binary number, you can see when k is going to be odd or even as the algorithm progresses.

For example, if n is 37, expressing 37 as a binary number gives 100101. Start at the right and moving left one bit at a time, you can how k will be even or odd each step.

If the exponent were just a power of two, all that would be needed is to do c := c*c the appropriate number of times. If n isn't exactly a power of two, then you will need to do the b := b*c when a non zero bit shifts off the right end of the binary representation of n as you shift it right.

That's what the:

if k mod 2 = 0 then begin
k := k div 2;

is all about. It's converting the exponent to binary, one bit at a time.
 
  • #14
s3a said:
Also, is it just me, or does the comment given in the opening post's pseudocode only hold true if the code is modified to be as follows?:

Code:
k := n; b := 1; c:= a;
{a^n  = b * (c^k)}
while k <> 0 do begin
    if k mod 2 = 0 then begin
        c := c * c;
        k := k div 2;
    end else begin
        b := b * c;
        k := k - 1;
    end;
end;

As other said, that makes no difference. Personally I would have written if like this, which seems more logical to me because you do all the processing for one binary digit of k on one pass through the loop, not sometimes one pass and sometimes two:

Code:
while k <> 0 do begin
    if k mod 2 <> 0 then begin
        b := b * c;
    end;
    c := c * c;
    k := k div 2;
end;

Note the "k := k - 1" is no longer needed.
 
  • #15
Okay, so I think I finally get it.

Thanks everyone!
 

Related to Why does this algorithm (about computing a^n) work?

1. Why do we use algorithms to compute a^n?

Algorithms are an efficient and systematic way of solving a problem or completing a task. In the case of computing a^n, using an algorithm allows us to quickly and accurately calculate the result without having to manually perform the calculations.

2. How does the algorithm for computing a^n actually work?

The algorithm for computing a^n involves breaking down the problem into smaller, simpler steps. It uses the fact that a^n can be rewritten as a*(a^(n-1)) and recursively applies this formula until n reaches 1, at which point the result is a. This approach reduces the number of calculations needed and makes the process more efficient.

3. What is the time complexity of this algorithm?

The time complexity of this algorithm is O(log n). This means that as the input (n) increases, the number of operations required to compute a^n does not increase at the same rate. Instead, it increases at a much slower rate, making the algorithm very efficient for large values of n.

4. Can this algorithm be used for any value of a and n?

Yes, this algorithm can be used for any value of a and n. However, it is most commonly used for computing large exponents, as it becomes more efficient compared to other methods as n increases.

5. Are there any limitations to this algorithm?

One limitation of this algorithm is that it can only be used for positive integer values of n. It cannot be applied to negative exponents or fractional exponents. Additionally, if the input values are extremely large, the algorithm may face issues with overflow or rounding errors.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
972
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Replies
9
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
33
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
Back
Top