![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
NetaTaneMenu?
例えば3^7を計算するのに、単純に掛ければ６回の掛け算が必要になりますよね。
3×3×3×3×3×3×3
でも、実際には 3×3=9 9×9=81 81×3=243 243×3=729 という具合に計算するわけですから、４回の掛け算で済みます。
質問その１、７乗を掛け算だけで計算するのに掛け算は４回「必要」か？
（掛け算３回で８乗を計算してから３で「割る」なんてのは無しです。）
質問その２、ｎ乗するときに必要な掛け算の回数を求める関数？プログラム？アルゴリズム？あるいは表？・・・を教えて下さい。
（2003.7.30.むらい）
この問題をみると，昔のプログラミングの心得で，演算の回数をいかに減らすかに気を使ったことを思い出しますね。3^7のケースで4回というのは，他のやりかたもあるけれど，いずれにしても最小回数であるようです。一般の場合に拡張した場合の答えは，整数をn進法で表現することと何か関係がありそうな。
そうなんですよね。ネット上をいろいろと探すのですが、２進法でとりあえず減らしたからまあ好いやって言うのが殆ど。数列百科事典でさえ役に立ちませんでした。33乗なんかは面白くて3x11で考えるより素直に2^5+1で考えるほうが少ない回数で計算できるのです。さてさて、どういうアルゴリズムが良いのでしょう。ほとほと困っているのですが、まあ楽しんでいます。でも分かった・分かっている人はもったいぶらずに教えてください。あと万が一「それは分かっていないことなんだ」ってことが分かっている場合も、、、
