Confusion with Bellard's algorithm for Pi

396 Views Asked by At

I've found the following algorithm for calculating the nth digit of pi in base B:

Algorithm

It all makes sense, until you reach the $b=$ inside the second for loop. The whole line is:

$$b=\frac{k}{a^{v(n,k)}}$$ Specifically, the radical in the denominator: $$v(n,k)$$ V is a variable, not a function. What does it mean to apply it as a function to n and k? This also appears many times past that in the algorithm. I've tried researching it, but I haven't found anything.

1

There are 1 best solutions below

0
On BEST ANSWER

Shortly $\,v(p,k)\,$ is the multiplicity of the prime $p$ in $k$ (the exponent of $p$ in the multiplicative decomposition of $k$ in prime powers, another name is "p-adic valuation").
Example : $v(3,18)= 2\,$ since $\,18=2\cdot 3^2$.

In your case we are concerned with $\,a$-adic valuations since the $n$ in $\,v(n,k)$ appears to be a typo for '$a$' as you may see in this extract from Fabrice Bellard's $1997$ paper "Computation of the n'th digit of $\pi$ in any base in $O(n^2)$" (this is a .ps file) :

Bellard's 1997 paper $$-$$ This paper, details as well as c source files are available at Bellard's site "Pi Formulas, Algorithms and Computations" and the file pi.c seems to correspond to the given algorithm in the case $B=10$.

Another paper from $2010$ is available "Computation of 2700 billion decimal digits of Pi using a Desktop Computer".