http://www.amazon.co.jp/gp/pdp/profile/A1T5VY0M1619SO/ref=cm_cr_pr_pdp こけおどしの題名だけの糞本。 キャリーやボローフラグが使えない言語で1文字でも短くする伝説のコードなんて笑える。xor eax,eax まあ、アセンブリが埋め込めるわけで普通に使える…

書こう書こうと思いつつ放置しておりました。 随分前話題になった7行テトリス http://d.hatena.ne.jp/Ozy/20071104#p1 ですが、2ch(http://pc11.2ch.net/test/read.cgi/tech/1215352849/35)やら http://d.hatena.ne.jp/Ozy/20071101#p1 のコメントでscriptタ…

ちょい脱線 前回、 水さすようで申し訳ないんですが、フェルマーテストはカーマイケル数に対して高確率で false positiveになります。 ミラー・ラビン素数判定は一つの底で判定する度に1/4の確率でしか素数性を担保出来ません。 確実な素数判定となるとAKS素…

試し割の効果 最初に書いたプログラムは、あまり速くはありませんでした。理由は、大きな素数が現れた場合に4千回以上も試し割りをしなければならないからです。プログラムを実行した結果、判定する33,333,333個の整数の中に、素数は3,260,532個でありました…

すげーぜ！ミラー・ラビン フェルマーテストによって、高確率で素数判定が出来るようになりましたが、もうちょっと確率の高い判定法があります。

フェルマーテストの実装 まずは、基数を色々変えられる一般的なものを書いてみます。

フェルマーの小定理 フェルマーの小定理という、素数判定には欠かせない定理があります。 3,5,7,11という素数を使って、以下のような計算をしてみます。 2^ 3 = 8, 8 / 3 = 2 余り2 2^ 5 = 32, 32 / 5 = 6 余り2 2^ 7 = 128, 128 / 7 = 18 余り2 2^11 =2048,…