41コメント12KB

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

■ このスレッドは過去ログ倉庫に格納されています

0001１３２人目の素数さん

2007/06/12(火) 19:19:10

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

0002１３２人目の素数さん

2007/06/12(火) 19:30:19

>>1

shonhage ->　sch\"onhage

すんません

0003１３２人目の素数さん

2007/06/12(火) 19:31:43

0004１３２人目の素数さん

2007/06/13(水) 21:14:04

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

0005１３２人目の素数さん

2007/06/13(水) 22:44:19

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

00061

2007/06/14(木) 05:32:10

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

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

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

0007１３２人目の素数さん

2007/06/14(木) 09:38:57

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

0008１３２人目の素数さん

2007/06/14(木) 19:23:15

>>7 また会おうぞノシ

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

0009１３２人目の素数さん

2007/06/17(日) 12:20:01

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

0010１３２人目の素数さん

2007/06/18(月) 11:54:13

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

0011１３２人目の素数さん

2007/06/18(月) 16:43:53

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

0012１３２人目の素数さん

2007/06/18(月) 16:50:15

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

0013１３２人目の素数さん

2007/06/18(月) 20:31:56

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

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

0014１３２人目の素数さん

2007/06/18(月) 20:33:44

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

0015１３２人目の素数さん

2007/06/18(月) 23:04:17

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

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

0016１３２人目の素数さん

2007/06/20(水) 16:20:40

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

0017１３２人目の素数さん

2007/06/20(水) 17:25:18

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

0018１３２人目の素数さん

2007/06/20(水) 20:56:38

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

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

0019P Shor

2007/06/20(水) 22:48:27

>>18
釣れます？

0020１３２人目の素数さん

2007/06/21(木) 11:21:47

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

0021１３２人目の素数さん

2007/06/21(木) 18:48:38

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

0022１３２人目の素数さん

2007/06/25(月) 15:28:42

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

0023１３２人目の素数さん

2007/08/26(日) 22:31:33

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

002424

2007/08/26(日) 23:21:50

2=√4

0025１３２人目の素数さん

2007/08/27(月) 02:04:10

25=5^2

0026１３２人目の素数さん

2007/08/31(金) 20:19:13

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

002727

2007/08/31(金) 20:20:29

27=3^3

0028１３２人目の素数さん

2007/08/31(金) 20:41:23

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

0029１３２人目の素数さん

2007/08/31(金) 21:05:09

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

0030１３２人目の素数さん

2007/09/02(日) 18:28:19

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

0031１３２人目の素数さん

2007/10/30(火) 12:24:34

839

0032１３２人目の素数さん

2008/01/19(土) 22:30:39

保守

0033１３２人目の素数さん

2008/02/28(木) 20:19:43

変換・逆変換のオーバーヘッドを除けば
足し算・引き算・掛け算にかかるオーダーが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

003433

2008/02/28(木) 20:22:38

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

0035１３２人目の素数さん

2008/04/10(木) 10:49:34

910

0036１３２人目の素数さん

2008/04/11(金) 04:14:45

age

0037１３２人目の素数さん

2008/05/15(木) 20:38:34

>>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 を使うとのこと。

0038１３２人目の素数さん

2008/05/15(木) 21:33:23

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

0039１３２人目の素数さん

2008/05/16(金) 01:26:44

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

0040１３２人目の素数さん

2008/06/27(金) 19:44:19

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

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

0041１３２人目の素数さん

2008/08/11(月) 19:27:26

780

■ このスレッドは過去ログ倉庫に格納されています