## Monday, March 14, 2016

Happy pi day. Here's how you can display as many digits of pi as you want (subject to your computer's resources).

We're going to be using Gibbon's unbounded spigot algorithm which spits out consecutive digits of pi in decimal without iterative approximations. It's really cool when you see it in action.

In the above linked paper, the algorithm is given in Haskell. I won't explain the mathematical derivation in this post, but here is a translation into Python 3:
def gibbons():
(q, r, t, k, n, l) = (1, 0, 1, 1, 3, 3)
while True:
if 4*q + r - t < n*t:
yield n
(q, r, n) = (
10*q,
10*(r - n*t),
10*(3*q + r)//t - 10*n
)
else:
(q, r, t, k, n, l) = (
q*k,
(2*q + r)*l,
t*l,
k+1,
(q*(7*k + 2) + r*l)//(t*l),
l + 2
)

To use this code run this:
digit_seq = gibbons()
print(next(digit_seq))
print(next(digit_seq))
print(next(digit_seq))
print(next(digit_seq))

This will output
3
1
4
1

If you want it to print out a thousand digits, do this:
digit_seq = gibbons()
for (position, digit) in enumerate(digit_seq):
if position == 1000:
break
print(digit, end='')

Now this code will let you print as many digits as you want; however being in Python it's not something you can just tell your non-geek friend to try out. So for pi day, here's a javascript implementation that anyone can just paste in their browser's web console and get a nice stream of pi digits. One thing you should keep in mind is that in Python you can have numbers which are as big as you like. Javascript is not like that, so we'll need to use an external library called bignumber.js. This is the full code we'll be using to generate the digits:
var script = document.createElement('script');
script.src = "https://cdnjs.cloudflare.com/ajax/libs/bignumber.js/2.3.0/bignumber.min.js";

function gibbons() {
var q=new BigNumber(1), r=new BigNumber(0), t=new BigNumber(1), k=new BigNumber(1), n=new BigNumber(3), l=new BigNumber(3);
function f() {
while (true) {
var digit = n.toString();
var q_ = q.mul(10);
var r_ = r.sub(n.mul(t)).mul(10);
var n_ = q.mul(3).add(r).mul(10).divToInt(t).sub(n.mul(10));
q=q_, r=r_, n=n_;
return digit;
}
else {
var q_ = q.mul(k);
var r_ = q.mul(2).add(r).mul(l);
var t_ = t.mul(l);
var k_ = k.add(1);
var l_ = l.add(2);
q=q_, r=r_, t=t_, k=k_, n=n_, l=l_;
}
}
}
return f;
}

function show_digits(max_num_digits) {
var get_digit = gibbons();
var num_digits = 0;
function f() {
var digits = '';
for (var i = 1; i <= 50; i++) {
digits += get_digit();
num_digits++;
if (num_digits >= max_num_digits) {
break;
}
}
console.log(digits);
if (num_digits < max_num_digits) {
setTimeout(f, 100);
}
else {
console.log('\n'+max_num_digits+' digits of pi displayed!');
}
}
f();
}

show_digits(1000);

The first line is to import the bignumber library in a way that works in the web console. After that there are two functions. The first is for the Gibbons algorithm which lets us get the digits of pi. The way it works is by returning a function which returns the next digit each time it is called. The second function outputs 50 digits of pi every 100 milliseconds.
The code to copy-paste
But this is not something you'll send you friend. Instead send them this minified code (of course you shouldn't trust obscure code sent by strangers as it might be evil code, but you can minify the above code youself if you don't trust me).
var script=document.createElement("script");script.src="https://cdnjs.cloudflare.com/ajax/libs/bignumber.js/2.3.0/bignumber.min.js",document.getElementsByTagName("head")[0].appendChild(script);