乗算回数について

質問

至急教えてください。
「X^100の乗算回数は普通に計算すると99回である。
どのくらい乗算回数を減らせるか？」
という問題があります。

私の知り合いの答えでは18回で答えが出るのですが、
私が計算すると8回で答えが出ます。

問題文は「」の中だけです。
私の答えは合ってますか？
大至急教えてください。おねがいします。

回答No.1

liar_adan · ベストアンサー

私も8回でできました。
具体的には書きませんが、複数の経路があるようです。

7回以上必要なことはすぐに証明できます。
2^6 = 64だから、6回ではどうがんばっても64乗止まり。
たぶん8回で正解だと思いますが…。

お礼

回答有難うございました。
とても参考になりましたし、安心しました。

回答No.2

ticky

たぶん８回かな。

というのは、100を２進数であらわすと、
1100100になり、
X^100＝x^2^2^2^2^2^2*x^2^2*x^2^2^2^2^2
で、xをどんどん自乗することを６回繰り返した後、
途中で出てくるxの繰り返し自乗を５回繰り返した数と、２回繰り返した数をかければいいのです。

お礼

有難うございます。