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!

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
    n=1000000=log_a(y)=

    or

    y=e^(nlog(a))=e^(1000000log(a))

    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

    Office_Shredder

    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

    or

    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

    Borek

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Calculate a^n, if n=1000000 then it should be calculated in 40 multiplications
Loading...