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

[.d9n.]

Homework Statement

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.

Homework Equations

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 isn't 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 I am pretty sure that's wrong.

any ideas on where to look?

 

[Office_Shredder]

Calculate a⁴ in 2 multiplications and it should be clear how to proceed

 

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

 

[Borek]

a⁶ 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.