いくつかの回答をいただいた「るい乗・べき乗の計算量」なのですが、説明がまずかったようなので再度、タイトルを変更して質問させて下さい。
例えば５の７乗を計算する場合、５×５×５×５×５×５×５と普通に考えれば６回の「かけ算」で計算ができます。「かけ算６回」ということですね。でも実際は、５×５で５の２乗を計算したら、（５の２乗）×（５の２乗）で５の４乗を計算して、それに５の２乗と５をかける。つまり、
（５×５）×（５の２乗）×（５の２乗）×５
の４回のかけ算で済みますよね。
１６乗なら４回ですし、４７乗ならば８回です。
どなたかこの「べき乗を（掛け算だけで）計算するための掛け算の最小回数」を求める求め方、、、を教えてください。
ちなみに、暗号などの世界や、プログラム言語内での定義では、
a^47=((((axa)xa^2)xa^4)xa^8)xa^16xa^8xa^4xa^2xa
のように、２倍を基準に計算を省いています。実用的にはそれで十分なのですが、私が知りたいのは「実用」ではなくて、最小の回数を求める方法です。
投稿日時 - 2003-08-04 11:09:04
0人が「このQ&Aが役に立った」と投票しています
回答（7件中 1～5件目)
mahler3さん、たびたび失礼します。#6の者です。
まだ、確認事項に答えてもらってませんよ。
＞確認ですが、指数の範囲を教えて下さい。
強引とは言いましたが、さすがに総当たりは私もやる気がしません。
取り敢えず問題を次のように定式化します。
Fを次のような条件を充たす有限数列の全体とする。
１ 初項は２
２ 狭義単調増加
３ Fに属する任意の数列｛f_n｝の隣り合う２項f_n、f_n+1の差は１であるかまたは、あるk<nが存在してf_k
に等しい。
このとき、与えられた自然数ｎに対し、Ｆに属する数列でｎを末項とし、長さが最も短いものを求める事。
一応プログラミングの方針としては、重み付き根付き木を、キュー構造を利用して作っていく事になるでしょう。
投稿日時 - 2003-08-06 23:16:46
補足
すいません。指数の範囲は「無制限」です。というか、どんな自然数に対しても、求められるようなアルゴリズムの存在を知りたかったのですが、、、どうやら無いようですね。
一生懸命考えていただいてありがとうございました。ツリーで探索ですか。うーん。そうですねえ。それしかないかあ。力業しか無いのでしょう、、、かあ、、、ねえ。きっと。
投稿日時 - 2003-08-07 00:38:56
４７乗ならば８回です。と書いていますが、
a^47=((((axa)xa^2)xa^4)xa^8)xa^16xa^8xa^4xa^2xa
この計算では９回となるのではないですか?
(a^((2+2+1)^(2*2*2+1))×5^2)
=(((axa)xa^2)xa)a^5xa^10xa^20xa^5xa^2=a^47
此が、８回となるのではないですか。
投稿日時 - 2003-08-04 22:30:18
補足
その通りです。８回なのです。だから
a^47=((((axa)xa^2)xa^4)xa^8)xa^16xa^8xa^4xa^2xa
は駄目なんです。この例は、単に計算回数を減らすと言う「実用」では一般的に単純だし（２進数で表せばどう計算すれば良いかすぐ分かる）ということです。ネット上ではそう言う説明が多いので、きっとそう言う回答が多いだろうと思い、釘をさしておいたのですが、、、逆効果だったかも。拙い説明ですいません。
投稿日時 - 2003-08-04 22:35:51
計算の途中結果を再利用していることが問題を難しくしていますね。
再利用を許さないのであれば、
１．ターゲットの数を２進数で表す。
２．先頭の１を除く。
３．０を１、１を２と数えて、数字の合計を求める。
で良いと思います。
２進数で表した数は
０→現在の数を２乗する。
１→現在の数を２乗して元の数を掛ける。
に対応するからです。
途中結果の再利用を許すとすると、ｎ乗の時の回数をＣ（ｎ）と表したとして、
１． Ｃ（１）＝０
２． Ｃ（ｎ）＝Ｃ（ｎ－１）＋１
３． Ｃ（ｎ）＝Ｃ（ｎ／２）＋１
４． Ｃ（ｎ）＝Ｃ（ｍ）＋１
但し、ｎ＞ｍ、Ｃ（ｍ）の計算過程にＣ（ｎ－ｍ）が使われる時
４’．Ｃ（ｎ）＝Ｃ（ｍ）＋Ｃ（ｎ－ｍ）
但し、ｎ＞ｍ、Ｃ（ｍ）の計算過程にＣ（ｎ－ｍ）が使われない時
のようなルールになると思いますから、再帰的に計算して答えは出せるかも
しれません。
検証はしていません。
投稿日時 - 2003-08-04 19:05:26
補足
考えていただいてありがとうございます。
この問題はなかなか難しいようです。
それでもなんとか、
解き方があるのならその解き方（あるごりずむ？）
ないのであれば、まだ解けていないのだという確認
が欲しいのです。とはいっても、未解決って訳ではないだろうと思うのですが、、、。
投稿日時 - 2003-08-04 22:41:29
るい乗・べき乗の計算ですので、この問題は、
４７にするために、１，２，括弧、＋、かけ算、できあがった数のみをつかって最小限で作り上げる問題に変わるのではないですか。
47=5*9+2が最小となると思いますけど、
((2+2+1)×(2*2*2+1))+2即ち(5^((2+2+1)^(2*2*2+1))×5^2)で、９回になると思います。
(1)最小回数でするためには、２，４，８，１６、３２でできあがるのがよい。
(2)此で出来なければ、(1)に１を加えた数で、出来た方がよい。
(3)できあがった数を利用出来る方がよい。
(4)端数については、(1) , (2) ,(3)の考えを繰り返すのみではないですか。
投稿日時 - 2003-08-04 14:38:11
