Computation of 2700 billion decimal digits of Pi using a Desktop...
需积分: 0 57 浏览量
2010-06-27
21:25:15
上传
评论
收藏 139KB PDF 举报
Computation of 2700 billion decimal digits of Pi using a
Desktop Computer
Fabrice Bellard
Jan 6, 2010
This article describes some of the methods used to get the world record of the
computation of the digits of π digits using an inexpensive desktop computer.
1 Notations
We assume that numbers are represented in base B with B = 2
64
. A digit in
base B is called a limb. M(n) is the time needed to multiply n limb numbers. We
assume that M(Cn) is approximately CM(n), which means M(n) is mostly linear,
which is the case when handling very large numbers with the Sch¨onhage-Strassen
multiplication [5].
log(n) means the natural logarithm of n. log
2
(n) is log(n)/ log(2).
SI and binary prefixes are used (i.e. 1 TB = 10
12
bytes, 1 GiB = 2
30
bytes).
2 Evaluation of the Chudnovsky series
2.1 Introduction
The digits of π were computed using the Chudnovsky series [10]
1
π
=
12
C
3/2
∞
X
n=0
(−1)
n
(6n)!(U + V n)
(n!)
3
(3n)!C
3n
with
U = 13591409 V = 545140134 C = 640320 .
It was evaluated with the binary splitting algorithm. The asymptotic running
time is O (log(n)
2
M(n)) for a n limb result. It is worst than the asymptotic running
time of the Arithmetic-Geometric Mean algorithms of O(log(n)M(n)) but it has
better locality and m any improvements can reduce its constant factor.
Let S(a, b) defined as
b−1
X
n=a
a
n
Q
n
k=a
g(k)
Q
n
k=a
q(k)
1
剩余10页未读，继续阅读
评论0
最新资源