パスワードを忘れた? アカウント作成
13808494 story
数学

米フロリダ州の男性、わずか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行におよぶ。
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2019年01月06日 10時06分 (#3543941)

    これは小さい順にn番目であることが証明されてるの? それとも発見順(今まで発見されたメルセンヌ素数の間にも未発見のメルセンヌ素数が存在する可能性がある)?

    • by Anonymous Coward on 2019年01月06日 10時34分 (#3543947)

      Wikipediaによると

      >48から51番目は、2018年12月時点でより小さなメルセンヌ素数の個数を検証できていないことによる暫定的な順位である。

      だそうで。

      親コメント
    • by Anonymous Coward

      既知の中で小さい順だね。

  • by Anonymous Coward on 2019年01月06日 10時36分 (#3543948)

    最近は円周率の桁数記録のニュース聞かないなーという感覚だったが、メルセンヌ素数っていう手法もあったのね>CPU負荷

    • by Anonymous Coward

      負荷を与えるならCPUのメーカーから公式のツールが配布されてませんか?
      どちらかと言うと排熱設計の目的ですが

      • by Anonymous Coward

        公式ツールだとVWが気になる

    • まあ円周率計算だと連続稼働時間をいかに伸ばせるかの戦いですからね
      素数の計算と違ってどこを計算するかとかどこから計算を始めるかといった選択の余地が一切ない
      アルゴリズムを考える人や実装する人、プロセッサに最適化する人にとってはまた違うのでしょうが
      #結局そういうことをやってるせいで歯抜けになってるわけで手分けして絨毯爆撃方式をやるほうが電気代と資源のムダが少ない

      • by annoymouse coward (11178) on 2019年01月06日 16時36分 (#3544020) 日記

        > 素数の計算と違ってどこを計算するかとかどこから計算を始めるかといった選択の余地が一切ない

        以前はそう考えられていましたが
        1995年に円周率のn桁目だけを直接計算する数式が発見されています.

        実際の式と,その実装であるBBPアルゴリズムについては
        以下のページあたりが参考になると思います
        http://www.kk62526.server-shared.com/pi/BBP.html [server-shared.com]

        これを応用することで,
        今では,円周率のN桁目からM桁目だけを計算するといった選択の余地ができています.

        たとえば円周率計算を2兆桁まで計算!などのニュースが時々流れますが
        その計算結果の検算でBBPアルゴリズムがよく使われます.

        つまり,2兆桁の円周率からランダムにN桁目からM桁目を選んで,
        その値をBBPアルゴリズムで計算した値と比較,
        一致したら計算結果は間違ってはなさそうと判断するわけです.
        (もちろん厳密な判定には他の検算方法も組み合わせます)

        親コメント
        • by Anonymous Coward on 2019年01月06日 19時08分 (#3544044)

          BBPで求まるのは16進数での任意桁だから、10進数だと基数変換できる程度には複数桁求めなきゃ駄目なんだっけ?
          まぁどっちにしてもBBP以外での計算で検算が必要なら他のアルゴリズムでの計算は結局必要だよね。

          親コメント
        • by Anonymous Coward

          この公式、もう20年以上前だし、コンピューター数学をやっている人にとっては常識(誰でも実装できるというレベルではないが、そういうのがあることぐらいは知っている程度には)だと思っていたけど、そうでもなかったのかな。

          • by Anonymous Coward

            はいはいそうですね。

          • by Anonymous Coward

            現代語訳: ボクは知ってた。すごいでしょ。

          • by Anonymous Coward

            自分が、そう思ってることを「常識」と言わないのが「常識」ですよw

  • by Anonymous Coward on 2019年01月06日 11時10分 (#3543957)

    初めて買った宝くじが一等に当たるようなモンですかね?

  • by Anonymous Coward on 2019年01月06日 12時25分 (#3543973)

    メルセンヌ素数を見つけることに数学的意義以外のメリットって何かあるんでしょうか?
    たとえば素数なら、素数テーブルを1個埋められて暗号解析に役立つかもとか
    地味ながらも何らかの現実的意味を見いだせなくもないのですが・・。

    全くの素人考えですが、
    メルセンヌ素数の bitが全部1だっていう特性がコンピュータ的に
    何か特別に役立つってことがあったりするんでしょうか。

    • by Anonymous Coward on 2019年01月06日 13時38分 (#3543983)

      これ [it1.jp]かな?大きい素数を探すのには効率がよいそうで。

      メルセンヌ数の素数判定法にはリュカ-レーマー・テストというものが考案されており、メルセンヌ数でない数の素数判定よりも早く素数であるかどうかを判定できる。
      リュカ-レーマー・テストでは、随所でメルセンヌ数で割り算をするという行為が行われるのだが、コンピューターで割り算をするとなると計算時間がかかるところを、シフト演算と足し算という計算時間がかからない操作のみで割り算と同等の操作をすることができるので早く素数判定ができるようになっている。

      なお、

      メルセンヌ素数という形にとらわれずに最大の素数を見つけようとすることは、険しい道のりになるかもしれないが、もしも発見することができたらそれは革命的なことだ。

      とも。

      親コメント
    • by Anonymous Coward on 2019年01月06日 14時56分 (#3543994)

      メルセンヌ・ツイスタって擬似乱数列生成器はメルセンヌ素数219937-1を使っている。
      他のメルセンヌ素数を使っても疑似乱数として使えるが、短いと周期が短いし、長いと使用メモリが増えるのでこの値を使用するのが一般的。

      親コメント
    • でかい素数があれば暗号強度が上げられるだろ。
      最大を使うとバレるから余裕が必要。

      --
      the.ACount
      親コメント
    • by Anonymous Coward

      メルセンヌ素数は素数である検証が楽だから、大きな素数を比較的簡単に見つけられる。メルセンヌ素数が集まってメルセンヌ素数の分布から次が予言できるようになれば、新しい数学定理が見つかるかもしれない。

    • by Anonymous Coward

      将来無関係そうな所で役に立つ可能性を否定できない以上、調べる事は未来に対する義務です。

    • by Anonymous Coward

      役に立つかどうかは知らんがメルセンヌ素数ばかり探されるのは2進数で1ばかりという特性を利用して計算機上ではほかの素数より容易に探せるからだと思う

    • by Anonymous Coward

      うまくやったらブロックチェーンのPoWとかに使えそうな気がするんだけどね。

  • by Anonymous Coward on 2019年01月06日 15時04分 (#3543996)

    ZIPファイルで公開されているM82589933のテキストファイル

    この手のはなぜかわざわざテキストファイルにする事が多いよね。
    1Bで0.42Bの情報って効率悪すぎだと思うんだが、なんで可変長整数/少数表記の標準ファイル形式とか産まれなかったんだろうね?
    圧縮すれば割と同じ事だろうけど。
    制御文字で切り替えて数字モードにする事で若干容量を小さくしたりコンピューターで処理しやすくなったりするだろうに。
    逆にファイルサイズが大きくなることもあるだろうけど、XMLとかJSONでのシリアライズで数字だけ2進数表記とかできれば処理も早くなるだろうし扱いやすい。

    • プログラムで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 です.

      親コメント
      • by Anonymous Coward

        それは交換形式であって、10進多倍長の内部形式としてはpacked BCD辺りも十分・・・
        C/C++ならビットフィールド使えば一桁1フィールドでそのまま表現可能。
        テキストだと上4ビットが邪魔で扱いにくい。

        あと、MB単位の長さを考え始めるとNULL終端文字列一つ(連続メモリ領域)で扱うのも微妙。
        そろそろストリームを考えるべき長さだと思う。

        • 短くなるようにコード化すると「このデータはどういうフォーマットなのか」という型情報が必要になってくる。
          テキスト形式なら「一目見れば誰でもわかる」とまではいかないけど、慣れてくれば見るだけで判別できることも多い。
          複数のデータ、それも型が混在しているものでも改行区切りやCSVなど見だけでも推測できるフォーマットが広く普及している。
          こういう「型情報付きでパック化したデータ」としてはMessagePack [msgpack.org]とかがあって、人間が直接目で見る必要がほとんどなくWebAPIなどでデータを頻繁にやりとりする場合はかなり有用だけど、こういう巨大ではあっても単発のデータではパック化することでテキストファイルと比べて得られるメリットって大してないと思う。

          --
          うじゃうじゃ
          親コメント
        • by Anonymous Coward

          メルセンヌ素数をプログラム内部で扱う場合、2進以外ありえるの?
          2進で扱いやすい、ビット演算を簡単にできるところにメルセンヌ素数の意義があると思うのだけど。

          • by Anonymous Coward

            多倍長演算で大きな数値を扱おうって場合、基数は2ではなく10の方が都合が良い場合がある。
            「任意精度の数値表記標準フォーマット 」みたいなことを考える場合は2以外の基数を想定するのは当然かと。

            メルセンヌ素数の美味しい応用例に関していえば基数2で扱うほうが良い場合も多々あるかもしれんが…
            …そもそもその場合メルセンヌ素数は桁数以外の情報がプログラム側に吸収されて値としては出てこない気も。

    • by Anonymous Coward on 2019年01月06日 15時20分 (#3543999)

      >圧縮すれば割と同じ事だろうけど。
      まさにこれが理由では?
      というか、情報量を考慮するなら「M82589933」という10文字足らずで表される数なんだから、10進で表すのはおまけみたいなもの。
      後半読んでると不安になってくるけど、2進表記で1が82589933個並ぶ特殊な数なのは分かってるよね。

      親コメント
      • by Anonymous Coward

        バイナリの二進数表記とBCDの二種類のイメージですね。
        わざわざテキストにするのはデコードコストと標準フォーマットによる扱いやすさでしょうから。
        やり方はテキストファイルとしてできるだけ透過的に扱える仕組みが望ましく、制御文字で4Bit単位のBCD(+小数点やマイナスや終了文字)とか数桁まとめる(3B毎なら16777216でキリが良いかな?)とか、同じく制御文字でネイティブのintやfloatが埋め込める方法とか色々考えられますね。
        どこかで標準化されていれば普通にテキストエディタで扱えて処理も軽く便利な場面が結構あった気がします。

    • by Anonymous Coward

      この手のデータをわざわざ可読テキストとして定義する需要が無いからね。
      受け渡しはバイナリで十分。
      門外漢にも広く公開しようと考えたら.txtは普及率も情報密度も圧倒的に良いでしょ。
      こんなもんのために専用ビューアをダウンロードしたい?

    • by Anonymous Coward

      すでにテキストファイルが標準ファイル形式みたいな役割をしていて、このトピみたいな特殊用途向けデータ交換形式としては割と満足されているからじゃないかなあ。
      サイズについてはおっしゃる通り圧縮で対応でき、
      テキストを数値として読み込む標準関数が普及していることで扱いも問題ないから。

    • by Anonymous Coward

      まあメルセンヌ数専用の圧縮形式作れば、82589933って情報だけあればデコードできるんだけどね。
      24.1MBのテキストファイルをヘッダ除いて8B(ASCIIコードの代わりにBCDコード使えば4B)に圧縮できるから超効率的

    • by Anonymous Coward

      なんかネタが思いっきり滑ってる感がハンパないが、
      *「メルセンヌ素数のバイナリデータ」なんてネタは皆食傷気味
      * 素で気づいてない
      どっちだろ?

      # 1111111.....

      • by Anonymous Coward

        そうだ、16進数表示すりゃいいんじゃない? FFFFFFF...
        # Base64だと///////////...

    • by Anonymous Coward

      すばらしい! ぜひ標準化すべきです [xkcd.com]!

  • by Anonymous Coward on 2019年01月06日 21時38分 (#3544070)

    観測出来る宇宙にあるすべての原子の数くらいですかね?

    そんな途方もない数の中で素数が51個だけ?
    規則性もないが100内にそれが半数もあるという驚くべき事象
    どういう数学的意味があるのでしょうか?
    それともこの素数の決まりも人間が定めただけのものなのでしょうか?

    • by Anonymous Coward

      「素数でなくメルセンヌ素数」というタイトルのコメントツリーまであるのに、どうやったらそんな誤読ができるの?
      天才?

      • by Anonymous Coward

        バカなだけだと思うけど。

        > そんな途方もない数の中で素数が51個だけ?
        「既知の」「メルセンヌ素数」がその範囲内で51個だから二段階に誤読
        > 規則性もないが100内にそれが半数もあるという驚くべき事象
        規則性がありすぎるぐらいにある特殊な素数だし
        指数関数で特殊な条件を満たす指数を数えているのだから元の指数関数(2^N)以上に増えるのは当然だし

        何も考えずに「壮大な数」と「意外と少ない数」を並べて神秘性見出してるだけでしょ

        • by Anonymous Coward

          >「既知の」「メルセンヌ素数」がその範囲内で51個だから二段階に誤読
          この場合「既知」こそが疑問の元なんじゃないの?
          その範囲でそれだけしか存在しないの?既知どうとかじゃなくて、本当に?なんで?どうして?
          っていう意味での。
          言ってみれば子供の単純な疑問みたいなもん。

          そもそも計算で導けるなら、上はともかく下は大体全部出そうなもんだしな、時間さえかければ。

        • by Anonymous Coward

          >規則性がありすぎる

          規則性は皆無だよ
          2進数で1が並ぶと思ってるようだけどそんな規則はない

          こいつ知ったかぶってバカ丸出しでワロタw

          数学の博士号も持ってない輩が粋がって突っ込み入れるとか
          自分の立場を理解してないのかな?
          笑止

    • by Anonymous Coward

      うん、まあ、あなたには数学そのものが意味のないものなんでしょうね。

    • by Anonymous Coward

      >観測出来る宇宙にあるすべての原子の数

      Wikipediaによると約10^80個だからぜんぜん足りないですね

  • by Anonymous Coward on 2019年01月07日 10時43分 (#3544156)

    > M82589933は桁数にして24,862,048桁。

    ふむふむ。

    > ZIPファイルで公開されているM82589933のテキストファイルを展開すると24.1MBとなり、

    1桁1バイトなんだから、24,862,048バイトで約24.1MBだなあ

    > 100桁ごとに改行されたテキストは248,621行におよぶ。

    24,862,048桁を100桁ごとに改行したら、248621行と48文字。

    #何ごとの不思議なけれど。

    • キリが良いのはわかるが、なぜ100桁ごとなんだ、とか思ってしまうなぁ。
      普通は80桁か136桁。で、縦は66行で1ページ。→15×11インチの連続用紙なら、2770枚か…とか。

      #いや、「一行78文字推奨だ!」ってRFC5322ネタを書こうかと思ったけど、それ以上膨らませられなかった…

      親コメント
    • by Anonymous Coward

      間違えた。

      ×24,862,048桁を100桁ごとに改行したら、248621行と48文字。
      〇24,862,048桁を100桁ごとに改行したら、248620行と48文字。

typodupeerror

私は悩みをリストアップし始めたが、そのあまりの長さにいやけがさし、何も考えないことにした。-- Robert C. Pike

読み込み中...