【nビット】 Furer 乗算【n log n 2^O(log^* n)】
1 ：１３２人目の素数さん：
がいしゅつならすまん、その場合、みんなもっと驚けよw
みんな掛け算計算するだろう
n ビットの数を２個掛ける時、２進数で筆算すると、
大体 n^2 個位 0や1 を書くことになり、n^2 くらいのビット演算を要する。
Shonhage と Strassen のアルゴリズムは高速 Fourier 変換の利用という
画期的アイデアでこれを O(n log n log log n) で行い、漸近的計算量で
長くチャンピオンとして語り継がれてきた。
Martin F\”urer は、これを n log n 2^O(log^* n) で出来ると発表した。
log^* は log の任意定数回の合成で、 *=3 にとると 2^{log log log n} = log log n
となる。（対数の底は、Oつきならどうでもいいがとりあえず 2 とした)
http://www.cse.psu.edu/~furer/
にある Faster integer multiplication
クリビツ
乗算という基本的演算について３５年ぶり？のオーダー改良。
アルゴリズムの教科書という教科書は、改訂の折にこのストーリーを
盛り込むことになるだろう
See also:
http://portal.acm.org/citation.cfm?id=1250790.1250800&coll=ACM&dl=ACM&type=series&idx=1250790&part=Proceedings&WantType=Proceedings&title=Annual%20ACM%20Symposium%20on%20Theory%20of%20Computing&CFID=25333501&CFTOKEN=39584821
あるいは、万一、解析がバグっているというような情報をお持ちでしたら教えてつかあさい。
みんな掛け算計算するだろう
n ビットの数を２個掛ける時、２進数で筆算すると、
大体 n^2 個位 0や1 を書くことになり、n^2 くらいのビット演算を要する。
Shonhage と Strassen のアルゴリズムは高速 Fourier 変換の利用という
画期的アイデアでこれを O(n log n log log n) で行い、漸近的計算量で
長くチャンピオンとして語り継がれてきた。
Martin F\”urer は、これを n log n 2^O(log^* n) で出来ると発表した。
log^* は log の任意定数回の合成で、 *=3 にとると 2^{log log log n} = log log n
となる。（対数の底は、Oつきならどうでもいいがとりあえず 2 とした)
http://www.cse.psu.edu/~furer/
にある Faster integer multiplication
クリビツ
乗算という基本的演算について３５年ぶり？のオーダー改良。
アルゴリズムの教科書という教科書は、改訂の折にこのストーリーを
盛り込むことになるだろう
See also:
http://portal.acm.org/citation.cfm?id=1250790.1250800&coll=ACM&dl=ACM&type=series&idx=1250790&part=Proceedings&WantType=Proceedings&title=Annual%20ACM%20Symposium%20on%20Theory%20of%20Computing&CFID=25333501&CFTOKEN=39584821
あるいは、万一、解析がバグっているというような情報をお持ちでしたら教えてつかあさい。
|
|
|
2 ：１３２人目の素数さん：2007/06/12(火) 19:30:19