べき乗

質問

大学のレポート課題ですが、自然数m, nで、mのn乗を求める効率の良いプログラムを考えています。

ヒントには、「n=64であれば6回の乗算で計算できる」とあります。

n=64のとき、乗算6回で計算するプログラムは出来ましたが、nの値を変えると間違った答えが出ますし、それを考慮して作ったプログラムもnの値によって正解だったり、不正解だったりします。

いくつも考えますたが、どれもそんな状況なので質問させていただきました。分かった方はどうか教えてください。
（回答は、出来る限りJAVAかCでお願いします。）

回答No.5

hrm_mmm · ベストアンサー

理論は既に述べられているので、具体化をすると
n=7 のとき
m^7 = m^( 2*2 +2 +1)
= (m^2)^2 * m^2 * m
= (m*m)^2 * (m*m) * m

あとは推して知るべし。
効率化の前に、2乗から15乗くらいまで、上記を全部自分の手で書いてみるといいです（手計算もするならなおよい）。
「エディターならコピーペーストですむのに」と思ったところを変数に入れて使い回す。
「同じ事繰り返してる」と思ったら、ループに入れる。
これで、アルゴリズムが見えてきませんか？

お礼

皆さん、ありがとうございます。
完成とまでは行っていませんが、自分のプログラムのまずかった点と、方法の検討がつきました。

回答No.4

rouden

ヒントから推測すれば、変数「n」を素因数分解して、その値でべき乗していけばよさそうな気がします。

参考URLのプログラムを(少し改造してから)利用して、変数「n」の値を素因数分解して、その分解したごとに出てきた値を変数「m」にべき乗していくプログラムを作れば良いです。

参考URL：

http://next1.cc.it-hiroshima.ac.jp/C/C-program.html#素因数分解

回答No.3

BLUEPIXY

#2でいう倍々は
m→m*m→(前の計算の結果:m^2)*(m^2)→(m^4)*(m^4)…
の意味です。

回答No.2

BLUEPIXY

ｎを２進数で表して、
最下位のビットをｍそのままとして
倍々していく
その過程で、ビットの立っているものを全部掛けていく。
というようなものでいいんじゃないでしょうか
実際のプログラムを書くことは、ＯＫＷａｖｅの規約違反になり削除されると思いますので、まずは、プログラムをお書き下さい。

回答No.1

noname#21649

今の大学で名に教えているやら。
これは.高校数学Iの内容。
m**64=(m**32)**2=((m**16)**2)**2=....
で答えね。因数分解(中学校でやってますね)を使ってm**iのiを求めて.m**iを既に求めた結果から使うことが基本。

CもJAVAも知らないからFotran。因数分解はどこかの教授が３０年くらい前に報告を書いているのでこの報告をみて。