| 速度&登録 投稿者：s-yama 投稿日：2004/07/05(Mon) 21:13 No.101 | |
|
20019996^8192+1の探索速度
P4 2.2GHz 4min28sec
P3 1.4GHz 3min57sec
以外や以外にも、GeneFerは、P4が遅いです。
ところで、probable primeが出たのですけど、わたし登録ができません。登録してもらえる「あなた様」に差し上げます。primeかどうか確認して登録して下さい。（素数探索連携掲示板では、発見者が登録することになっているのですが）素数探索連携掲示板に書きましょうかメールにしましょうか。よろしくお願いします。
初めてなもので、年甲斐もなく興奮してます。
|
| Re: 速度&登録 turbo - 2004/07/05(Mon) 23:51 No.102 | |
|
|
> 登録してもらえる「あなた様」に差し上げます。
あつかましいことを承知でいただきたく思います。
（ふるいをやってなかったらここまで堂々と言えません）
probable primeの値はメールでいただければ幸いです。
お礼、というには程遠いかもしれませんが、The Prime Pages 登録の日本語マニュアルを作ろうと思います。
既に英文ページのおおまかな訳はしているのですが文章の推敲に時間がかかるので、とりあえず簡易マニュアルを UP するつもりです。
|
| Re: 速度&登録 nohara - 2004/07/06(Tue) 02:14 No.103 | |
|
|
s-yamaさん、turboさん、
登録についてですが、グループ名を設定して、それで登録するというのはどうでしょうか。
例えば、Matさんの掲示板上での共同作業で見つかったということで、MatGFNsearch等、適当な名前をつけてみるのはどうでしょう。
プロフィール欄のメッセージの文章が書けない、という場合は
パスワードを教えて下されれば、私の拙い英語で適当に
書いておきます。
|
| Re: 速度&登録 turbo - 2004/07/06(Tue) 13:37 No.105 |  |
|
|
とりあえず "MatGFNsearch" のアカウントを取ってみました。
http://primes.utm.edu/bios/page.php?id=662
いまのところ人物扱いで、プロジェクト扱いにするには管理人にメールで連絡しなければならないとのことですが、私一人でつっ走るのはどうかと思うので皆さんの意見をお聞かせいただけないでしょうか。
あと、グループ登録について気をつけなければならない点などをご存知でしたら教えてください。
|
| Re: 速度&登録 nohara - 2004/07/06(Tue) 15:36 No.106 | |
|
|
noharaです。
turboさん、行動が早いですね。
私はてっきり、team-turboの方が格好良いので、nohara案は却下
等という返信を期待していたのですが。
冗談はさておき、わたしもグループ登録の注意点などは
私も良く分かりません。個人的には、責任者(登録代行者)
を誰かはっきりさせ、連絡先メールアドレスを載せることで
十分なような気がします。またプロジェクトの内容に
日本語での活動の旨を記述すれば良いでしょう。
プロジェクト自体がオンラインでなければならない規則は
無いのではないか、というのが個人的な意見です。
暫定処置（そのまま恒久でも良いとは思いますが）
としてはturboさんの作成されたアカウントでの登録で良いか
と思います。見たら、素数が一緒に登録して無いので、
素数を登録しない限り、いつでも削除され得ますよ、
との注意がありますね。
しかし、3*2^n+1という形式の素数を探索されていたJhon
Cosgrave氏の場合、実際は氏と大学内のグループで探索されて
いたにも関わらず、個人名で登録されていた例もあります。
この点Chris K. Caldwell氏にメールを出してみましょうか。
もっとも、氏もPrime Pagesをたった一人で運営されているため、
（私も初めて知ったが）かなり多忙なようです。つい先日Prime
Pagesのサーバーがダウンしたことがありましたが（それで
アクセスできなくなっていた）、一人での管理は大変だ、
top20等、管理項目を増やしたいという要望が多いが、
今のままでは無理だよ。
だれかボランティアで管理を分担してくれる人がいたら、
お願いしますというような内容のことがグループメールで
流れてきました。（やや意訳あり）
英文メールなら私は毎日仕事で書いているので書くこと
自体別に苦でも無いですが（得意というほどでもないですが）、Chris氏に負担はあまり掛けさせたくないので、そのままでも
いいのでは無いでしょうか。
|
| Re: 速度&登録 216091 - 2004/07/06(Tue) 19:39 No.107 | |
|
|
s-yama さん素数発見おめでとうございます。
>20019996^8192+1の探索速度
>P4 2.2GHz 4min28sec
>P3 1.4GHz 3min57sec
>以外や以外にも、GeneFerは、P4が遅いです。
P4 は、SSE2 の演算器だけで従来の FPU の計算も
SSE2 の 64bit の演算器でやっているみたいです。
というわけで genefer80 最速は、アスロンみたい
です。
|
| Re: 速度&登録 turbo - 2004/07/06(Tue) 20:05 No.108 | |
|
|
nohara さん wrote:
> Chris氏に負担はあまり掛けさせたくないので、そのままでも
> いいのでは無いでしょうか。
s-yama さんにいただいた素数を登録してみました。
私と MatGFNsearch という仮想の人物との共同発見扱いにしています。
この場合発見個数などが折半されてポイントでは不利になりますが、そこだけ我慢すればあとは同じだと思います。
|
| Re: 速度&登録 s-yama - 2004/07/06(Tue) 21:14 No.109 | |
|
|
turboさん、お疲れ様です。
みなさんの協力のおかげです。今年の初めには、primeということばさえ知らない私にいろいろ教えて頂いてありがとうございます。
あ〜ぁ Athlonが欲し〜いです。
|
| Re: 速度&登録 nohara - 2004/07/07(Wed) 07:14 No.110 | |
|
|
皆様お疲れ様でした。
ところで、
AthlonでGenefer80のベンチマークテストを実施してみました。
Generalized Fermat Number Bench
246303942^256+1 Time: 18.1 us/mul. Err: 4.06e-001 2149 digits
200060966^512+1 Time: 38.1 us/mul. Err: 4.06e-001 4251 digits
162500000^1024+1 Time: 86.8 us/mul. Err: 3.75e-001 8408 digits
131991014^2048+1 Time: 183 us/mul. Err: 3.75e-001 16631 digits
107210016^4096+1 Time: 442 us/mul. Err: 3.75e-001 32892 digits
87081592^8192+1 Time: 984 us/mul. Err: 3.75e-001 65044 digits
70732232^16384+1 Time: 2.11 ms/mul. Err: 3.75e-001 128609 digits
57452424^32768+1 Time: 5.19 ms/mul. Err: 3.28e-001 254258 digits
46665870^65536+1 Time: 13.1 ms/mul. Err: 3.59e-001 502596 digits
37904464^131072+1 Time: 28.4 ms/mul. Err: 3.75e-001 993355 digits
30787992^262144+1 Time: 59.3 ms/mul. Err: 3.13e-001 1963035 digits
25007620^524288+1 Time: 140 ms/mul. Err: 2.97e-001 3878721 digits
20312500^1048576+1 Time: 308 ms/mul. Err: 2.81e-001 7662746 digits
16498876^2097152+1 Time: 670 ms/mul. Err: 2.81e-001 15136099 digits
実際に素数判定テストを実施してはいないのですが、
この結果から、20019996^8192+1の場合、
Athlon XP 3000+ (actual 2166M/FSB333MHz)
での推定処理時間は3min16sec.となります。
Athlon MP 2800+ (actual 2133M/FSB266MHz)
でも同様にテストしましたが、一様にXP3000+と比較して
4％程度低速になります。大きなnの場合でもFSBの影響は
ほとんどみられません。
P3でいえば1.7MHz相当の速度なので、Athlonといえど
それほど速いわけではありません。
|
| Re: 速度&登録 216091 - 2004/07/07(Wed) 19:19 No.111 | |
|
|
こんばんわ、
わざわざアスロンを買う程の性能差じゃありませんね。
で、otto で 3.2万円で買ってしまった P4 1.6Ghz に何をやらせたら良いかというと
pfgw
+ ./pfgw-linux-1.1-i586 -t '-q1000000^8192+1' 1000000^8192+1 is composite (998.380000 seconds) user 16m37.320s
+ ./pfgw-linux-1.1-i586 -t '-q10000000^8192+1' 10000000^8192+1 is composite (1593.890000 seconds) user 26m32.880s
+ ./pfgw-linux-1.1-i586 -t '-q100000000^8192+1' 100000000^8192+1 is composite (-2046.457296 seconds) user 37m27.540s
genefer80
GeneFer 1.3 (80-bit x86-ASM) Copyright (C) 2001-2003, Yves GALLOT
Testing 1000000^8192+1...1000000^8192+1 is composite (err = 5.53e-05). user 5m10.580s
Testing 10000000^8192+1...10000000^8192+1 is composite (err = 5.86e-03). user 5m59.870s
Testing 100000000^8192+1...100000000^8192+1 is composite (err = 5.00e-01). user 6m48.080s
genefer64(Proth.exe と多分同じ)
GeneFer 1.3 (x86-ASM) Copyright (C) 2001-2003, Yves GALLOT
Testing 1000000^8192+1...1000000^8192+1 is composite (err = 6.49e-02). user 1m22.170s
Testing 10000000^8192+1...10000000^8192+1 is composite (err = 5.00e-01). user 1m40.290s
Testing 100000000^8192+1...100000000^8192+1 is composite (err = 5.00e-01). user 1m57.500s
というわけで、pfgw 、genefer80 は遅いので Proth.exe が良いのですが、
GFN で Proth.exe で探せる数はもう巨大なものしか残ってないので、
k.2^n+1 とかの数で top 5000 にランクインする数を探すのがよさそうですね。
(linux で動く Proth.exe がないので私にはできないのですが)
＃探せる素数の数が倍位ちがうんじゃないでしょうか
pfgw が OPENpfgw と同じソースなら FFT に GNU のものを使っているので SSE2 とかの対応が
されていないので遅いのでしょう。
|
| Re: 速度&登録 nohara - 2004/07/08(Thu) 05:21 No.112 | |
|
|
こんばんは
216091さん
>＃探せる素数の数が倍位ちがうんじゃないでしょうか
私の意見では、倍までは違わなくとも、素数を見つける
効率がよいのはやはり、LLR.exeを用いてのk*2^n-1探索です。
http://www.mersenne.org/gimps/llr.zip
ここのLLR.zipを選択します。
linux版もあるようです。
turboさんに紹介した当時はとりあえず、k<256以下で速く
判定できると思ったのですが、その後、K<256でも場合によって
異なることが判明しました。
k=1の場合、これはメルセンヌ数ですが、Prime95を使いなさい、
とアドバイスをくれます。処理は可能ですが、Prime95より遅い
ようです。
k=3の場合 実質的に最も速くなります。指数によって異なるの
ですが、PRP.exeの80%増から3倍近い速度で素数判定を実施します。
Proth.exeでのGFNといい勝負です。
k=5-15の場合 k=3より20%程度遅くなります
k=17-63の場合 k=5-15より20%程度遅くなります
k=65-255の場合 k=17-63より20%程度遅くなります
k>257の場合 k=65-255より20%程度遅くなり、PRP.exeと
同等の速度になります。
(P3 600MHz上での結果)
kを固定して、k*2^n-1でふるいを実施し、それをLLRを使うのが
素数探索には最も効率がよいでしょう。
ただ、k=3の場合とk=121の場合はすでにプロジェクトが立ち上
がっており、LLR.exeによる探索も最近競争が激しくなっています。
素数探索の方針としては、大きさはそれほど目指さなくても、
特殊な形式のものを探す、という手があります。
例1 双子素数 今更言うまでもないでしょう。
例2 Sophie GermainやCunningham chain の組など
例3 フェルマー数や一般フェルマー数の約数になる素数
小さなkのk*2^n+1を探すと見つけやすい。
素数k*2^n+1は1/kの確率でフェルマー数の約数になりうる、
という定理があります。
例4 階乗 n!+1, n!-1といった数または
素数階乗 P#+1/-1 (2*3*5*7*11*......*P+1/-1)といった数
例5 ECPPによる素数判定を行う
これらは桁数的には大きなものは狙えませんが、例えば、
フェルマー数の約数や階乗、素数階乗素数となるような
素数を見つければ、半永久的にランキングに残ります。
もちろん、その分発見はかなり困難になります。
こういった素数は、最大素数ほどではないですが、
ある程度は注目されるので、見つけた時の感動はひとしおです。
ECPPはテスト対象となる数はほぼ間違いなく素数になりますが、
1回のテストに2GHzクラスのマシンで数ヶ月、長い場合には
1年以上マシンが占領されます。もちろん途中で処理を中断する
ことは可能です。ただ、現在、このツールがおいてあるHP
ではECPPによる素数判定ソフトがダウンロードできなくなって
います。
|
| Re: 速度&登録 216091 - 2004/07/08(Thu) 22:02 No.114 | |
|
|
こんばんは、
教えていただいた、llr 試しました。P4 1.6Ghz で
2066a 147*2^198692-1 59815 L40 2004
2067a 20019996^8192+1 59814 p142 2004 Generalized Fermat
2068a 20000822^8192+1 59811 g360 2004 Generalized Fermat
s-yama さんと私が発見した素数とその近くの k.2^n-1 型素数で
Starting Lucas Lehmer Riesel prime test of 147*2^198692-1
147*2^198692-1 is prime! Time : 202.180 sec.
user 3m22.110s
$ time ~/genefer/genefer80a
20019996^8192+1 is a probable prime. (err = 2.34e-02)
user 6m16.500s
と genefer80 に比較して倍近く速いです。でも
Starting Lucas Lehmer Riesel prime test of 26565*2^198349-1
26565*2^198349-1 is prime! Time : 314.965 sec.
user 5m14.940s
確かに k が大きくなると遅いですね。
おっしゃるように、ある k に対する素数の数は Mersenne 素数なみに
少なくまた、n は２の冪の項なのでどんどん数が大きくなってしまう
ので 小さい k には探す数がない問題がありますね。
なので、探す素数を小さくして top5000 ぎりぎりにして速度を
かせいで n を固定して探索することにしました。
Starting Lucas Lehmer Riesel prime test of 205053*2^168666-1
205053*2^168666-1 is prime! Time : 184.857 sec.
user 3m4.820s
ここのあたりで上記の GFN 素数の半分位の時間なので n=168668 k=2〜10000
を探索してみようとおもいます。
|
| Re: 速度&登録 nohara - 2004/07/09(Fri) 05:48 No.115 | |
|
|
216091さんwrote
>おっしゃるように、ある k に対する素数の数は Mersenne 素数なみに
>少なくまた、n は２の冪の項なのでどんどん数が大きくなってしまう
>ので 小さい k には探す数がない問題がありますね。
実は、この点平均した場合はそうかもしれませんが、kによっては
それは正しくありません。
例えば、
3*2^n-1の場合、この数列はどんなnを代入しても3で割り切れること
はありません。
しかし、メルセンヌ数2^n-1はnが偶数の場合、必ず3で割り切れます。この時点で素数脱落候補がメルセンヌ数系列では多くなります。
実際、3*2^n-1系列での素数出現数(n<1000000)はメルセンヌ素数
よりずっと多くなっています。
7*2^n-1の場合、この数列はどんなnを代入しても7で割り切れること
はありません。
しかし、メルセンヌ数2^n-1はnが3で割り切れる場合、必ず7で割り切れます。この時点で素数脱落候補はメルセンヌ数系列は不利です。
21*2^n-1の場合、この数列はどんなnを代入しても、3で割り切れる
ことも、7で割り切れることもありません。
メルセンヌ数ではnが偶数なら3で割り切れ、nが3の倍数なら7で割り切れ、この段階ですでに素数候補の多くが脱落します。
ただし、その一方で
509203*2^n-1の場合、この数列はどんなnを代入しても、素数には
絶対になりません。
(素数探索プロジェクトの私の書き込みを参照)
ということもあるわけです。
単純に考えれば、kが多くの異なる素数の積であれば、それらの素数
で割り切れて素数候補が脱落する、という可能性が減るため、
そういった数では素数にめぐり合う可能性が高くなります。
もちろん、そうとは限らないのですが。つまりkが比較的
大きな素数なのに頻度が高かったり、逆の場合もあります。
このことを実感するには、NewPGen.exeを用いて、いくつか
ランダムにkを選んで、kを固定し、ふるい上限のpを固定した
とき、残る候補がどう異なるかみてみると面白いと思います。
k*2^n+1の場合なら、例えばk=45とk=47とでその違いを
ぜひ比べてください。
素数出現率が高そうなkを使ってk固定での探索を行う、
実際にこういった方針で探索されている方も結構
いらっしゃいます。
また、桁数がランキングぎりぎりの素数を多数見つけても
素数発見者に与えられるスコアは全然伸びず、大きな桁数
の素数1個発見した人には普通は到底及びません。
探索する素数の形式にこだわらず、2GHz以上のパワーが
24時間素数探索に使える人には10万桁、できれば、私の知る
限りの日本人最高64059*2^510101+1 (153561桁)更新は
狙ってほしいというのが個人的な意見です。
2GHz1台で10万桁なら2-3ヶ月で、記録更新レベルなら
1年かければ狙えます。
もちろん、方針が人それぞれなのが普通なので、
あくまで私の一意見ということですが。
|
| Re: 速度&登録 s-yama - 2004/07/09(Fri) 08:44 No.116 | |
|
|
3500000^32768+1(21万桁)を探索してみます。
|
| Re: 速度&登録 nohara - 2004/07/10(Sat) 02:18 No.118 | |
|
|
私は現在9*2^n+1のn=600000-700000を探索しています。
n<600000は探索済みです。
ベンチマークテストで使用したAhlonXP 3000+はずっとこの計算
を行っています。素数があれば、18-21万桁になるのですが、
この範囲で素数があるかどうか。
探索範囲が広いので、探索終了は年末の予定です。
競争相手（？）がいるほうがモチベーションが上がるとはいえ、
s-yamaさん相手では分が悪すぎます(笑)。
|
| Re: 速度&登録 s-yama - 2004/07/10(Sat) 18:15 No.121 | |
|
|
b^32768+1 b=3250000-35000000 P4 5台で探索します。
約９ヶ月間の予定です。年末までに1〜2個見つかるでしょう。
47万桁は、簡単なものと思ったけれど、実際に探索してみると、
続けることの困難さを知らされました。21万桁は、どうなりますかな。
|
| Re: 速度&登録 216091 - 2004/07/10(Sat) 18:25 No.122 | |
|
|
こんばんは、
GFN について フェルマーテストをするプログラムを
作りました。
30406.^8192+1 is probable prime err=0.056
real 32m40.064s
user 32m31.665s
genefer よりかなり遅いですが、 FFT を使って
いるので指数関数的に遅いわけではありません。
|
| Re: 速度&登録 216091 - 2004/07/11(Sun) 18:53 No.127 | |
|
| Re: 速度&登録 nohara - 2004/07/12(Mon) 05:28 No.130 | |
|
|
216091さん、
わざわざ、ありがとうございます。
UBASICしか知らず、20行を超えるプログラムを書いたことが
無い私ですが、私もこれを機に少し勉強してみます。
|
|