さて、多倍精度整数の乗算ですが、現状では単純な平方による古典的乗算（2n^2）、Karatsuba法の再帰的適用（O(n^(log 3))）、Schönhage and Strassen (1971), Schönhage(1977), Cantor and Kaltofen (1991)のFFTによるアルゴリズム（O(n log n log log n)）が一般的な様です。
ただしO記法で見かけ上のオーダーが低く見積もれると言ってもアルゴリズムは複雑になる傾向にあり、コストが極端なものにならない限り単純な古典的方法やKaratsuba法が処理速度が有利な場合があります。
波束エンジニアリングに関してはよく分かりませんが、今回の記事を見る限り複雑な処理もより低コストに実装できるようになり、昔から知られていた単純なものと、オーダーは低いが複雑で遅いものとの差が一層小さくなるのではないでしょうか。
フーリエ変換速いと (スコア:0)
桁数が多い処理解くのに便利そうだなー
素数探査とか暗号解読に使えるんじゃね？
Re:フーリエ変換速いと (スコア:1)
変換結果を何百桁の精度で得られる訳じゃないと思うので、暗号解読にどれほど役に立つのか疑問です。
偉い人、教えてください!
Re: (スコア:0)
超高速エンコーダボードとか出ないかな。
Re:フーリエ変換速いと (スコア:1)
もちろん、動画関連(不可逆変換)への応用は期待しています。
ですが、暗号解読にはどの程度役に立つのかなぁ、と思ったのです。
Re: (スコア:0)
GNUMPなんかにも使われていたと思います．
そういうわけで，大きい整数を扱う公開鍵暗号や，それに関連した素因数分解は
速くなるんじゃないでしょうか．
どうやって精度保証をしているのかは，理論があるらしいですが，
詳しくは知りません．
Re:フーリエ変換速いと (スコア:1, 参考になる)
>詳しくは知りません．
FFTによる乗算の利用と精度の保障についてはPeter Henriciによる著ISBN-13: 978-0471608417にきっちりと書かれていたはずです。
（私も大分昔に読んだので具体的になんだったか良く覚えていませんが＾＾；）
さて、多倍精度整数の乗算ですが、現状では単純な平方による古典的乗算（2n^2）、Karatsuba法の再帰的適用（O(n^(log 3))）、Schönhage and Strassen (1971), Schönhage(1977), Cantor and Kaltofen (1991)のFFTによるアルゴリズム（O(n log n log log n)）が一般的な様です。
ただしO記法で見かけ上のオーダーが低く見積もれると言ってもアルゴリズムは複雑になる傾向にあり、コストが極端なものにならない限り単純な古典的方法やKaratsuba法が処理速度が有利な場合があります。
波束エンジニアリングに関してはよく分かりませんが、今回の記事を見る限り複雑な処理もより低コストに実装できるようになり、昔から知られていた単純なものと、オーダーは低いが複雑で遅いものとの差が一層小さくなるのではないでしょうか。
Re: (スコア:0)
ビット数を増やすとレーザー装置もたくさん要る
というオチ？