Digits of $\pi$ using Integer Arithmetic

Question

How can I compute the first few decimal digits of $\pi$ using only integer arithmetic? By 'integer arithmetic' I mean the operations of addition, subtraction, and multiplication with both operands as integers, integer division, and exponentiation with a positive integer exponent. The first hundred decimal digits or so would be sufficient if the method is not a completely general one.

By 'compute', I mean that I would like to obtain subsequent digits of $\pi$ one-by-one, printing them to the screen as I go along.

(Context: I'm writing a Befunge-98 program...)

Answer 1

The (or rather a) spigot algorithm for $\pi$ does exactly that: extract digits of $\pi$ one by one based entirely on integer arithmetic. See this paper.

Answer 2

If you are willing to start with the beginning of the continued fraction for $\pi$ as input data

3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13, 1, 4, 2, 6, 6, 99, 1, 2, 2, 6, 3, 5, 1, 1, 6, 8, 1, 7, 1, 2, 3, 7, 1, 2, 1, 1, 12, 1, 1, 1, 3, 1, 1, 8, 1, 1, 2, 1, 6, 1, 1, 5, 2, 2, 3, 1, 2, 4, 4, 16, 1, 161, 45, 1, 22, 1, 2, 2, 1, 4, 1, 2, 24, 1, 2, 1, 3, 1, 2, 1

(see http://oeis.org/A001203) you can compute the approximations $P_n/Q_n$ with integer arithmetic. You can use the value of $Q_n$ to estimate the number of correct decimal digits you will get when you compute its decimal expansion (Theorem 5 on the wikipedia page https://en.wikipedia.org/wiki/Continued_fraction).

That page has formulas for $P_n$ and $Q_n$ - it calls them $h_n$ and $k_n$.

This algorithm is probably not a good one for producing the digits one at a time without deciding in advance how many you want. In that respect it's like the sieve of Eratosthenes for listing primes.

Answer 3

I believe what you're looking for is this paper by Simon Plouffe

http://arxiv.org/abs/0912.0303

And it is about decimal digits.