Discrete Math complexity of algorithms

[phoenixwhiterose]

Determine the number of multiplications used to find x^2^k starting with x and successively squaring(to find x^2, x^4, so on). Is this a more effiecient way to find x^2^k than by multiplying x by itself the appropiate amount of times?

Help please.

 

[TchrWill]

Determine the number of multiplications used to find x^2^k starting with x and successively squaring(to find x^2, x^4, so on). Is this a more effiecient way to find x^2^k than by multiplying x by itself the appropiate amount of times?

Help please

What are you assuming the expression is; x^(2^k) or (x^2)^k?

 

[phoenixwhiterose]

x^(2^k)

 

[soroban]

Hello, phoenixwhiterose!

Determine the number of multiplications used to find \(\displaystyle x^{2^k}\)
starting with \(\displaystyle x\) and successively squaring to find \(\displaystyle x^2,\,x^4\), and so on.
Is this a more effiecient way to find \(\displaystyle x^{2^k}\) than by multiplying \(\displaystyle x\) by itself
the appropiate amount of times? . . . Yes!

With no parentheses, the form is assumed to be: \(\displaystyle \,x^{(2^k)}\)

For \(\displaystyle k\,=\,1,2,3,\cdots\), we have: \(\displaystyle \,x^2,\,x^4,\,x^8,\,x^{16},\,\cdots\)


Which do you think is more efficient?

. . \(\displaystyle \begin{array}{cccc}x^2 &=& x\cdot x \\ x^4 &=&(x^2)^2 \\ x^8 &=&(x^4)^2 \\ \vdots & &\vdots\end{array}\) . . . . \(\displaystyle \begin{array}{ccccc}x^2 &=&x\cdot x \\ x^4 &=&x\cdot x\cdot x\cdot x \\ x^8 &=& x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x \\ \vdots & &\vdots\end{array}\)