(* Pi Spigot from April '95 Math Monthly
                  ----------------------

  The program basically evaluates n terms of a series for pi
   by starting with the last term and multiplying by 10 and carrying the
   remainder to the next term, reading off the ones digit, and repeating
   until all numerators are zeroed.
   Check out the issue for a more detailed explanation.

   Improved output by Robert Simms, of Salsibury, MD

   Language: Pascal
*)

program pi_spigot(input, output);
const	n = 1003;
	len = 10*n div 3;
var	i, j, k, q, x, nines, predigit: integer;
	a : array[1..len] of integer;
	count : integer;

procedure list(var count: integer; digit: integer);
   begin
   count := count +1;
   write(digit:1);
   if count mod 5 = 0 then
      write(' ');
   if count mod 20 = 0 then
      writeln;
   if count mod 100 = 0 then
      writeln
   end;

begin
count := -2;
for j := 1 to len do
   a[j] := 2;
nines := 0;
predigit := 0;
for j := 1 to n do
   begin
   q := 0;
   for i := len downto 1 do
      begin
      x := 10*a[i] +q*i;
      a[i] := x mod (2*i-1);
      q := x div (2*i-1)
      end;
   a[1] := q mod 10;
   q := q div 10;
   if q = 9 then
      nines := nines +1
   else
      if q = 10 then
         begin
         list(count, predigit +1);
         for k := 1 to nines do
            list(count, 0);
         predigit := 0; nines := 0
         end
      else
         begin
         list(count, predigit);
         predigit := q;
         if nines <> 0 then
            begin
            for k := 1 to nines do
               list(count, 9);
            nines := 0
            end
         end
   end;
   list(count, predigit)
end.