乗算回数最小の冪乗アルゴリズム

質問

断面ｎ次モーメントを計算するプログラムを書いていてふと思ったのですが，
X^n を乗算の繰り返しで計算する場合，一般の自然数ｎについて乗算回数最小の
アルゴリズムって存在するんでしょうか？

たとえばｎが２の冪乗の場合，２乗を繰り返すと１回ごとに
X → X^2 → X^4 → X^8 → X^16 → …
となるので，X^n は log2(n) 回の乗算で計算でき，たぶんこれが最小だと思います．

その他のｎについてはどうでしょうか？
ｎの素因数分解とか使えばうまくいくんでしょうか？

回答No.1

noname#22058 · ベストアンサー

ここのサイトが参考になるようです。

参考URL：

http://www.asahi-net.or.jp/~kc2h-msm/mathland/math11/math1103.htm

お礼

回答ありがとうございます．
その URL にあるのとほとんど同じ方法は私も考えました．
(質問に書いた，２乗を繰り返す方法を一歩進めればすぐ思いつく方法ですから．)

これは実用上は十分効率の良いアルゴリズムだと思いますが，
残念ながら必ずしも乗算回数最小ではないようです．
(すぐには具体例が思い浮かばないのですが．)
http://math.pisan-dub.jp/concrete/index.php?catid=2&subcatid=15&itemid=9