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!

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

  1. Nov 29, 2017 #1

    s3a

    User Avatar

    1. The problem statement, all variables and given/known data
    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.

    2. Relevant 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

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

        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!
     
  2. jcsd
  3. Nov 29, 2017 #2

    rcgldr

    User Avatar
    Homework Helper

    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
     
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: Question about O(log n) algorithm for computing a^n
  1. Log(n) algorithm (Replies: 5)

Loading...