ttの日記: べきじょう 3
日記 by
tt
世間ではべき乗計算がはやりだそうで(?)。
過去に自分のバカさに泣けたというか自分の限界を知ったのがべき乗計算アルゴリズムであった。 あれは中学生の時だったか、小学生の時だったか…。
x^15=(x^8)*(x^4)*(x^2)*(x)
と計算するとx^8とx^4とx^2の計算で3回、それらとxを掛けるので合計6回の掛け算が必要ですが、
x^15=(x^5)*(x^5)*(x^5)
と計算するとx^5=(x^2)*(x^2)*xの計算で3回、それをさらに2回掛け合わせるのとあわせても5回の掛け算でOk、
というのが不思議でならなかった。そしてこれを一般的な形で実装する(掛け算の回数が最小限となる方法でべき乗を計算する)こともやっぱり出来なかった。たぶん再帰を使ってやればいいんだけどなあ、ぐらいのところで最小の回数であることの証明ができず挫折。ちなみに再帰はOh!PCだったかの記事で読んで学んだんだったと思う。
これを中学の時に同級生に聞いたら、「そんなのあたりまえじゃん」という感じで(今から思うとそうではなかったかもしれない)、いろいろ説明されたんだけど全然理解できず、自分は数学に向いて無いと実感した。ちなみに彼は中学三年の時に数学オリンピック初代日本代表となり、銅メダルを取っていた。
大学に入ってこれが実はグラフ理論という学問だということをはじめて知った。が、やっぱり説明を聞いても理解できず、もちろん単位は落とした。ぁぁょゎょゎ。
ま、そんなのでもプログラムで飯が食える程度には何とかなるということだ。
x^nのnが大きい場合 (スコア:1)
クヌースの本にしっかりいろいろ書いてあったりして。
最適化とかメモ化とか再帰とかが絡んでくるビミョーな話だったりして。
ご存知とは思いますが、奥村晴彦著『C言語による最新アルゴリズム事典』から
ipower()をコピペしておきますね。# アセンブラの入門ページへのリンクどうもありがとうございました。
love && peace && free_software
t-nissie
Re:x^nのnが大きい場合 (スコア:1)
>クヌースの本
たとえばソートでもマージインサートソート(マージソートでもインサートソートでもない)というのが比較回数最小のソートであることが載っていたりしますが、もちろん非実用的なので使われていません。この問題でも乗算回数最小もnが2^500とか2^1000近辺だと(ペアリング暗号の計算で出てきた訳ですが)素因数分解出来ないことの方が多い訳で、多分実用的な解ではないと思います。
と言うのも、xの指数が2^n程度のときどう頑張っても乗算回数はn回程度は必要ですし、ipower()でnの値が悪いときでも2n回程度ですから、ipower()でも最小の2倍以内の回数で済む訳で、この差と2^nの素因数分解では後者の法が一般的には重い計算になります。
未踏でのペアリングアルゴリズムの実装ではこのあたりを担当しましたが、基本はこのipower()と同じ2ベキを中心とした方法で、冗長2進数を用いて(0以外のビットが連続しないように変形して)5ビット単位または7ビット単位で圧縮するwindow法を利用しました。
(別の方法としてはそもそも指数のHamming weightを小さくすると言う方法もありますが、別の要請から我々は指数を選ぶことは出来ませんでした。)
こういう用途の場合には、ジャストで素因数分解する必要もない訳で、指数を適当な羃乗数などの和で表わすことが出来れば速くなるかも知れません(でも上記の通りせいぜい2倍以内です)。
Best regards, でぃーすけ
Re:x^nのnが大きい場合 (スコア:1)
誤: ipower()でnの値が悪いときでも2n回程度
正: ipower()で指数(2^n程度)の値が悪いときでも2n回程度
Best regards, でぃーすけ