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

1. Mar 13, 2012

### .d9n.

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

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. Mar 13, 2012

### Office_Shredder

Staff Emeritus
Calculate a4 in 2 multiplications and it should be clear how to proceed

3. Mar 13, 2012

### .d9n.

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

4. Mar 13, 2012

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