(1)2^2=2*2=4,2^4=(2^2)*(2^2)=4*4=16,2^8=(2^4)*(2^4)=16*16=256,
2^10=(2^2)*(2^8)=4*256=1024,共做4次乘法.
(2)2^2=2*2=4,2^4=(2^2)*(2^2),2^8=(2^4)*(2^4),2^16=(2^8)*(2^8)
2^20=(2^16)*(2^4),共做5次乘法.
(3)2^2=2*2=4,2^4=(2^2)*(2^2),2^8=(2^4)*(2^4),2^16=(2^8)*(2^8)
2^30=(2^16)*(2^8)*(2^4)*(2^2),共做6次乘法.
对一般的N,x,计算x^N可采用如下方法,将N表示为二进制数
a1a2a3,...an,其中a1,a2,a3,...,an是0或1
计算x^2,x^4,x^8,...,x^(2^n),
x^N=a1*x^2+a2*x^4+a3*x^8+...+an*x^(2^n),
即将对应二进制数为1的项相加.
如10=1010(二进制),2^10=(2^2)*(2^8)
如20=10100(二进制),2^20=(2^4)*(2^16)
如30=11110(二进制),2^20=(2^2)*(2^4)*(2^8)*(2^16)