素数生成とグラボを使った多倍長演算
かなり昔の話ですが、素数を600億まで計算しました。アルゴリズムはエラトステネスの篩です。7以上の素数は30で割って1,7,11,13,17,19,23,29余るという性質を利用して8個にスレッドを分けています。この8個という数字、私のコンピュータのロジックコア数に相当するのでそれなりに効率よく処理を配分できていると思います。
タイムはintel Core i7 4770K 3.5~3.9GHzの8logic coreで、90秒でした。
篩処理は配列の要素を1に書き換えていくという方法を取っているのでgccのコンパイルの最適化オプションの-O3にかなり恩恵を受けています（タイムが半分ぐらいになった）
部活のi5のデスクトップで300億まで計算させてみたところ、こちらは60秒でした。（私のだと45秒だった）シングルロジックコアに割り当てられるキャッシュ量が部活のPCの方が多いのが原因かも知れません。
知っての通りC++のスタンダードライブラリに多倍長演算をサポートするものはありません。私はGMPという素晴らしいライブラリ（とにかく演算がめちゃくちゃ速い。FFTを使ってるんでしょううが8000万bit同士の演算が0.3秒で終わる）を使っていますが、それでももっと早くしたいなと思うことがあります。
掛け算とかの簡単な処理はグラボで処理させたほうが速いと思って調べてみてるところなのですが、積表を用いて演算する方式が取られているものがありました。コンピュータで演算させることを考えたらビット演算でやるのが良さそうなきがしますがどうでしょうね。
レピュニット素数
10進で1を並べて作った数のうち、素数になるものです。
超レアです。
2、19、23、317、1031、、、、というふうになるらしいです。
ミラーラビンで1から判定してみたのですが、確かにめちゃくちゃレアです。
1031の次は5万弱というのだから笑えませんね
メルセンヌ素数みたいに専用のアルゴリズムがあるわけではないでしょうし劇的な高速化も不可能な気がします。実際Wikipediaに載っているものもprobably primeなので私どうようミラーラビン判定法が使われていると考えられます。私が探したとき1031まで程度ならばそこまで時間はかかりませんでした
それと、ノートパソコンに入っていたWindows10を消してlinux mintを入れました。この先数カ月は動画を作る用事がなさそうなので持ち運びに便利なノートパソコンで開発をおこなえるようにしたかったのが理由です。 デスクトップのほうが使いやすいっちゃ使いやすいのですが、たまにはノートでやるのも悪くないですね。（ちなみにデスクトップのドライブの容量は128GBでノートが240なのでノートパソコンの方がでかい）
ただ、3月中旬から下旬にかけて動画をつくる用事が出てきそうなのでそれまでに500GB程度のSSDを買いたいなと思っています。
パソコン甲子園について
当方今高校1年で、ぱそこんをいじる部活の部長をしています。部活で先日（9月上旬だったかな？）会津大学主催のパソコン甲子園に出場しました。私を含め、出場者全員（4人）人生初の競プロだったのですが、私ともう一人の古参のチームがブロックの新人賞をいただきました。（予選落ちしましたが）
当初の予定としては、前半（1〜4までぐらい）をそいつが考えてる間に私が5番以降のアルゴリズムを考えるというイメージで行こうと思っていたのですが、案外6番以降が難しくて1番から5番までしか解けませんでした。（9番が解けそうだったらしいですがなんかコンパイラがへんな挙動を見せたらしい）
1から5番程度ならどちらか片方だけしかいなくても余裕で解けていたと思うのでちょっと不甲斐ない結果でした。
また、パートナーの実装力にとても助けられたと感じたコンテストでもありました。9番がおしいところまで行ったのはひとえに彼のおかげです。
来年はぜひ会津で本選に臨みたいです。
リュカレーマーテストとミラーラビンテスト
※リュカレーマーテストもミラーラビンテストもWiki見ればわかるので説明は省略します。
少し前にリュカレーマーテストを使って下から順にメルセンヌ素数を探すプログラムを組んだのですが、7~8時間かかって28番目が出ないという感じでした。
リュカレーマーテストは指数の二乗に比例して実行時間が伸びる気がするので、「リュカレーマーテストで全部の候補をテストするの効率悪すぎやろ」ってなって「これ確率的な方法である程度目星つけてからやってんのとちゃうか？」と思い、確率的素数判定アルゴリズムとして非常に有名なミラーラビンテストを実装して試しにサクッと組んで実装してみました。
2の9941乗-1を判定した（擬素数対策に100回判定）（乱数は64bit）
ちなみにリュカレーマー
ミラーラビンで一回しか判定しなくても0.4秒かかるのでリュカレーマーテストの方が速い
やはり任意の数を判定できるアルゴリズムなのでメルセンヌ素数に特化したアルゴリズムにはかなわないようです。
それにしても離散演算するとは言えGIMPSはどうやって49番目とか見つけたんでしょうね
どうもよろしく
ブログを書いた経験が全く無いので拙い文章が膨大に発生しそうですがどうぞよろしく（いきなり拙い日本語が露呈している）
