« ゴスロリ用語辞典 | メイン | サイトを都市として表現するログ解析 »
2004年07月24日
グーグル、人材募集広告 を解く 第三回
続き、グーグルの人材募集広告を解く。
やっと、ネピア数の計算プログラム製作です。
とりあえず、前回でアルゴリズムは作ったので、
そのまま、perlで実装。
code:
$M = 1000000;
$N_MAX = 10000;
$X_MAX = 1000;
$M_LEN = length($M)-1;
@a = (1*$M);
@ans = (1*$M);
for($n = 1; $n <= $N_MAX; $n++){
$tmp_mod = 0;
for($x = 0; $x <= $X_MAX; $x++){
$tmp_a = int(($tmp_mod*$M + $a[$x]) / $n);
$tmp_mod = ($tmp_mod*$M + $a[$x]) % $n;
$a[$x] = $tmp_a;
$ans[$x] = $ans[$x] + $a[$x];
}
}
$tmp_adv = 0;
for($x = $X_MAX; $x >= 0; $x--){
$ans[$x]+= $tmp_adv;
$tmp_adv = int($ans[$x] / $M);
$ans[$x] = $ans[$x] - $tmp_adv * $M;
}
print "e = ".$tmp_adv.".";
for($x = 0; $x <= $X_MAX; $x++){
printf("%0".$M_LEN."d", $ans[$x]);
}
exit;
$N_MAX = 10000;
$X_MAX = 1000;
$M_LEN = length($M)-1;
@a = (1*$M);
@ans = (1*$M);
for($n = 1; $n <= $N_MAX; $n++){
$tmp_mod = 0;
for($x = 0; $x <= $X_MAX; $x++){
$tmp_a = int(($tmp_mod*$M + $a[$x]) / $n);
$tmp_mod = ($tmp_mod*$M + $a[$x]) % $n;
$a[$x] = $tmp_a;
$ans[$x] = $ans[$x] + $a[$x];
}
}
$tmp_adv = 0;
for($x = $X_MAX; $x >= 0; $x--){
$ans[$x]+= $tmp_adv;
$tmp_adv = int($ans[$x] / $M);
$ans[$x] = $ans[$x] - $tmp_adv * $M;
}
print "e = ".$tmp_adv.".";
for($x = 0; $x <= $X_MAX; $x++){
printf("%0".$M_LEN."d", $ans[$x]);
}
exit;
ans.
2.718281828459045235360287471352662497757247093699
95957496696762772407663035354759457138217852516642
74274663919320030599218174135966290435729003342952
60595630738132328627943490763233829880753195251019
01157383418793070215408914993488416750924476146066
80822648001684774118537423454424371075390777449920
69551702761838606261331384583000752044933826560297
60673711320070932870912744374704723069697720931014
16928368190255151086574637721112523897844250569536
96770785449969967946864454905987931636889230098793
12773617821542499922957635148220826989519366803318
25288693984964651058209392398294887933203625094431
17301238197068416140397019837679320683282376464804
29531180232878250981945581530175671736133206981125
09961818815930416903515988885193458072738667385894
22879228499892086805825749279610484198444363463244
96848756023362482704197862320900216099023530436994
18491463140934317381436405462531520961836908887070
16768396424378140592714563549061303107208510383750
51011574770417189861068739696552126715468895703503
54021234078498193343210681701210056278802351930332
24745015853904730419957777093503660416997329725088
68769664035557071622684471625607988265178713419512
46652010305921236677194325278675398558944896970964
09754591856956380236370162112047742722836489613422
5164450781824423529486363721417402...値が間違えてたら意味ないので、NASAの出してるネピア数と照合。
6003桁目の値が間違っているみたいで、有効なデータは6002桁までとなった。
ま、かなり十分かな。とりあえず、答えもちゃんと含まれてるみたいだし。
次は素数判定です。
で、一応素数判定についてウィキペディアで調べると。
素数判定は基本的に時間が掛かる処理で、
擬似素数判定法という方法で行う方がいいみたい。
・フェルマーテスト
・ラビン・ミラーの強擬似素数判定法
・ルーカステスト
・AKS素数判定法
など。。
この中でAKS素数判定法が
「決定的多項式時間で判定することが出来る、
世界初のアルゴリズムである」と書かれてるので、
これを使用することに決定。
次回からは、ASK素数判定法のプログラミングを行っていきます。
投稿者 wizkid : 2004年07月24日 19:11
トラックバック
このエントリーのトラックバックURL:
http://www.wizkidjp.com/sns_blog/mt-tb.cgi/5

主婦と生活社: ロリィタ雑誌「FRiLL」 [book]
深田恭子in下妻物語[book]