【nビット】 Furer 乗算【n log n 2^O(log^* n)】

がいしゅつならすまん、その場合、みんなもっと驚けよ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
あるいは、万一、解析がバグっているというような情報をお持ちでしたら教えてつかあさい。

>>1

shonhage ->　sch\"onhage

すんません

see also:

http://en.wikipedia.org/wiki/Schonhage-Strassen_multiplication

プログラムの技術はム板でやれ。

どっちかというと数学板だと思うけど、どこに建てても盛り上がらなさそうなスレだな
暇な時に読んでみるよ

>>4 気持ちわからんでもないが、\bbb{C}[X]/(X^P+1) とか、
代数の基本を知ってないと難渋するので、どちらかというとここ向けかと。

>>5 ヨロ
俺はまだ、「第一フェーズ」（先入観なしで正しさを確認しにいくのでなく、著者に感情移入して読む）です

（成立してたとして）
改善量としては渋すぎる結果だが、「これがあるべき姿」と思われていたところから更に踏み込んだ
結果なので、出来上がったアルゴリズムはもちろんのこと、その構成とかに習うべき点が多くあると
おもふ

>>1
あぁそういえばSTOC 2007の採録論文リストでタイトル見つけてびっくりして論文探しに行ったなぁ．
手元にはあるんだがまだ読んでなかったよ．って丁度昨日STOC終わったところだな．参加してないけど．
まぁ読むことがあったらまた書き込むわ．

>>7 また会おうぞノシ

雰囲気わかってきたんだけど、複素数に行って戻ってくるところで、これで精度十分というのがまだわからん

複素数でだめなら、俺なら四元数とかには手を出したくないからそのままゴリ押しするけどな。

>>9 いや有理数体の適当な円分拡大かその整数環でたりるとおもいますが、問題は実部虚部の近似値を持つより効率よく行く表し方蛾あるかどうかでげす。 1のべき根が正しく機能するようにすれば正標数ですら行けるのかも。　精度めんどい

コレって実用上意味あるの？

スラッシュドットにはまだ流れてないな、
ブログでチラッと書いてる人はいるが

>>11
「それは文明の程度による」とニヒルに決めたいところだが、
正直には O( ) の中に何が隠れているかを数えないとわかりまへん

損益分岐点が今の文明にとっては大きすぎたとしても、
「マインスイーパ」で無理と思っていた場所が開いたところで、
ここを軸にいろいろできるかも、というのをひそかに期待

ものすごい個人的な感想というかアレなんだが
ＦＦＴってオーパーツみたいに感じるんだよね

オーパーツ：「場違いな工芸品」、「時代錯誤遺物」

FFTって高速フーリエ変換の事だよな？別にパソコンもあるんだし、時代にそぐわないものではないような気がするんだが。

量子コンピュータが完成する前に量子コンピュータ用のアルゴリズムを考えちゃう人

人工知能が完成する前に人工知能との対話を妄想してﾊｧﾊｧする人

>>17
あるあるｗｗｗｗｗ

>>16
あるあ・・・・・・ねーよｗｗｗｗｗ

>>18
釣れます？

最近成功したShorのアルゴリズムで因数分解することに成功したっていうけど
あれって別に3*5=15よりもっと巨大な数でも因数分解できるんですよね？

量子コンピュータ用のアルゴリズムは研究されてるだろ

それを理解できる段階にいるというだけでうらやましい
量子コンピュータシミュレータなんてソフトがあるんですね

>>20
13bit程度の数までならいけるらしい。（埼玉大オープンキャンパスにて訊いた）

2=√4

25=5^2

26 = 2 * P( 2 * P(2) )
ただしP(n):n番目の素数

27=3^3

面倒な実装のオーバーヘッドを考えてメリットあるの？

k=φ(φ(φ(φ(φ(φ(n))))))

>>29
入力した殆どの値が0になりそうだな。φ(1)=φ(0)=0なら。

839

保守

変換・逆変換のオーバーヘッドを除けば
足し算・引き算・掛け算にかかるオーダーがn:桁数としてO(n)になりそうなアルゴリズムが
[DONALD E. KNUTH]のあの本の第2巻の第4章3の2に載ってたりするがアレは実際どうなのよ？
今手元に英語版しかない関係上適当に和訳して書いておくが。

変換:O(logn)
1.二つの巨大数をu,vと置く。
2.互いに素である数の集合を{m(1),m(2),...,m(n)}と置く。
3.u及びvをm(1),m(2),...,m(n)で割った余りを数列U<u(1),u(2),...,u(n)>及びV<v(1),v(2),...,v(n)>とする。

演算:O(n)
U+V=<(u(1)+v(1)) mod m(1),(u(2)+v(2)) mod m(2),...,(u(n)+v(n)) mod m(n)>
U-V=<(u(1)-v(1)) mod m(1),(u(2)-v(2)) mod m(2),...,(u(n)-v(n)) mod m(n)>
U*V=<(u(1)*v(1)) mod m(1),(u(2)*v(2)) mod m(2),...,(u(n)*v(n)) mod m(n)>

逆変換:多分O(nlogn)
M(j)≡1(mod m(j))で、かつM(j)≡0(mod m(k)) for k≠jを成り立たせる数M(j)を定める。
M(j)の具体的な値は、m=m(1)*m(2)*...*m(n)とし、オイラーのファイ関数をφ(n)とするときに
M(j)=((m/m(j))^φ(m(j))) mod m
このとき、u=(u(1)*M(1)+u(2)*M(2)+...+u(n)*M(n)) mod m

やばい、オーダーの算出ミスった。
よく考えたら全部O(n)じゃないかこれ。

910

age

>>9 >>10
STOC08 のプログラム見て遅ればせながら知ったのだが、複素数を外すのは大分前（１月頃）に
できていたらしい。

http://arxiv.org/abs/0801.1416

Fast Integer Multiplication using Modular Arithmetic
Authors: Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi
(Submitted on 9 Jan 2008 (v1), last revised 6 May 2008 (this version, v2))

体でなく、Z[X]/(p^c, X^m+1) のような1の根をもったring を使うとのこと。

リソースは有限なのに漸近的計算量を考えることにどんな意味があるの？

膨大な計算量の速やかな有効数字特定

>>38
大抵、実用レベルになってくる100桁くらいになったらかなりいい値に近似出来てるから。

100桁までの計算にかかる実測時間から200桁までの計算にかかる予想時間を近似的に求める事には意味があると思う。

780