2008年10月04日

PHPからGMPを使ってメルセンヌ素数を探す

javaのBigDecimalは遅かったのでPHPのGMPライブラリを使ってメルソンヌ素数をさがしてみました。
PHPのインストール時にGMPを有効にし、大きな数を確認する場合はphp.iniで使用メモリの制限を広げてください。
手元のPCでは5時間程度で26番目のメルセンヌ素数が出てきました。
初期値を変えれば見つかっている最大素数1300万桁の計算もできますが、GMPのライブラリだけでは現実的な時間ではIsMersenne()は戻ってきません。


//メルセンヌ素数をLucas-Lehmerテストによって確認する

// Lucas-Lehmerテストによって素数を判別する
function IsMersenne($sosu)
{
$worknumber = gmp_init(4);
$merse = gmp_sub(gmp_pow(2, $sosu), 1);

for ($i = 2; $i < $sosu; $i++){
$worknumber = gmp_mod(gmp_sub(gmp_mul($worknumber,$worknumber), 2), $merse);
}
if (gmp_scan1($worknumber, 0) < 0) {
echo date("H:i:s: ")." 2^".$sosu."-1=".gmp_strval($merse)."\n";
}
}

//ここでは初期値2から
$fromprime = 2;
$fromprime = gmp_intval(gmp_nextprime($fromprime));
echo "メルセンヌ素数探索 2^".$fromprime."-1より開始\n";
while(true)
{
IsMersenne($fromprime);
$fromprime = gmp_intval(gmp_nextprime($fromprime));
}
?>

C:\home\php>php -f Mersenne.php
メルセンヌ素数探索 2^3-1より開始
10:16:09: 2^3-1=7
10:16:09: 2^5-1=31
10:16:09: 2^7-1=127
10:16:09: 2^13-1=8191
10:16:09: 2^17-1=131071
10:16:09: 2^19-1=524287
10:16:09: 2^31-1=2147483647
10:16:09: 2^61-1=2305843009213693951
10:16:09: 2^89-1=618970019642690137449562111
10:16:09: 2^107-1=162259276829213363391578010288127
10:16:09: 2^127-1=170141183460469231731687303715884105727
10:16:09: 2^521-1=6864797660130609714981900799081393217269435300143305409394463
45918554318339765605212255964066145455497729631139148085803712198799971664381257
4028291115057151
10:16:09: 2^607-1=5311379928167670986895882065524686273295931177270319231994441
38200403559860852242739162502265229285668889329486246501015346579337652707239409
519978766587351943831270835393219031728127
10:16:10: 2^1279-1=104079321946643990819252403273640855386152622472667048053191
12350403608059673360298012239441732324184842421613954281007791383566248323464908
13990660567732076292412950938922034577318334966158355047295942054768981121169367
71475484788669625013844382602917323488853111608285384165850282556046662248318909
18801847068222203140521026698435488732958028878050869736186900714720710555703168
729087
10:16:13: 2^2203-1=147597991521418023508489862273738173631206614533316977514777
12164785702978780789493774073370493892893827485075314964804772812648387602591918
14463365330269540496961201113430156902396093989090226259326935025281409614983499
38822283144859860183431853623092377264139020949023183644689960821079548296376309
42366309454108327937699053999824571863229447296364188906233721717237421056364403
68218459649632948538696905872650486914434637457507280441823676813517852099348660
84717257940842231667809767022401199028017047489448742692474210882353680848507250
22405194525875428753499765585726702296339625752126374778977855015526465226099888
69914013540483809865681250419497686697771007
10:16:13: 2^2281-1=446087557183758429571151706402101809886208632412859901111991
21996340468579282047336911254526900398902615324593112431670239575870569367936479
09034974611470710652541933539381249782263079473124107988748690400702793284288103
11754844108094878252494866760969586998128982645877596028979171536962503068429617
33170218475032458300917183210491605015762888660637214550170222592512522407682960
54271735739648129952505694124807207384768552936816667128448311908776206067866638
62190240118570736831901886479225810414714078935386562497968178729127629594924411
96096138671394627989927500695491713975879606122380339353738103466649440295105205
9047968693255388647930440925104186817009640171764133172418132836351
10:16:23: 2^3217-1=259117086013202627776246767922441530941818887553125427303974
92316187401926658636208620120951680048340655069524173319417744168950923880701741
03777095975120423130666240829163535179523111861548622656045476911275958487756105
68757931191017711408826252153849035830401185072116424747461823031471398340229288
07454567790794103728823582070589235106843388298688861665865028092769208033960586
93087905004095037098759021190183719916209940025689351131365488297391126567973032
41986517250116412703509705427773477972349821676443446668383119322540099648994051
79024162405651905448369080961606162574304236172186333941585242643120873726659196
20617535357488928945996291951830826218608534009379328394202618665861425032514507
73096274235376822938649407127700846077124211823080804139298087057504713825264571
44837937112503208182612656664908425169945395188778961365024840573937859459944433
52311882801236604062624686092121503499375847822922371443396288584859382157388212
32393687046160677362909315071


yamama009ma at 10:26│Comments(0)TrackBack(1)コンピュータ 

トラックバックURL

この記事へのトラックバック

1. GMP(GNU MP)メモ  [ テキトーな備忘録 ]   2009年04月01日 13:54
高速な多倍長演算ライブラリであるGMP(GNU MP)についてのまとめメモ。 本家(最新バージョンは4.2.4) GMPの使い方(studio kamadaさん) Windows璮..

この記事にコメントする

名前:
URL:
  情報を記憶: 評価: 顔