割り算無しで円周率の計算
2009年7月2日
割り算は少し面倒なので、これを行わずに円周率を計算させる方法を考えてみた。
実行結果は、次のとおり。
ただ、2進数の数値を10進数で表示させるときに、割り算は必要になるのだけれど…。ただしこの場合、10で割るだけだから何か方法を考えてみよう。掛け算して、右シフトとか。
ちなみに、Wikipediaに載っている収束の早い方法で円周率を求めるスクリプトは、次の通り。
実行結果:
1秒以内に40桁以上。速い。これは、先日作った、pi calculatorに入れてみたいアルゴリズムだ。
for ($max=2;$max<=2000000000;$max=$max*sqrt(10)) { $t=time(); echo intval($max).': '.calc_pi(intval($max))." (".(time()-$t).")\n"; } function calc_pi($max) { $total=0; $max2=$max*$max; $prev_y=$max-1; for ($x=0;$x<$max;$x++) { $max2_x2=$max2-$x*$x; for ($y=$prev_y;0<=$y;$y--) { if ($y*$y < $max2_x2) break; } $total+=$y+1; $prev_y=$y; } return $total; }
実行結果は、次のとおり。
2: 4 (0) 6: 33 (0) 20: 331 (0) 63: 3175 (0) 200: 31602 (0) 632: 314319 (0) 2000: 3143579 (0) 6324: 31416676 (0) 20000: 314179205 (0) 63245: 3141600733 (0) 200000: 31416126094 (1) 632455: 314159368708 (0) 2000000: 3141594652558 (3) 6324555: 31415929675774 (8) 20000000: 3.1415928535658E+14 (24) 63245553: 3.1415926966214E+15 (76) 200000000: 3.1415926756486E+16 (242) 632455532: 3.1415926602871E+17 (757)
ただ、2進数の数値を10進数で表示させるときに、割り算は必要になるのだけれど…。ただしこの場合、10で割るだけだから何か方法を考えてみよう。掛け算して、右シフトとか。
ちなみに、Wikipediaに載っている収束の早い方法で円周率を求めるスクリプトは、次の通り。
$prev=''; for ($max=1;$max<=1073741824;$max++) { $t=time(); $pi=calc_pi($max); echo "$max: ".$pi." (".(time()-$t).")\n"; if ($pi===$prev) exit; $prev=$pi; } function calc_pi($max) { $fig=50; $pi='0'; for($n=0;$n<$max;$n++){ $y=bcdiv('3',bcadd('1',bcmul('2',$n,$fig),$fig),$fig);//$y=3/(2*$n+1); for($x=1;$x<=$n;$x++) $y=bcmul($y,bcdiv(bcadd($x,$n,$fig),bcmul('16',$x,$fig),$fig),$fig);//$y*=($x+$n)/(16*$x); $pi=bcadd($pi,$y,$fig);//$pi+=$y; } return $pi; }
実行結果:
1: 3.00000000000000000000000000000000000000000000000000 (0) 2: 3.12500000000000000000000000000000000000000000000000 (0) 3: 3.13906250000000000000000000000000000000000000000000 (0) 4: 3.14115513392857142857142857142857142857142857142857 (0) 5: 3.14151117234002976190476190476190476190476190476190 (0) 6: 3.14157671577486640963203463203463203463203463203462 (0) 7: 3.14158942531912159292530386280386280386280386280385 (0) 8: 3.14159198235838245718311636280386280386280386280384 (0) 9: 3.14159251115786195576584413164577456856868621574501 (0) 10: 3.14159262287061749311263384304585680541079147890290 (0) 11: 3.14159264687556079607822377507885066701793433604575 (0) 12: 3.14159265210588688135876980275995259042146694474140 (0) 13: 3.14159265325873792265602348969466213937166225724139 (0) 14: 3.14159265351533760243194355890199599553044860706777 (0) 15: 3.14159265357293032612549212123332185179268852363902 (0) 16: 3.14159265358595061661642608384639847682401749402515 (0) 17: 3.14159265358891285600131896691248906315335157085779 (0) 18: 3.14159265358959056160849298995008835905936938801550 (0) 19: 3.14159265358974637793146374412070756654526875476065 (0) 20: 3.14159265358978236182926181471105468109455961729002 (0) 21: 3.14159265358979070504702871491957876055027172123928 (0) 22: 3.14159265358979264648516079676489008081121469559402 (0) 23: 3.14159265358979309973252269314519066555395251877355 (0) 24: 3.14159265358979320586410315569955105918300479582472 (0) 25: 3.14159265358979323078381629789582891946431607133556 (0) 26: 3.14159265358979323664972132283830569814426002942394 (0) 27: 3.14159265358979323803372159223919304405740718426681 (0) 28: 3.14159265358979323836096542698221430286801580025617 (0) 29: 3.14159265358979323843849617573672865968992142865277 (0) 30: 3.14159265358979323845689896669986550549021156502481 (0) 31: 3.14159265358979323846127465763857311206335432217720 (0) 32: 3.14159265358979323846231676887659993003945930165518 (0) 33: 3.14159265358979323846256533495254514882234155307033 (0) 34: 3.14159265358979323846262470806826589448932920075401 (0) 35: 3.14159265358979323846263890915077177829682640612762 (0) 36: 3.14159265358979323846264231012430349423281705978877 (0) 37: 3.14159265358979323846264312558794378057382395120362 (0) 38: 3.14159265358979323846264332133595004570496024509324 (0) 39: 3.14159265358979323846264336837467762778641281058918 (0) 40: 3.14159265358979323846264337968969774439469471016827 (0) 41: 3.14159265358979323846264338241412060503328604254763 (0) 42: 3.14159265358979323846264338307070811563605557427481 (0) 43: 3.14159265358979323846264338322908456383432165635004 (0) 44: 3.14159265358979323846264338326731865359081966634046 (0) 45: 3.14159265358979323846264338327655619908899808301619 (0) 46: 3.14159265358979323846264338327878973382315776673073 (0) 47: 3.14159265358979323846264338327933017039204440595583 (0) 48: 3.14159265358979323846264338327946102805957801577268 (1) 49: 3.14159265358979323846264338327949273420351838380846 (0) 50: 3.14159265358979323846264338327950042135844352612057 (0) 51: 3.14159265358979323846264338327950228625461732116515 (0) 52: 3.14159265358979323846264338327950273894369663020878 (0) 53: 3.14159265358979323846264338327950284889283679480685 (0) 54: 3.14159265358979323846264338327950287561187378816546 (0) 55: 3.14159265358979323846264338327950288210835387941934 (0) 56: 3.14159265358979323846264338327950288368871178204397 (0) 57: 3.14159265358979323846264338327950288407334337413938 (0) 58: 3.14159265358979323846264338327950288416700013995681 (0) 59: 3.14159265358979323846264338327950288418981569271129 (0) 60: 3.14159265358979323846264338327950288419537619160133 (0) 61: 3.14159265358979323846264338327950288419673194616024 (0) 62: 3.14159265358979323846264338327950288419706264059075 (0) 63: 3.14159265358979323846264338327950288419714333536557 (0) 64: 3.14159265358979323846264338327950288419716303377602 (0) 65: 3.14159265358979323846264338327950288419716784415123 (0) 66: 3.14159265358979323846264338327950288419716901927533 (0) 67: 3.14159265358979323846264338327950288419716930644645 (0) 68: 3.14159265358979323846264338327950288419716937664780 (1) 69: 3.14159265358979323846264338327950288419716939381476 (0) 70: 3.14159265358979323846264338327950288419716939801409 (0) 71: 3.14159265358979323846264338327950288419716939904164 (0) 72: 3.14159265358979323846264338327950288419716939929315 (0) 73: 3.14159265358979323846264338327950288419716939935472 (0) 74: 3.14159265358979323846264338327950288419716939936980 (0) 75: 3.14159265358979323846264338327950288419716939937349 (0) 76: 3.14159265358979323846264338327950288419716939937439 (0) 77: 3.14159265358979323846264338327950288419716939937461 (0) 78: 3.14159265358979323846264338327950288419716939937466 (0) 79: 3.14159265358979323846264338327950288419716939937467 (0) 80: 3.14159265358979323846264338327950288419716939937467 (0)
1秒以内に40桁以上。速い。これは、先日作った、pi calculatorに入れてみたいアルゴリズムだ。