繰り返し2乗法
repeated squaring
binary exponentiation
冪をより少ない回数の乗算で得るアルゴリズム
n^25 = (((n^2 * n)^2)^2)^2 * n
指数法則による工夫を機械的にできて便利あんも.icon 誰もがやっている工夫で、特別なものではないことを強調したい
必ず少なくできるわけではない
n^15 = ((n^2 * n)^2 * n)^2 * n: 6回
n^15 = (n^{2+1})^{2*2+1}: 5回
2進表示を配列にして、取り出してチェックする
digits()は逆向き入っていて便利あんも.icon
code:jl
function power(n, x)
bits = digits(x, base=2)
p = n
acc = one(n)
for b in bits
if b == 1
acc *= p
end
p *= p
end
return acc
end
右シフトを使えば配列は不要
回数をチェックして、後片付けしておく
return acc * p
code:jl
function power(n, x)
p = n
acc = one(n)
while x > 1
if isodd(x)
acc *= p
end
n ÷= 2
p *= p
end
return acc * p
end