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


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.


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".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.