米フロリダ州の男性、わずか4回の試行で51番目のメルセンヌ素数を発見 53
ストーリー by headless
幸運 部門より
幸運 部門より
Great Internet Mersenne Prime Search(GIMPS)は12月21日、これまで知られている中で最大の素数かつ51番目のメルセンヌ素数となる、282,589,933-1(M82589933)が12月7日に発見されたことを発表した(プレスリリース、
The Registerの記事)。
発見に使われたコンピューター資源を提供したのは、米国・フロリダ州のITプロフェッショナルの男性だ。この男性は何年にもわたってGIMPSのソフトウェアをコンピューターのストレステストとして使用しており、プロジェクトへの恩返しとしてメディアサーバーで素数の探索を最近開始したそうだ。
GIMPS参加者の中には20年以上にわたる数万回の試行で探索に成功しない人もいる中、この男性は4か月未満、わずか4回の試行でM82589933を発見したという。男性のメディアサーバーはIntel Core i5-4590T(4コア4スレッド)を搭載したもので、素数であることの確認に連続稼働で12日間を要しているが、GIMPSでは豊富なコンピューター資源がなくても十分に戦えることを示すものだと述べている。
M82589933は桁数にして24,862,048桁。これまで最大だった素数M77232917よりも160万桁以上多い。ZIPファイルで公開されているM82589933のテキストファイルを展開すると24.1MBとなり、100桁ごとに改行されたテキストは248,621行におよぶ。
発見に使われたコンピューター資源を提供したのは、米国・フロリダ州のITプロフェッショナルの男性だ。この男性は何年にもわたってGIMPSのソフトウェアをコンピューターのストレステストとして使用しており、プロジェクトへの恩返しとしてメディアサーバーで素数の探索を最近開始したそうだ。
GIMPS参加者の中には20年以上にわたる数万回の試行で探索に成功しない人もいる中、この男性は4か月未満、わずか4回の試行でM82589933を発見したという。男性のメディアサーバーはIntel Core i5-4590T(4コア4スレッド)を搭載したもので、素数であることの確認に連続稼働で12日間を要しているが、GIMPSでは豊富なコンピューター資源がなくても十分に戦えることを示すものだと述べている。
M82589933は桁数にして24,862,048桁。これまで最大だった素数M77232917よりも160万桁以上多い。ZIPファイルで公開されているM82589933のテキストファイルを展開すると24.1MBとなり、100桁ごとに改行されたテキストは248,621行におよぶ。
n番目のメルセンヌ素数 (スコア:1)
これは小さい順にn番目であることが証明されてるの? それとも発見順(今まで発見されたメルセンヌ素数の間にも未発見のメルセンヌ素数が存在する可能性がある)?
Re:n番目のメルセンヌ素数 (スコア:2, 参考になる)
Wikipediaによると
＞48から51番目は、2018年12月時点でより小さなメルセンヌ素数の個数を検証できていないことによる暫定的な順位である。
だそうで。
Re: (スコア:0)
既知の中で小さい順だね。
負荷 (スコア:0)
最近は円周率の桁数記録のニュース聞かないなーという感覚だったが、メルセンヌ素数っていう手法もあったのね＞CPU負荷
Re: (スコア:0)
負荷を与えるならCPUのメーカーから公式のツールが配布されてませんか？
どちらかと言うと排熱設計の目的ですが
Re: (スコア:0)
公式ツールだとVWが気になる
素数探求はレースじゃねぇ (スコア:0)
まあ円周率計算だと連続稼働時間をいかに伸ばせるかの戦いですからね
素数の計算と違ってどこを計算するかとかどこから計算を始めるかといった選択の余地が一切ない
アルゴリズムを考える人や実装する人、プロセッサに最適化する人にとってはまた違うのでしょうが
#結局そういうことをやってるせいで歯抜けになってるわけで手分けして絨毯爆撃方式をやるほうが電気代と資源のムダが少ない
Re:素数探求はレースじゃねぇ (スコア:5, 参考になる)
> 素数の計算と違ってどこを計算するかとかどこから計算を始めるかといった選択の余地が一切ない
以前はそう考えられていましたが
1995年に円周率のn桁目だけを直接計算する数式が発見されています．
実際の式と，その実装であるBBPアルゴリズムについては
以下のページあたりが参考になると思います
http://www.kk62526.server-shared.com/pi/BBP.html [server-shared.com]
これを応用することで，
今では，円周率のN桁目からM桁目だけを計算するといった選択の余地ができています．
たとえば円周率計算を2兆桁まで計算！などのニュースが時々流れますが
その計算結果の検算でBBPアルゴリズムがよく使われます．
つまり，２兆桁の円周率からランダムにN桁目からM桁目を選んで，
その値をBBPアルゴリズムで計算した値と比較，
一致したら計算結果は間違ってはなさそうと判断するわけです．
（もちろん厳密な判定には他の検算方法も組み合わせます）
Re:素数探求はレースじゃねぇ (スコア:1)
BBPで求まるのは16進数での任意桁だから、10進数だと基数変換できる程度には複数桁求めなきゃ駄目なんだっけ？
まぁどっちにしてもBBP以外での計算で検算が必要なら他のアルゴリズムでの計算は結局必要だよね。
Re: (スコア:0)
この公式、もう20年以上前だし、コンピューター数学をやっている人にとっては常識（誰でも実装できるというレベルではないが、そういうのがあることぐらいは知っている程度には）だと思っていたけど、そうでもなかったのかな。
Re: (スコア:0)
はいはいそうですね。
Re: (スコア:0)
現代語訳: ボクは知ってた。すごいでしょ。
Re: (スコア:0)
自分が、そう思ってることを「常識」と言わないのが「常識」ですよｗ
豊富なコンピューター資源がなくても十分に戦える (スコア:0)
初めて買った宝くじが一等に当たるようなモンですかね？
Re: (スコア:0)
リアルチャーリーとチョコレート工場ですね
Re: (スコア:0)
宇宙破壊コンピューターか確率操作能力でも持っているのかもしれない。
https://qiita.com/iKodack/items/d606a09f0a40b95bf2b6 [qiita.com]
しかし4回もの試行が観測可能であったことから、能力は完全ではないようだ。
Re:豊富なコンピューター資源がなくても十分に戦える (スコア:1)
へ〜これは面白いな
素数でなくメルセンヌ素数 (スコア:0)
メルセンヌ素数を見つけることに数学的意義以外のメリットって何かあるんでしょうか？
たとえば素数なら、素数テーブルを１個埋められて暗号解析に役立つかもとか
地味ながらも何らかの現実的意味を見いだせなくもないのですが・・。
全くの素人考えですが、
メルセンヌ素数の bitが全部1だっていう特性がコンピュータ的に
何か特別に役立つってことがあったりするんでしょうか。
Re:素数でなくメルセンヌ素数 (スコア:2, 興味深い)
これ [it1.jp]かな？大きい素数を探すのには効率がよいそうで。
メルセンヌ数の素数判定法にはリュカ-レーマー・テストというものが考案されており、メルセンヌ数でない数の素数判定よりも早く素数であるかどうかを判定できる。
リュカ-レーマー・テストでは、随所でメルセンヌ数で割り算をするという行為が行われるのだが、コンピューターで割り算をするとなると計算時間がかかるところを、シフト演算と足し算という計算時間がかからない操作のみで割り算と同等の操作をすることができるので早く素数判定ができるようになっている。
なお、
メルセンヌ素数という形にとらわれずに最大の素数を見つけようとすることは、険しい道のりになるかもしれないが、もしも発見することができたらそれは革命的なことだ。
とも。
Re:素数でなくメルセンヌ素数 (スコア:2, 参考になる)
メルセンヌ・ツイスタって擬似乱数列生成器はメルセンヌ素数219937-1を使っている。
他のメルセンヌ素数を使っても疑似乱数として使えるが、短いと周期が短いし、長いと使用メモリが増えるのでこの値を使用するのが一般的。
Re:素数でなくメルセンヌ素数 (スコア:1)
でかい素数があれば暗号強度が上げられるだろ。
最大を使うとバレるから余裕が必要。
the.ACount
Re: (スコア:0)
メルセンヌ素数は素数である検証が楽だから、大きな素数を比較的簡単に見つけられる。メルセンヌ素数が集まってメルセンヌ素数の分布から次が予言できるようになれば、新しい数学定理が見つかるかもしれない。
Re: (スコア:0)
将来無関係そうな所で役に立つ可能性を否定できない以上、調べる事は未来に対する義務です。
Re: (スコア:0)
役に立つかどうかは知らんがメルセンヌ素数ばかり探されるのは2進数で1ばかりという特性を利用して計算機上ではほかの素数より容易に探せるからだと思う
Re: (スコア:0)
うまくやったらブロックチェーンのPoWとかに使えそうな気がするんだけどね。
任意精度の数値表記標準フォーマット (スコア:0)
ZIPファイルで公開されているM82589933のテキストファイル
この手のはなぜかわざわざテキストファイルにする事が多いよね。
1Bで0.42Bの情報って効率悪すぎだと思うんだが、なんで可変長整数/少数表記の標準ファイル形式とか産まれなかったんだろうね？
圧縮すれば割と同じ事だろうけど。
制御文字で切り替えて数字モードにする事で若干容量を小さくしたりコンピューターで処理しやすくなったりするだろうに。
逆にファイルサイズが大きくなることもあるだろうけど、XMLとかJSONでのシリアライズで数字だけ2進数表記とかできれば処理も早くなるだろうし扱いやすい。
Re:任意精度の数値表記標準フォーマット (スコア:3, 興味深い)
プログラムで24,862,048桁もあるような巨大な数値を扱う場合は
数値は「文字列」として記述するのが普通です
たとえば比較的有名なライブラリとして
GNUの多倍長整数演算ライブラリGMPをみても，
変数に大きな値を代入するAPIはmpz_set_str関数しかありません
https://gmplib.org/manual/Assigning-Integers.html [gmplib.org]
そして，この関数の引数は null-terminated C string，つまり文字列です
ですから，この手のライブラリを使う人々にとっては
文字列が標準フォーマットです．だからファイルフィーマットはテキストファイルが普通ですし，その方が便利です．
数値計算で何日も掛かるような大掛かりな計算をする分野ですから，
24MB程度のデータファイルのサイズは気にしても意味がありません．
24,862,048文字を{}とかでくくったJSONとかXML形式とか
リトルエンディアン，ビッグエンディアンとかを考慮しなければならないバイナリ形式なんて
とても使えたものじゃないと思います．simple is best です．
Re: (スコア:0)
それは交換形式であって、10進多倍長の内部形式としてはpacked BCD辺りも十分・・・
C/C++ならビットフィールド使えば一桁1フィールドでそのまま表現可能。
テキストだと上4ビットが邪魔で扱いにくい。
あと、MB単位の長さを考え始めるとNULL終端文字列一つ(連続メモリ領域)で扱うのも微妙。
そろそろストリームを考えるべき長さだと思う。
Re:任意精度の数値表記標準フォーマット (スコア:2)
短くなるようにコード化すると「このデータはどういうフォーマットなのか」という型情報が必要になってくる。
テキスト形式なら「一目見れば誰でもわかる」とまではいかないけど、慣れてくれば見るだけで判別できることも多い。
複数のデータ、それも型が混在しているものでも改行区切りやCSVなど見だけでも推測できるフォーマットが広く普及している。
こういう「型情報付きでパック化したデータ」としてはMessagePack [msgpack.org]とかがあって、人間が直接目で見る必要がほとんどなくWebAPIなどでデータを頻繁にやりとりする場合はかなり有用だけど、こういう巨大ではあっても単発のデータではパック化することでテキストファイルと比べて得られるメリットって大してないと思う。
うじゃうじゃ
Re: (スコア:0)
メルセンヌ素数をプログラム内部で扱う場合、2進以外ありえるの？
2進で扱いやすい、ビット演算を簡単にできるところにメルセンヌ素数の意義があると思うのだけど。
Re: (スコア:0)
多倍長演算で大きな数値を扱おうって場合、基数は2ではなく10の方が都合が良い場合がある。
「任意精度の数値表記標準フォーマット 」みたいなことを考える場合は2以外の基数を想定するのは当然かと。
メルセンヌ素数の美味しい応用例に関していえば基数2で扱うほうが良い場合も多々あるかもしれんが…
…そもそもその場合メルセンヌ素数は桁数以外の情報がプログラム側に吸収されて値としては出てこない気も。
Re:任意精度の数値表記標準フォーマット (スコア:1)
>圧縮すれば割と同じ事だろうけど。
まさにこれが理由では？
というか、情報量を考慮するなら「M82589933」という10文字足らずで表される数なんだから、10進で表すのはおまけみたいなもの。
後半読んでると不安になってくるけど、2進表記で1が82589933個並ぶ特殊な数なのは分かってるよね。
Re: (スコア:0)
バイナリの二進数表記とBCDの二種類のイメージですね。
わざわざテキストにするのはデコードコストと標準フォーマットによる扱いやすさでしょうから。
やり方はテキストファイルとしてできるだけ透過的に扱える仕組みが望ましく、制御文字で4Bit単位のBCD(+小数点やマイナスや終了文字)とか数桁まとめる(3B毎なら16777216でキリが良いかな？)とか、同じく制御文字でネイティブのintやfloatが埋め込める方法とか色々考えられますね。
どこかで標準化されていれば普通にテキストエディタで扱えて処理も軽く便利な場面が結構あった気がします。
Re: (スコア:0)
この手のデータをわざわざ可読テキストとして定義する需要が無いからね。
受け渡しはバイナリで十分。
門外漢にも広く公開しようと考えたら.txtは普及率も情報密度も圧倒的に良いでしょ。
こんなもんのために専用ビューアをダウンロードしたい？
Re: (スコア:0)
すでにテキストファイルが標準ファイル形式みたいな役割をしていて、このトピみたいな特殊用途向けデータ交換形式としては割と満足されているからじゃないかなあ。
サイズについてはおっしゃる通り圧縮で対応でき、
テキストを数値として読み込む標準関数が普及していることで扱いも問題ないから。
Re: (スコア:0)
まあメルセンヌ数専用の圧縮形式作れば、82589933って情報だけあればデコードできるんだけどね。
24.1MBのテキストファイルをヘッダ除いて8B（ASCIIコードの代わりにBCDコード使えば4B）に圧縮できるから超効率的
Re: (スコア:0)
なんかネタが思いっきり滑ってる感がハンパないが、
*「メルセンヌ素数のバイナリデータ」なんてネタは皆食傷気味
* 素で気づいてない
どっちだろ？
# 1111111.....
Re: (スコア:0)
そうだ、16進数表示すりゃいいんじゃない？ FFFFFFF...
# Base64だと///////////...
Re:任意精度の数値表記標準フォーマット (スコア:1)
それはありえない。
メルセンヌ素数を16進数表記した場合は先頭は1or7となる。
もし先頭が3(2進数で11)かF(2進数で1111)だと全体が3の倍数になってしまいます。
ちなみに今回のものは16進数で先頭は"1"です。(1FFFFFFF...)
Re: (スコア:0)
すばらしい！ ぜひ標準化すべきです [xkcd.com]！
24,862,048桁 (スコア:0)
観測出来る宇宙にあるすべての原子の数くらいですかね？
そんな途方もない数の中で素数が51個だけ？
規則性もないが100内にそれが半数もあるという驚くべき事象
どういう数学的意味があるのでしょうか？
それともこの素数の決まりも人間が定めただけのものなのでしょうか？
Re: (スコア:0)
「素数でなくメルセンヌ素数」というタイトルのコメントツリーまであるのに、どうやったらそんな誤読ができるの？
天才？
Re: (スコア:0)
バカなだけだと思うけど。
> そんな途方もない数の中で素数が51個だけ？
「既知の」「メルセンヌ素数」がその範囲内で51個だから二段階に誤読
> 規則性もないが100内にそれが半数もあるという驚くべき事象
規則性がありすぎるぐらいにある特殊な素数だし
指数関数で特殊な条件を満たす指数を数えているのだから元の指数関数(2^N)以上に増えるのは当然だし
何も考えずに「壮大な数」と「意外と少ない数」を並べて神秘性見出してるだけでしょ
Re: (スコア:0)
>「既知の」「メルセンヌ素数」がその範囲内で51個だから二段階に誤読
この場合「既知」こそが疑問の元なんじゃないの？
その範囲でそれだけしか存在しないの？既知どうとかじゃなくて、本当に？なんで？どうして？
っていう意味での。
言ってみれば子供の単純な疑問みたいなもん。
そもそも計算で導けるなら、上はともかく下は大体全部出そうなもんだしな、時間さえかければ。
Re: (スコア:0)
＞規則性がありすぎる
規則性は皆無だよ
2進数で1が並ぶと思ってるようだけどそんな規則はない
こいつ知ったかぶってバカ丸出しでワロタｗ
数学の博士号も持ってない輩が粋がって突っ込み入れるとか
自分の立場を理解してないのかな？
笑止
Re: (スコア:0)
うん、まあ、あなたには数学そのものが意味のないものなんでしょうね。
Re: (スコア:0)
＞観測出来る宇宙にあるすべての原子の数
Wikipediaによると約10^80個だからぜんぜん足りないですね
理の当然 (スコア:0)
> M82589933は桁数にして24,862,048桁。
ふむふむ。
> ZIPファイルで公開されているM82589933のテキストファイルを展開すると24.1MBとなり、
1桁1バイトなんだから、24,862,048バイトで約24.1MBだなあ
> 100桁ごとに改行されたテキストは248,621行におよぶ。
24,862,048桁を100桁ごとに改行したら、248621行と48文字。
＃何ごとの不思議なけれど。
Re:理の当然 (スコア:1)
キリが良いのはわかるが、なぜ100桁ごとなんだ、とか思ってしまうなぁ。
普通は80桁か136桁。で、縦は66行で1ページ。→15×11インチの連続用紙なら、2770枚か…とか。
#いや、「一行78文字推奨だ!」ってRFC5322ネタを書こうかと思ったけど、それ以上膨らませられなかった…
Re: (スコア:0)
間違えた。
×24,862,048桁を100桁ごとに改行したら、248621行と48文字。
〇24,862,048桁を100桁ごとに改行したら、248620行と48文字。