New record on the computation of log(2)
Number of decimal digits computed and verified : 108 000 000.
When : 23/01/98 -> 25/01/98
Who : Xavier Gourdon
Machine : Sgi r10000, memory: 256 Mo.
Total timing: 47h40' (real timing)
Formula used:
-------------
The computation used a formula of Pascal Sebah :
log(2) = 72 LL(251) + 27 LL(449) - 19 LL(4801) + 31 LL(8749),
with LL(q) = log(1+1/q)-log(1-1/q)
= 2/q + 2/3/q^3 + 2/5/q^5 + 2/7/q^7+ ...,
A variant of the Brent binary-splitting algorithm was used to
compute the series. Thanks to this approach, the complexity of
the computation is reduced to O(N log(N)^3), where N is the number of digits.
The key of the speed was to use a fast multiplication of big numbers,
with an efficient FFT modulo two prime numbers of 59 bits.
Verification:
-------------
The verification was done thanks to another formula due to Pascal Sebah :
log(2) = 36 LL(127) + 27 LL(449) + 17 LL(4801) - 5 LL(8749)
for which the value of LL(449), LL(4801) and LL(8749) were reused.
Timing of verification: 15h20'
Statistics on the first 100 000 000 decimal digits of log(2) :
----------
Number of 0 : 10001186
Number of 1 : 10001248
Number of 2 : 10002102
Number of 3 : 9995171
Number of 4 : 9999885
Number of 5 : 9998600
Number of 6 : 9995182
Number of 7 : 10004947
Number of 8 : 9998730
Number of 9 : 10002949
Digits from rank 107999901 to rank 108000000 :
------
9245706887 1300903284 3317607704 5424313441 5393301435
3063662358 0655648631 6249090084 2079842604 6198155195