402コメント176KB

　　　最速の素数判定アルゴリズム　　

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

0001　刺身定食

NGNG

最速のアルゴリズムはRabinの定理を使ったものと聞き、
文献を読んでみたのですが、サッパリわかりません。
日本で完璧に理解している方、たまたまこのスレ
見ていたら、ついでに教えてください。
マジです。

0352340

NGNG

>log(2)*8*2^32 = 10343311891.9
>わずか10G桁=１００億桁
なるほど，ミスったよ
1G=1000MByte=1000*1000KByte=1000*1000*1000Byte=1000*1000*1000*8bit
=10^9
でもって
表現可能な数字＝2^(10^9)
ってわけか
で、こいつのlog10をとるのか・・・
そうすると，大体一桁落ちて
数千万桁
あれ，どっかで計算ミスってる？

まあ高速なアルゴリズムよりも
高速な分散処理を考えないと普通に無理だよね
分散って言っても，一つの数値の判定を分散処理する
数学板から誰か連れてきてよ
でもって作る？
通信するので、言語は何でもありですね。
まあ、C++ですかね。

0353デフォルトの名無しさん

NGNG

>>349
手元にあるWindows2000 RC2の説明によると、ProfessionalとServerは4GB、
Advanced Serverは8GBまでサポートしてるよ。

素数関係ないのでsage

0354仕様書無しさん

NGNG

>>352
でもな～、素数の判定にロハで協力すれ、って言って、人が集まるのかな。
SETI と比べてジミかつマニアック過ぎると思われ。
100万桁の自然数ひとつ判定するのに、どれくらいの台数のマシンが必要
なんだろか。
一つの数の判定するのにかけていい時間を1日くらいと考えると･･････
数十万台はいるんじゃなかろうか。

0355デフォルトの名無しさん

NGNG

>>354
かっこいいスクリーンセーバー作って、裏で勝手に計算しちゃえよ（笑

0356仕様書無しさん

NGNG

>>354
自己複製機能と感染機能を実装すれば大丈夫かと。

0357

NGNG

nimbda改造すればすぐできそうだNE!

0358デフォルトの名無しさん

NGNG

>>334
>「素数判定はエラトステネスの篩」っつー結論

デマを撒くな～

>>25
の確率性アルゴリズムを使うか、
特定の構造をもった数に対する検証のどちらかしかないぞ。

スレのテーマが「最速で素数表を作る」ってなら櫛で間違いないけど。

0359336

NGNG

>>352　log10(256)が2.4だからバイト数のおよそ2.5倍ね

4Gバイトなら10G桁表現出来るって事ね

0360デフォルトの名無しさん

NGNG

39番目のメルセンヌ素数が見つかったらしいな。
インターネット上のPCの共同作業で。
http://mersenne.org/status.htm

0361デフォルトの名無しさん

NGNG

オンメモリじゃなきゃもっと行くでしょ？
遠いネットワークの先にあるメモリーよりも先に地元のディスク使わないの？

0362デフォルトの名無しさん

NGNG

1億までの素数リストを出すのに約20秒かかった。
10億までなら200秒かなとか単純に思ったら、すんげえ時間かかる。
ハードディスクがガリガリ言ってるし。
10億でもたったの10桁・・・素数計算って大変だねー。

0363デフォルトの名無しさん

NGNG

>>360
うわ。見逃していました。すげーニュースだ。
まだ検証中（ダブルチェック中）なんだね。
M38 が (2^6972593) - 1 で M39 が 8000000 以上ってことだから
かなりの値だ。

0364デフォルトの名無しさん

NGNG

>>1
なに、Ladinの定理?

0365デフォルトの名無しさん

NGNG

よくわからんが１０進数で何桁だ？

0366デフォルトの名無しさん

NGNG

2^8000000くらいなら10進で2408240桁くらいだろう。

0367デフォルトの名無しさん

NGNG

>>361
１Gのデータをハードディスクから読み出すのにどれくらいかかると思ってるん
だか・・・・

0368デフォルトの名無しさん

NGNG

うちのマシンには12ディスクのRAID(FC-AL)が8並列で付いてるので
1GBの読み込み1.3秒ですが何か？

0369デフォルトの名無しさん

NGNG

PCIバスの帯域は32bit,33MHzだと133MB/secですが何か？
(64bit,66MHzで533MB/sec)

0370デフォルトの名無しさん

NGNG

そんな安いバス使ってませんが何か？

0371デフォルトの名無しさん

NGNG

crc

0372　

NGNG

最大の素数発見！ 13万人で検算中。
http://news.2ch.net/test/read.cgi/newsplus/1007792330/l50

0373　

NGNG

あ、検算済みでした。

0374デフォルトの名無しさん

NGNG

age

0375デフォルトの名無しさん

NGNG

>>64
できました。
http://www.research.ibm.com/resources/news/20011219_quantum.shtml

0376デフォルトの名無しさん

NGNG

>>64 >>375
こっちのほうが見やすいと思われ。
http://slashdot.jp/article.pl?sid=01/12/20/155216&mode=nested

0377デフォルトの名無しさん

NGNG

/*素数のlucas判定のプログラム作ってみました。
　C言語による最新アルゴリズム辞典の改造しただけだけどどうでしょう？*/
#define N 4000
int prime(unsigned int p)
{
unsigned int h, i, j, k, s,cash,cash2;
char a[N+1],x[N];
memset(a,0,p);
a[2] = 1; /* a = 4 */
for (k = 2; k < p; k++)
{
memcpy(x,a,p);
memset(a,1,p);

a[1] = 0; /* a = -2 mod M_p */
for (i = 0; i < p; i++)
{
if (x[i])
{
s = 0;
cash=p-(h=i)-1;
for (j = 0; j < cash; j++)
{
s = (s >> 1) + a[h] + x[j];
a[h++] = s & 1;
}
{
s = (s >> 1) + a[h] + x[j];
a[h++] = s & 1;
h -= p;
}
for (j++; j < p; j++)
{
s = (s >> 1) + a[h] + x[j];
a[h++] = s & 1;
}
if (s > 1)
{
cash2=h;
for(j=0;a[h]&&j<cash;j++) h++;
if(a[h])
{
h++;
memset(a+cash2,0,h-cash2);
cash2=0;
h -= p;
while(a[h]) h++;
}
memset(a+cash2,0,h-cash2);
a[h] = 1;
}
}
}
}
a[p] = 1 - a[0]; /* 番人 */
i = 1;
while (a[i] == a[0]) i++;
return (i == p);
}

0378デフォルトの名無しさん

NGNG

素数を見つけるよりもロト６の１等の番号の組み合わせの方が知りたい
とフト思ってしまった

0379素数が理解出来ない技術者

NGNG

　エラトステネスの篩を使用して、ゴールドバッハ（ゴルトバッハ）の予想を、
1億までエクセルのＶＢＡで計算しましたが、実行時間は、約２０時間、反例は
見つかりませんでした。
　これって、結構早いのでしょうか？
　ちなみにマシンは、ＶＡＩＯのPCG-FX55/XPで、メモリーは６４ＭＢ。
　なお、ゴールドバッハの予想を知らない方への説明。
　全ての偶数は、２個の素数の和で表される。
　そこで、ある制限をかけて、いかなる偶数の平方根の２倍＋１よりも大きい
素数と、その他の素数の和となることは無いと予想したのですが、果たして反
例は見つかったか？結果は？
　興味のある方は、掲示板に書きこんで頂けば、マクロが入ったエクセルのソ
フトの配置してあるＵＲＬを書き込みます。
　なお、今のところ、私のエラトステネスの篩は、１００万の計算に１２秒かか
りますので、まだ改善の余地有り。
　なお、定義に従えば、１００万の計算に８日かかります。

0380デフォルトの名無しさん

NGNG

ところで、ある程度以上大きくて2^n-1以外の素数ってあるの？
ある程度ていうのも、へんな言い方だけど…

0381デフォルトの名無しさん

NGNG

＞379
VBで実行してみたいです。

0382デフォルトの名無しさん

NGNG

>>380　素数は Aの付近に 1/log(A)程度の頻度でありますよ
log(2^n-1)はおよそlog(2)*Nだから　2^n-1～2^(n+1)の間にも0.7*n個程度あるという事

0383380

NGNG

>>382　さんきゅ。

0384デフォルトの名無しさん

NGNG

×　だから　2^n-1～2^(n+1)の間にも0.7*n個程度あるという事
○　だから　2^n-1～2^(n+1)の間にも(2^n)/(0.7*n)個程度あるという事

0385デフォルトの名無しさん

NGNG

　ＦＦＴではなぜ、ビット反転操作をするんですか?教えてください。

0386デフォルトの名無しさん

NGNG

刺身定食くいたくなった…

0387デフォルトの名無しさん

NGNG

>>385
ここ参考にするといいでしょ
http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/

特にこの絵
http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/fig_bf2.gif

最後にビット反転置換をしなくても良い方法もあるけど、
　すると毎回複製が必要になるのと、ループが少し複雑になるから
メモリの節約になるこの方法が好まれているのでしょう

0388デフォルトの名無しさん

NGNG

ありがとうございました＞387

0389デフォルトの名無しさん

NGNG

確率的判定法(Rabin)の計算量オーダーはlog(n)なのは知ってるけど
確定的判定法で最速の物ってどれよ？
ecppだっけ？あれはどれぐらいのオーダー？

0390デフォルトの名無しさん

NGNG

>>389　なんでsageで聞いたの？

0391デフォルトの名無しさん

NGNG

俺も知りたいage

0392デフォルトの名無しさん

NGNG

あげ

0393デフォルトの名無しさん

NGNG

あげ

0394デフォルトの名無しさん

NGNG

確率的判定法って　単に何度か割ってみて割り切れなかったらと変わりないように思うのだが？

例えば1万個の素数を用意しといて割ってみて割り切れなかったら　素数でない確率は1万分とか

0395デフォルトの名無しさん

NGNG

>>394
オオバカ

0396デフォルトの名無しさん

NGNG

>>394 確かにそうだけど、それだと1桁確度を改善しようとすると、判定時間も１桁増になってしまう

Rabinの方法は、対数和にしかならない

0397デフォルトの名無しさん

NGNG

保存

0398デフォルトの名無しさん

NGNG

ぷろろｒぐ

0399デフォルトの名無しさん

NGNG

素人でよくわからんのですが
テーブルを分解・圧縮して計算に使う部分をなるべくキャッシュに載るようにして
レジスタも使って（速度の桁が違うので）
2の倍数乗除にシフト、（プロセッサ内で勝手にシフトに切り替わるかな？^^;）
遅い割り算を逆数掛け算にしたりとかは効果ないんでしょうか？

0400デフォルトの名無しさん

NGNG

倍数→累乗　マチガえました(笑
大規模３Ｄレンダリングなどで使う
クラスタリングが分散にいいらしいです

0401デフォルトの名無しさん

NGNG

>>399　小手先のテクニックは　同じ計算時間で　計算出来る数が少し増えるだけ
　並列計算も、完全に成功しても台数分　数が増えるだけ
　それは頑張って１０台並列でももたった１桁増えるかどうかのレベル

　掛算をFFTにしたような、一挙に桁数を倍に出来るようなアイデアが求められている

0402デフォルトの名無しさん

NGNG

32bitMAXなら計算済みのを展開して2分探索すればあっという間だね

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