1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Aug 14, 2014 #1

    s3a

    User Avatar

    1. The problem statement, all variables and given/known data
    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 (Text):
    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;
    2. Relevant equations
    The given algorithm for computing a^n, where a is any integer and n is a nonnegative integer.

    3. 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 (Text):
    c := c * c;
    and
    Code (Text):
    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!
     
  2. jcsd
  3. Aug 14, 2014 #2

    Borek

    User Avatar

    Staff: Mentor

    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: Aug 14, 2014
  4. Aug 14, 2014 #3

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  5. Aug 14, 2014 #4

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  6. Aug 14, 2014 #5
    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)".
     
  7. Aug 14, 2014 #6

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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
    couldn't possibly be correct otherwise.
     
  8. Aug 15, 2014 #7

    s3a

    User Avatar

    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 (Text):
    c := c * c;
    part, so thanks for that.

    Everyone:
    However, I'm still confused about the
    Code (Text):
    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 (Text):
    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;
     
  9. Aug 15, 2014 #8

    Mark44

    Staff: Mentor

    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.
     
  10. Aug 15, 2014 #9

    rcgldr

    User Avatar
    Homework Helper

    The order of operations doesn't matter, the statement only holds true after both c and k or both b and k are updated.
     
  11. Aug 15, 2014 #10
    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.
     
  12. Aug 15, 2014 #11

    s3a

    User Avatar

    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.
     
  13. Aug 15, 2014 #12

    s3a

    User Avatar

    .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?
     
  14. Aug 15, 2014 #13

    The Electrician

    User Avatar
    Gold Member

    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.
     
  15. Aug 15, 2014 #14

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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 (Text):

    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.
     
  16. Aug 16, 2014 #15

    s3a

    User Avatar

    Okay, so I think I finally get it.

    Thanks everyone!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Why does this algorithm (about computing a^n) work?
Loading...