PI Spigot

by Stephen R. Schmitt

Archimedes' Constant, π

A procedure based on integer arithmetic for calculating the value of π to a large number digits, known as the spigot algorithm, was first published by Rabinowitz and Wagon [1]. A spigot algorithm produces its outputs incrementally, and does not reuse them after producing them. Their algorithm uses only bounded integer arithmetic, is efficient, and allows concise implementations.

Zeno source code

• Download Page

program

    var x : string
    var a, b, c, d, e, g, n, m : int 
    var f : array[8191] of int
    
    a := 10000
    b := 1
    c := 8190
    e := 0

    while (b ~= c)                          % init array
        f[b] := a div 5
        incr b
    end while 

    m := 0
    put 4*m, ":", tab(10)...                % count digits
    
    while (c > 0)                           % start algorithm
        g := 2*c 
        d := 0 
        b := c
        while (b > 0)
            d := d + f[b]*a
            g := g - 1
            f[b] := d mod g
            d := d div g
            g := g - 1
            b := b - 1
            if (b ~= 0) then 
                d := d*b
            end if
        end while
        c := c - 14 
        x := intstr( e + d div a, 5 )       % convert to string
        for n := 2...5 do                   % add leading zeroes
            if x[n] = ' ' then
                x[n] := '0'
            end if
        end for
        put x...                            % output four digits
        incr m                              % increment digit counter
        if (m mod 10 = 0) then              % start new line
            put ""
            put 4*m, ":", tab(10)... 
        end if
        e := d mod a
    end while

end program

Reference

[1] A spigot algorithm for the Digits of π, Stanley Rabinowitz and Stan Wagon, Am. Math. Monthly, March 1995, 195-203

AbCd Classics - free on-line books