乗算回数

質問

べき乗の乗算回数をプログラミングしたいのですが、
わかりません。どうやってプログラミングしたらよいですか。
時間がなくて困っています。教えてください。お願いします。

回答No.4

arrysthmia

不規則に少ない回数で実現できるヤツがあるから、
一般論にするのは難しいです。

x2 = x * x;
x4 = x2 * x2;
x8 = x4 * x4;
x16 = x8 * x8;
x32 = x16 * x16;
x64 = x32 * x32;
x119 = x64 * x32 * x16 * x4 * x2 * x;
の 11 回に比べて、

x2 = x * x;
x4 = x2 * x2;
x7 = x4 * x2 * x;
x14 = x7 * x7;
x28 = x14 * x14;
x56 = x28 * x28;
x112 = x56 * x56;
x119 = x112 * x7;
の 9 回とか。

人工知能レベルのプログラムになりますね。

回答No.3

noname#94461

x^(1,2,4,8,16,32) の時に　0,1,2,3,4,5 回の乗算で計算する...といったことを考えられているのですね?
ans=x^countを求める場合、
if (count.and.1)
ans = x;
else
ans = 1.0;
count = count>>1;
xpower = x;
while (count>0) {
xpower=x*x;
if (count.and.1)
ans = ans * xpower;
xpower = xpower*xpower;
count = count>>1;
}
以上のような形で求まると思います。

回答No.2

nagi_szn

不勉強なら本でも読んで勉強してください。

何かよく分かりませんが、さっき書いたのにちょっと加えればできると思います。
最小値ってことは、何回も計算させその都度乗算回数を求めるってことですかね。
その、その都度の乗算階数はさっき書いたcounterで保持し、新たなカウンターmincounterとかを作って、その計算の都度、if文でmincounterとcounterの小さい方を取ってやればいいはずです。

回答No.1

nagi_szn

カウンターを用意すればよいです。
c言語なら
int couter=0;
を用意して、
べき乗を計算するfor文やwhile文の最後に
counter++;
を付ければいいです。

補足

すみません、不勉強でよくわかりません。
もう少し詳しく説明してもらってもいいですか。

それと質問に書き忘れてしまったので追加します。
求めるのは最小の乗算回数です。ただ個別に最適化する必要は
ないです。すみません。