Calculation method
The ancients calculate the circumferential rate, generally using a cutting method. That is, with a circularly connected or outer positive polygon to force the circular circumference. Archimedes Get the accuracy of 3 digits after the circumferential rate decimal point with a positive 96; Liu Hui uses a positive 3072 to get 5-bit accuracy; Ludolph Van Ceulen has obtained 35-bit precision with a positive 262. This geometric algorithm is large, slow, and it is not good. With the development of mathematics, mathematicians intentionally discover many formulas that calculate the circumferential rate during mathematical research. Some classic common formulas are selected below. In addition to these classic formulas, there are many other formulas and formulas derived from these classic formulas, not one by one.
Machin formula
This formula was discovered by John Machin, a professor of British Astronomy. He used this formula to calculate 100-bit peripheral rate. Machin formulas each calculate a 1.4-bit decimal accuracy. Because it is not more than long than long than long than long than long during its calculation, it can be easily programmed on your computer. Machin.c source program
There are many anti-fixed formulas similar to the Machin formula. In all these formulas, the Machin formula seems to be the fastest. Even so, if you want to calculate more bits, such as tens of millions, the Machin formula is not from your heart. The algorithm described below, calculating about approximately a day on the PC, and the accuracy of the annular rate can be obtained. These algorithms are more complicated. Because the calculation process involves two large number of multi-multi-multiplier operations, use FFT (FOST FOURIER TRANSFORM) algorithm. FFT can shorten the two large number of multi-multiplication operations from O (N2) to O (NLOG (N)).
For specific implementation and source procedures for FFT algorithms, please refer to Xavier Gourdon's homepage
Ramanujan formula
In 1914, Indian mathematician Srinivasa Ramanujan published a series of 14 revolutionary calculations in his paper, one of which. This formula can obtain an 8-bit decimal accuracy per calculated. In 1985, Gosper calculated from 17,500,000 bits of the circumferential rate. In 1989, David & Gregory Chudnovsky brothers improved Ramanujan formulas:
This formula is referred to as a Chudnovsky formula, each calculated a 15-bit decimal accuracy. In 1994, Chudnovsky Brothers used this formula to calculate 4,044,000,000. Another more convenient for the CHUDNOVSKY formula is:
AGM (ARITHMETIC-GeMetric Mean) algorithm
GAUSS-Legendre formula:
Initial value: Repeated calculation: Final calculation: This formula will be doubled twice an iteration once, for example, to calculate 1 million, iterate 20 times. In September 1999 Takahashi and Kanada used this algorithm to calculate 206,158,430,000 positions in the perimeter rate and create a new world record.
Borwein iterative:
Initial value: Repeated calculation: Final calculation: This formula is published by Jonathan Borwein and Peter Borwein in 1985, which converges over the circumference rate.
Bailey-borwein-plouffe algorithm
This formula is referred to as the BBP formula, which is jointly published by David Bailey, Peter Borwein and Simon Plouffe in 1995. It breaks the algorithm of the traditional circumferential rate, and can calculate any of the N-1 bits of the circumferential rate without calculating the N-1 bit in front. This provides feasibility for distributed calculations of the circumferential rate. In 1997, Fabrice Bellard found a Formula that was 40% faster than BBP: Previous Home Next Page