円周率の99901桁から100000桁までを簡単に求めるには?
http://worldrecord314.com/pi
上記ページには円周率10万桁が載っているのですが、
9万9901桁から10万桁までを簡単に求めるには
どうすればよいでしょうか?
参考までにRubyのコードと実行結果を記しておきます。
require 'benchmark'
require 'bigdecimal/math'
include BigMath
puts Benchmark::CAPTION
puts Benchmark.measure{
N = 100000
M = N * 2
p BigDecimal(PI(M).to_s).to_s("F")[N - 98..N + 1] # 3.と続くのでN + 1
}
実行結果
user system total real
"8575016363411314627530499019135646823804329970695770150789337728658035712790913767420805655493624646"
118.047000 7.266000 125.313000 (125.424243)
(追記)
https://stackoverflow.com/questions/28284996/python-pi-calculation
上記記事のPythonのコードをいじってみたものの、
Nが10000位で速度がかなり遅くなってしまった。
なお、N = 1000 ならすぐ求まります。
from decimal import Decimal, getcontext
def power(a, n):
p = 1
for i in format (n, 'b'):
p *= p
if i == '1':
p *= a
return p
N = 1000
getcontext().prec = N + 1
s = 0
for k in range(N):
s += (Decimal(4) / (8 * k + 1) - Decimal(2) / (8 * k + 4) - Decimal(1) / (8 * k + 5) - Decimal(1) / (8 * k + 6)) / power(Decimal(16), k)
print str(s)[N - 98:]
実行結果
5982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989
また、
π = 2 + 1 / 3( 2 + 2 / 5( 2 + 3 / 7( 2 + ・・・ ( 2 + k / (2k + 1)( 2 + ・・・))・・・)))
(例えば次を参照してください。http://xn--w6q13e505b.jp/formula/arctan.html)
という式を利用した
http://d.hatena.ne.jp/htz/20110613/1307958164
に載っているRubyのコード
(ちなみに、len = 31, 32 のときを比較するとわかるように必ずしも末尾は正しくありません。)
をいじるとさらに速く求まりました。
require 'benchmark'
puts Benchmark::CAPTION
puts Benchmark.measure{
N = 10 ** 5
B = 10 ** N
B2 = B << 1
# (i >> 1) / iの部分がk / (2k + 1)にあたる
p ((N * 8 + 1).step(3, -2).inject(B){|a, i| (i >> 1) * (a + B2) / i} - B).to_s[-100..-1]
}
実行結果
user system total real
"8575016363411314627530499019135646823804329970695770150789337728658035712790913767420805655493624646"
76.547000 7.875000 84.422000 ( 84.476262)