最速の素数判定アルゴリズム
353 ：デフォルトの名無しさん：01/11/19 04:40
>>349
手元にあるWindows2000 RC2の説明によると、ProfessionalとServerは4GB、
Advanced Serverは8GBまでサポートしてるよ。
素数関係ないのでsage
手元にあるWindows2000 RC2の説明によると、ProfessionalとServerは4GB、
Advanced Serverは8GBまでサポートしてるよ。
素数関係ないのでsage
>>352
でもな〜、素数の判定にロハで協力すれ、って言って、人が集まるのかな。
SETI と比べてジミかつマニアック過ぎると思われ。
100万桁の自然数ひとつ判定するのに、どれくらいの台数のマシンが必要
なんだろか。
一つの数の判定するのにかけていい時間を1日くらいと考えると･･････
数十万台はいるんじゃなかろうか。
でもな〜、素数の判定にロハで協力すれ、って言って、人が集まるのかな。
SETI と比べてジミかつマニアック過ぎると思われ。
100万桁の自然数ひとつ判定するのに、どれくらいの台数のマシンが必要
なんだろか。
一つの数の判定するのにかけていい時間を1日くらいと考えると･･････
数十万台はいるんじゃなかろうか。
355 ：デフォルトの名無しさん：01/11/19 07:48
>>354
かっこいいスクリーンセーバー作って、裏で勝手に計算しちゃえよ（笑
かっこいいスクリーンセーバー作って、裏で勝手に計算しちゃえよ（笑
>>354
自己複製機能と感染機能を実装すれば大丈夫かと。
自己複製機能と感染機能を実装すれば大丈夫かと。
357 ： ：01/11/19 08:23
nimbda改造すればすぐできそうだNE!
358 ：デフォルトの名無しさん：01/11/19 12:30
>>334
>「素数判定はエラトステネスの篩」っつー結論
デマを撒くな〜
>>25
の確率性アルゴリズムを使うか、
特定の構造をもった数に対する検証のどちらかしかないぞ。
スレのテーマが「最速で素数表を作る」ってなら櫛で間違いないけど。
>「素数判定はエラトステネスの篩」っつー結論
デマを撒くな〜
>>25
の確率性アルゴリズムを使うか、
特定の構造をもった数に対する検証のどちらかしかないぞ。
スレのテーマが「最速で素数表を作る」ってなら櫛で間違いないけど。
359 ：336：01/11/19 12:54
360 ：デフォルトの名無しさん：01/11/20 02:33
361 ：デフォルトの名無しさん：01/11/21 22:17
オンメモリじゃなきゃもっと行くでしょ？
遠いネットワークの先にあるメモリーよりも先に地元のディスク使わないの？
遠いネットワークの先にあるメモリーよりも先に地元のディスク使わないの？
362 ：デフォルトの名無しさん：01/11/21 23:51
1億までの素数リストを出すのに約20秒かかった。
10億までなら200秒かなとか単純に思ったら、すんげえ時間かかる。
ハードディスクがガリガリ言ってるし。
10億でもたったの10桁・・・素数計算って大変だねー。
10億までなら200秒かなとか単純に思ったら、すんげえ時間かかる。
ハードディスクがガリガリ言ってるし。
10億でもたったの10桁・・・素数計算って大変だねー。
363 ：デフォルトの名無しさん：01/11/22 00:16
>>360
うわ。見逃していました。すげーニュースだ。
まだ検証中（ダブルチェック中）なんだね。
M38 が (2^6972593) - 1 で M39 が 8000000 以上ってことだから
かなりの値だ。
うわ。見逃していました。すげーニュースだ。
まだ検証中（ダブルチェック中）なんだね。
M38 が (2^6972593) - 1 で M39 が 8000000 以上ってことだから
かなりの値だ。
364 ：デフォルトの名無しさん：01/11/22 00:24
>>1
なに、Ladinの定理?
なに、Ladinの定理?
365 ：デフォルトの名無しさん：01/11/22 01:11
よくわからんが１０進数で何桁だ？
366 ：デフォルトの名無しさん：01/11/22 02:11
2^8000000くらいなら10進で2408240桁くらいだろう。
367 ：デフォルトの名無しさん：01/11/23 22:56
368 ：デフォルトの名無しさん：01/11/24 14:59
うちのマシンには12ディスクのRAID(FC-AL)が8並列で付いてるので
1GBの読み込み1.3秒ですが何か？
1GBの読み込み1.3秒ですが何か？
369 ：デフォルトの名無しさん：01/11/24 19:16
PCIバスの帯域は32bit,33MHzだと133MB/secですが何か？
(64bit,66MHzで533MB/sec)
(64bit,66MHzで533MB/sec)
370 ：デフォルトの名無しさん：01/11/25 04:40
そんな安いバス使ってませんが何か？
371 ：デフォルトの名無しさん：01/11/29 23:20
crc
372 ： ：01/12/10 12:01
最大の素数発見！ 13万人で検算中。
http://news.2ch.net/test/read.cgi/newsplus/1007792330/l50
http://news.2ch.net/test/read.cgi/newsplus/1007792330/l50
373 ： ：01/12/10 12:03
あ、検算済みでした。
374 ：デフォルトの名無しさん：01/12/20 02:53
age
375 ：デフォルトの名無しさん：01/12/21 01:33
376 ：デフォルトの名無しさん：01/12/21 02:38
377 ：デフォルトの名無しさん：01/12/30 13:40
/*素数の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);
}
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);
}
378 ：デフォルトの名無しさん：02/01/09 07:16
素数を見つけるよりもロト６の１等の番号の組み合わせの方が知りたい
とフト思ってしまった
とフト思ってしまった
379 ：素数が理解出来ない技術者：02/01/30 03:37
エラトステネスの篩を使用して、ゴールドバッハ（ゴルトバッハ）の予想を、
1億までエクセルのＶＢＡで計算しましたが、実行時間は、約２０時間、反例は
見つかりませんでした。
これって、結構早いのでしょうか？
ちなみにマシンは、ＶＡＩＯのPCG-FX55/XPで、メモリーは６４ＭＢ。
なお、ゴールドバッハの予想を知らない方への説明。
全ての偶数は、２個の素数の和で表される。
そこで、ある制限をかけて、いかなる偶数の平方根の２倍＋１よりも大きい
素数と、その他の素数の和となることは無いと予想したのですが、果たして反
例は見つかったか？結果は？
興味のある方は、掲示板に書きこんで頂けば、マクロが入ったエクセルのソ
フトの配置してあるＵＲＬを書き込みます。
なお、今のところ、私のエラトステネスの篩は、１００万の計算に１２秒かか
りますので、まだ改善の余地有り。
なお、定義に従えば、１００万の計算に８日かかります。
1億までエクセルのＶＢＡで計算しましたが、実行時間は、約２０時間、反例は
見つかりませんでした。
これって、結構早いのでしょうか？
ちなみにマシンは、ＶＡＩＯのPCG-FX55/XPで、メモリーは６４ＭＢ。
なお、ゴールドバッハの予想を知らない方への説明。
全ての偶数は、２個の素数の和で表される。
そこで、ある制限をかけて、いかなる偶数の平方根の２倍＋１よりも大きい
素数と、その他の素数の和となることは無いと予想したのですが、果たして反
例は見つかったか？結果は？
興味のある方は、掲示板に書きこんで頂けば、マクロが入ったエクセルのソ
フトの配置してあるＵＲＬを書き込みます。
なお、今のところ、私のエラトステネスの篩は、１００万の計算に１２秒かか
りますので、まだ改善の余地有り。
なお、定義に従えば、１００万の計算に８日かかります。
380 ：デフォルトの名無しさん：02/01/30 04:03
ところで、ある程度以上大きくて2^n-1以外の素数ってあるの？
ある程度ていうのも、へんな言い方だけど…
ある程度ていうのも、へんな言い方だけど…
381 ：デフォルトの名無しさん：02/01/30 04:56
＞379
VBで実行してみたいです。
VBで実行してみたいです。
382 ：デフォルトの名無しさん：02/01/30 08:44
>>380 素数は Aの付近に 1/log(A)程度の頻度でありますよ
log(2^n-1)はおよそlog(2)*Nだから 2^n-1〜2^(n+1)の間にも0.7*n個程度あるという事
log(2^n-1)はおよそlog(2)*Nだから 2^n-1〜2^(n+1)の間にも0.7*n個程度あるという事
>>382 さんきゅ。
384 ：デフォルトの名無しさん：02/01/30 12:03
× だから 2^n-1〜2^(n+1)の間にも0.7*n個程度あるという事
○ だから 2^n-1〜2^(n+1)の間にも(2^n)/(0.7*n)個程度あるという事
○ だから 2^n-1〜2^(n+1)の間にも(2^n)/(0.7*n)個程度あるという事
385 ：デフォルトの名無しさん：02/02/08 23:54
ＦＦＴではなぜ、ビット反転操作をするんですか?教えてください。
386 ：デフォルトの名無しさん：02/02/09 00:27
刺身定食くいたくなった…
387 ：デフォルトの名無しさん：02/02/09 08:12
>>385
ここ参考にするといいでしょ
http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/
特にこの絵
http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/fig_bf2.gif
最後にビット反転置換をしなくても良い方法もあるけど、
すると毎回複製が必要になるのと、ループが少し複雑になるから
メモリの節約になるこの方法が好まれているのでしょう
ここ参考にするといいでしょ
http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/
特にこの絵
http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/fig_bf2.gif
最後にビット反転置換をしなくても良い方法もあるけど、
すると毎回複製が必要になるのと、ループが少し複雑になるから
メモリの節約になるこの方法が好まれているのでしょう
388 ：デフォルトの名無しさん：02/02/10 15:12
ありがとうございました＞387
389 ：デフォルトの名無しさん：02/03/02 23:03
確率的判定法(Rabin)の計算量オーダーはlog(n)なのは知ってるけど
確定的判定法で最速の物ってどれよ？
ecppだっけ？あれはどれぐらいのオーダー？
確定的判定法で最速の物ってどれよ？
ecppだっけ？あれはどれぐらいのオーダー？
390 ：デフォルトの名無しさん：02/03/11 18:04
>>389 なんでsageで聞いたの？
391 ：デフォルトの名無しさん：02/03/16 18:45
俺も知りたいage
392 ：デフォルトの名無しさん：02/04/13 09:40
あげ
393 ：デフォルトの名無しさん：02/04/21 11:05
あげ
394 ：デフォルトの名無しさん：02/05/21 09:16
確率的判定法って 単に何度か割ってみて割り切れなかったらと変わりないように思うのだが？
例えば1万個の素数を用意しといて割ってみて割り切れなかったら 素数でない確率は1万分とか
例えば1万個の素数を用意しといて割ってみて割り切れなかったら 素数でない確率は1万分とか
395 ：デフォルトの名無しさん：02/05/21 09:19
>>394
オオバカ
オオバカ
396 ：デフォルトの名無しさん：02/05/21 09:28
397 ：デフォルトの名無しさん：02/06/07 20:47
保存
398 ：デフォルトの名無しさん：02/06/21 06:51
ぷろろｒぐ
399 ：デフォルトの名無しさん：02/06/21 08:45
素人でよくわからんのですが
テーブルを分解・圧縮して計算に使う部分をなるべくキャッシュに載るようにして
レジスタも使って（速度の桁が違うので）
2の倍数乗除にシフト、（プロセッサ内で勝手にシフトに切り替わるかな？^^;）
遅い割り算を逆数掛け算にしたりとかは効果ないんでしょうか？
テーブルを分解・圧縮して計算に使う部分をなるべくキャッシュに載るようにして
レジスタも使って（速度の桁が違うので）
2の倍数乗除にシフト、（プロセッサ内で勝手にシフトに切り替わるかな？^^;）
遅い割り算を逆数掛け算にしたりとかは効果ないんでしょうか？
400 ：デフォルトの名無しさん：02/06/21 08:48
倍数→累乗 マチガえました(笑
大規模３Ｄレンダリングなどで使う
クラスタリングが分散にいいらしいです
大規模３Ｄレンダリングなどで使う
クラスタリングが分散にいいらしいです
401 ：デフォルトの名無しさん：02/06/21 09:26
>>399 小手先のテクニックは 同じ計算時間で 計算出来る数が少し増えるだけ
並列計算も、完全に成功しても台数分 数が増えるだけ
それは頑張って１０台並列でももたった１桁増えるかどうかのレベル
掛算をFFTにしたような、一挙に桁数を倍に出来るようなアイデアが求められている
並列計算も、完全に成功しても台数分 数が増えるだけ
それは頑張って１０台並列でももたった１桁増えるかどうかのレベル
掛算をFFTにしたような、一挙に桁数を倍に出来るようなアイデアが求められている
32bitMAXなら計算済みのを展開して2分探索すればあっという間だね