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!

Homework Help: Calculate a^n, if n=1000000 then it should be calculated in 40 multiplications

  1. Mar 13, 2012 #1
    1. The problem statement, all variables and given/known data

    Given integers a and n, where n > 0, how many multiplications
    are needed to calculate a^n? You are not expected to produce a
    precise answer, but if n is a million it should become clear from
    your answer that 40 multiplications will suffice.

    2. Relevant equations

    3. The attempt at a solution

    y=a^n so n=log_a(y)
    so if n=1000000



    not sure how I'm meant to do this, as far as i am (aware/ can find) there isnt a relationship between a and n that could do it to 40 multiplications as this would mean you have to knwo a^25 000 and then maybe multiply this by 40, but im pretty sure thats wrong.

    any ideas on where to look?
  2. jcsd
  3. Mar 13, 2012 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Calculate a4 in 2 multiplications and it should be clear how to proceed
  4. Mar 13, 2012 #3
    so by two multiplications do you mean
    a^2 x a^2
    so for the qu you mean
    a^25000 x a^25000 x ... x a^25000 - 40 times

    say n=1000000

    is this what you mean

    a^1000000=a^500000 x a^500000 =a^ (a^25000)^20 x (a^25000)^20 = (a^25000)^40


    a^2^500000= a^2^2^250000 = a^2^2^2^125000 = a^2^2^2^2^62500 = a^2^2^2^2^2^31250 ..........
    or neither
  5. Mar 13, 2012 #4


    User Avatar

    Staff: Mentor

    a6 in three multiplications:

    First multiplication:
    $$a\times a=a^2$$

    Second multiplication:
    $$a\times a^2 = a^3$$

    Third multiplication:
    $$a^3\times a^2=a^6$$

    Idea is to reuse what you already calculated earlier.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook