乗算回数について

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

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

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

No.1 ベストアンサー 回答者： liar_adan 回答日時： 2003/04/22 00:11

私も8回でできました。

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

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

この回答へのお礼

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

お礼日時：2003/04/22 00:15

No.2 回答者： ticky 回答日時： 2003/04/22 01:20

たぶん８回かな。

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

この回答へのお礼

有難うございます。

お礼日時：2003/04/22 18:21