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

[s3a]

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

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

c := c * c;

and

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!

 

[Borek]

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 a²ⁿ = aⁿ*aⁿ (that's what c:=c*c; does).

 

[AlephZero]

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).

 

[rcgldr]

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.

 

[.Scott]

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

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)".

 

[AlephZero]

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.

 

[s3a]

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

c := c * c;

part, so thanks for that.

Everyone:
However, I'm still confused about the

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

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;

 

[Mark44]

Everyone:
However, I'm still confused about the

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.

 

[rcgldr]

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.

 

[.Scott]

Everyone:
However, I'm still confused about the

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.

 

[s3a]

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.

 

[s3a]

.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?

 

[The Electrician]

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.

 

[AlephZero]

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

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:

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.

 

[s3a]

Okay, so I think I finally get it.

Thanks everyone!