るい乗・べき乗の計算量

質問

例えば５の７乗を計算する場合、５×５×５×５×５×５×５と普通に考えれば６回の「かけ算」で計算ができます。「かけ算６回」ということですね。でも実際は、５×５で５の２乗を計算したら、５の２乗×５の２乗で５の４乗を計算して、それに５の２乗と５をかける。つまり、
（５×５）×（５の２乗）×（５の２乗）×５の４回のかけ算で済みます。

ちなみに、４７乗ならば８回だと思うのですが、、、
どなたかこの「べき乗を計算するためのかけ算の最小回数」を求める求め方、、、を教えてください。

回答No.5

pancho

＃１の者です。

この手の問題は、回数についての「見込みがついていて検証のみ場合」と「見当すらついていない場合」で方針が違ってきます。
質問の仕方から、問題を提起しただけで見込みもついていない状態と判断されたため、ご自身での努力を促す意味でヒントのみとしました。

「２進数表記せよ」とは、これによって回数の上限と下限が抑えられるので、検討の第一段階となるからですが、これも必要ないようですね。

コメントを見ていると、とても人に教えを請う態度ではなさそうなので、これ以上は差し控えておきます。

以上。

回答No.4

gamasan

にゃるほど　５条を先に計算するのか・・・大汗
失礼しました。

補足

面倒なのでまとめてコメントを。
２進数で済むのならここで尋ねたりはしません。
それから、知りたいのは一般的な解法なんです。
a^27=(((axa)xa)xa^3xa^3)xa^9xa^9
で合計６回ですよね。
(((axa)xa^2)xa^4)xa^8xa^8xa^2xa
だと７回ですよね。
27＝11011（２進数）
かな。
これじゃあ困るんです。最小じゃない。

回答No.3

gamasan

（５×５）×（５の２乗）×（５の４乗）×（５の８乗）
×（５の16乗）×（５の16乗÷５）必殺技・・・だめ？

掛け算しか使えないなら　最後の15乗を８乗、４乗、２乗
５に分けるから　９回じゃないですか？

ヒントとしては　トーナメント表でしょう
何段の表になるかですね

回答No.2

yuusukekyouju

最小回数は8回でよいと思います。
1回　5×5＝5^2
2回　5^2×5^2＝5^4
3回　5^4×5＝5^5
4回　5^5×5^5＝5^10
5回　5^10×5^5＝5^15
6.7.8回　5^15×5^15×5^15×5^2=5^47
あとは7回でできない証明をすればよいのではないでしょうか、この証明は地道に細かく場合に分けてやっていくしかないと思います。

参考までに計算回数だけでいえば5＾48を計算して5で割れば7回でできると思います。

補足

４７乗だけを確かめたいのではないのです。
一般的にn乗であれば何回のかけ算でできるか？
その最小値を示すアルゴリズムなり関数なりを知りたいのです。
ですから高々４７についてだけ証明してもね。

わり算は使いません。（笑）

回答No.1

pancho

答えをすぐ書いてしまうのはもったいないので、ヒントだけにしておきます。

べき数を２進数で表記してみてください。その内、１となっている数を数えると...。

以上。

補足

甘いですね。