- 締切済み
べき乗を最小回数の掛算で
いくつかの回答をいただいた「るい乗・べき乗の計算量」なのですが、説明がまずかったようなので再度、タイトルを変更して質問させて下さい。 例えば５の７乗を計算する場合、５×５×５×５×５×５×５と普通に考えれば６回の「かけ算」で計算ができます。「かけ算６回」ということですね。でも実際は、５×５で５の２乗を計算したら、（５の２乗）×（５の２乗）で５の４乗を計算して、それに５の２乗と５をかける。つまり、 （５×５）×（５の２乗）×（５の２乗）×５ の４回のかけ算で済みますよね。 １６乗なら４回ですし、４７乗ならば８回です。 どなたかこの「べき乗を（掛け算だけで）計算するための掛け算の最小回数」を求める求め方、、、を教えてください。 ちなみに、暗号などの世界や、プログラム言語内での定義では、 a^47=((((axa)xa^2)xa^4)xa^8)xa^16xa^8xa^4xa^2xa のように、２倍を基準に計算を省いています。実用的にはそれで十分なのですが、私が知りたいのは「実用」ではなくて、最小の回数を求める方法です。
- みんなの回答 （7）
- 専門家の回答
みんなの回答
- graphaffine
- ベストアンサー率23% (55/232)
mahler3さん、たびたび失礼します。#6の者です。 まだ、確認事項に答えてもらってませんよ。 ＞確認ですが、指数の範囲を教えて下さい。 強引とは言いましたが、さすがに総当たりは私もやる気がしません。 取り敢えず問題を次のように定式化します。 Fを次のような条件を充たす有限数列の全体とする。 １ 初項は２ ２ 狭義単調増加 ３ Fに属する任意の数列｛f_n｝の隣り合う２項f_n、f_n+1の差は１であるかまたは、あるk<nが存在してf_k に等しい。 このとき、与えられた自然数ｎに対し、Ｆに属する数列でｎを末項とし、長さが最も短いものを求める事。 一応プログラミングの方針としては、重み付き根付き木を、キュー構造を利用して作っていく事になるでしょう。
- graphaffine
- ベストアンサー率23% (55/232)
確認ですが、指数の範囲を教えて下さい。 １００ぐらいまでなら何とかプログラムで強引に求められるかもしれないが それ以上はかなり難しそう。 暗号計算云々といってるのですから１００程度じゃお話にはならないかもしれないが。
補足
そうですね。私は十進ベーシックで総当たりの強引なプログラムを組んでみましたが、メモリやスピードはもう一杯一杯です。 なんとかもう少し美味いアルゴリズムを知りたいのですが。 もしかしてＮＰ完全？
- mirage70
- ベストアンサー率28% (32/111)
４７乗ならば８回です。と書いていますが、 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 此が、８回となるのではないですか。
補足
その通りです。８回なのです。だから a^47=((((axa)xa^2)xa^4)xa^8)xa^16xa^8xa^4xa^2xa は駄目なんです。この例は、単に計算回数を減らすと言う「実用」では一般的に単純だし（２進数で表せばどう計算すれば良いかすぐ分かる）ということです。ネット上ではそう言う説明が多いので、きっとそう言う回答が多いだろうと思い、釘をさしておいたのですが、、、逆効果だったかも。拙い説明ですいません。
- ranx
- ベストアンサー率24% (357/1463)
計算の途中結果を再利用していることが問題を難しくしていますね。 再利用を許さないのであれば、 １．ターゲットの数を２進数で表す。 ２．先頭の１を除く。 ３．０を１、１を２と数えて、数字の合計を求める。 で良いと思います。 ２進数で表した数は ０→現在の数を２乗する。 １→現在の数を２乗して元の数を掛ける。 に対応するからです。 途中結果の再利用を許すとすると、ｎ乗の時の回数をＣ（ｎ）と表したとして、 １． Ｃ（１）＝０ ２． Ｃ（ｎ）＝Ｃ（ｎ－１）＋１ ３． Ｃ（ｎ）＝Ｃ（ｎ／２）＋１ ４． Ｃ（ｎ）＝Ｃ（ｍ）＋１ 但し、ｎ＞ｍ、Ｃ（ｍ）の計算過程にＣ（ｎ－ｍ）が使われる時 ４’．Ｃ（ｎ）＝Ｃ（ｍ）＋Ｃ（ｎ－ｍ） 但し、ｎ＞ｍ、Ｃ（ｍ）の計算過程にＣ（ｎ－ｍ）が使われない時 のようなルールになると思いますから、再帰的に計算して答えは出せるかも しれません。 検証はしていません。
補足
考えていただいてありがとうございます。 この問題はなかなか難しいようです。 それでもなんとか、 解き方があるのならその解き方（あるごりずむ？） ないのであれば、まだ解けていないのだという確認 が欲しいのです。とはいっても、未解決って訳ではないだろうと思うのですが、、、。
- mirage70
- ベストアンサー率28% (32/111)
るい乗・べき乗の計算ですので、この問題は、 ４７にするために、１，２，括弧、＋、かけ算、できあがった数のみをつかって最小限で作り上げる問題に変わるのではないですか。 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)の考えを繰り返すのみではないですか。
- shige_70
- ベストアンサー率17% (168/946)
#1です。 書いた後で、前記の2条件で計算したところ、47乗が8回にはなりませんでした。 ってことは、やはり間違っていたと。。。 でも、考え方としては的はずれでもない気がするので、もう少し条件を変えてあげると、帰納的に最低回数が算出できる漸化式が作れるのではないでしょうか。。。 うーん、、、やっぱり自信はないです。。。
補足
そのとおり。ですね。下にも書いた通りです。 数学の場合、「自信がない」のではなくて、検証できていません。ですよね。（笑）
- shige_70
- ベストアンサー率17% (168/946)
これは、一般解を出すのはかなり難しそうですね。 少しずつ、考えてみますか? 1は0回、2は1回、3は2回。。。途中まで調べて、以下の予測を立てました。 Claim. 1) nが奇数の時、n乗の時の回数は、(n-1)乗の時のの回数+1 である。 Claim. 2) nが偶数の時、n乗の時の回数は、(n/2)乗の時のの回数+1 である。 この辺が糸口になると思うんですが、、、上記が間違っている可能性も。。。 はっきりいって自信ないですが、どうでしょうか?
補足
そのとおりです。難しい？のですけど、 とっても難しいのか、ある分野の人にとっては簡単なことなのか、あるいは結果があるのか、 そのあたりを教えて欲しいわけです。 例えば、 ｎ＝ａｂ（ただし、ａもｂも２以上）なら、ａ乗の時の回数＋ｂ乗の時の回数 そうではない、つまり、素数の場合は、ｎ－１乗の時の回数＋１ と考えれば良さそうに思いますが、実際のところは、例えばｎ＝３３のときは、 ３３＝３×１１ ３は素数なので、３乗は２乗の回数＋１、つまり２ １１も素数なので、１０乗＋１ １０＝５×２ ５は素数なので、５乗は４乗の回数＋１、つまり３ よって、１１乗の時の回数は５ よって３３乗のときの回数は７回。 となるのですけど、３３＝２の５乗＋１だと考えれば、６回で済みます。 なぜそんな事になるのか。 ３×１１と分けて考えたとき、どちらの場合にも２乗することを計算に入れているからではないでしょうか。 一から考えてそうそう簡単には解決しないようです。
補足
すいません。指数の範囲は「無制限」です。というか、どんな自然数に対しても、求められるようなアルゴリズムの存在を知りたかったのですが、、、どうやら無いようですね。 一生懸命考えていただいてありがとうございました。ツリーで探索ですか。うーん。そうですねえ。それしかないかあ。力業しか無いのでしょう、、、かあ、、、ねえ。きっと。