Geeky is Awesome: March 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

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";
document.getElementsByTagName('head')[0].appendChild(script);
 
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) {
            if (q.mul(4).add(r).sub(t).lt(n.mul(t))) {
                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 n_ = (q.mul(k.mul(7).add(2)).add(r.mul(l))).divToInt(t.mul(l));
                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);
 
function gibbons(){function u(){for(;;){if(n.mul(4).add(i).sub(m).lt(d.mul(m))){var u=d.toString(),e=n.mul(10),r=i.sub(d.mul(m)).mul(10),t=n.mul(3).add(i).mul(10).divToInt(m).sub(d.mul(10));return n=e,i=r,d=t,u}var e=n.mul(l),r=n.mul(2).add(i).mul(o),a=m.mul(o),b=l.add(1),t=n.mul(l.mul(7).add(2)).add(i.mul(o)).divToInt(m.mul(o)),g=o.add(2);n=e,i=r,m=a,l=b,d=t,o=g}}var n=new BigNumber(1),i=new BigNumber(0),m=new BigNumber(1),l=new BigNumber(1),d=new BigNumber(3),o=new BigNumber(3);return u}function show_digits(u){function n(){for(var l="",d=1;50>=d&&(l+=i(),m++,!(m>=u));d++);console.log(l),u>m?setTimeout(n,100):console.log("\n"+u+" digits of pi displayed!")}var i=gibbons(),m=0;n()}
 
show_digits(1000);

What you have to do is open your browser's web console on any web page by pressing F12 (even a blank tab works, although Facebook will block it), then paste the first line of code at the bottom. After pressing enter, paste the second line of code. Finally paste the "show_digits(1000);" line and press enter. You'll see a stream of digits displayed in the console panel. I think this is a nice way to celebrate pi day. Maybe someone else can make the digits somehow interact with the web page you are on instead of just display them in the console. Until then, enjoy your pie today!

Geeky is Awesome

Monday, March 14, 2016

Displaying the digits of pi in your web browser