The Pi is done

When last we left the endless Pi project, it a “simple” matter of getting FatRats to work. Which in this case, meant getting the Math::FatRat module to work. Which in turn meant getting Math::BigInt to work again. Which meant getting Zavolaj to work again. Frankly, I thought I might have a month’s worth of blog posts left in the project.

Enter Niecza. As of the latest release, it has baked-in FatRats. I was worried about it lacking lazy lists, but it turns out it has them too. I ran into four holes in its implementation of Perl 6: No floor function, no bless, no MAIN, and no sub-signatures. Luckily floor’s easy to write, MAIN is easily skipped, using the default new works, and I just reverted TimToady’s sub-signature suggestion. A bit of work, and I had this, a complete and fully functional Perl 6 spigot stream for pi:

sub floor(FatRat $n) {
    my $mod = $n.numerator % $n.denominator;
    ($n.numerator - $mod) div $n.denominator;
}

sub stream(&next, &safe, &prod, &cons, $z is copy, @x) {
    my $x-list = @x.iterator.list;
    gather loop {
        my $y = next($z);
        if safe($z, $y) {
            take $y;
            $z = prod($z, $y);
        } else {
            $z = cons($z, $x-list.shift);
        }
    }
}

sub convert($m, $n, @x) {
    stream(-> $u { floor($u.key * $u.value * $n); },
           -> $u, $y { $y == floor(($u.key + 1) * $u.value * $n); },
           -> $u, $y { $u.key - $y / ($u.value * $n) => $u.value * $n; },
           -> $u, $x { $x + $u.key * $m => $u.value / $m; },
           0/1 => 1/1,
           @x);
}

class LFT {
    has $.q;
    has $.r; 
    has $.s; 
    has $.t;
    # method new($q, $r, $s, $t) { self.bless(*, :$q, :$r, :$s, :$t); }
    method extr($x) { ($.q * $x + $.r) / ($.s * $x + $.t); }
}

sub unit() { LFT.new(q => FatRat.new(1, 1), 
                     r => FatRat.new(0, 1), 
                     s => FatRat.new(0, 1), 
                     t => FatRat.new(1, 1)); }    
sub comp($a, $b) { 
    LFT.new(q => $a.q * $b.q + $a.r * $b.s,
            r => $a.q * $b.r + $a.r * $b.t,
            s => $a.s * $b.q + $a.t * $b.s,
            t => $a.s * $b.r + $a.t * $b.t);
}

sub pi-stream() {
    stream(-> $z { floor($z.extr(3)); },
           -> $z, $n { $n == floor($z.extr(4)); },
           -> $z, $n { comp(LFT.new(q => 10, r => -10*$n, s => 0, t => 1), $z); },
           &comp,
           unit, 
           (1..*).map({ LFT.new(q => $_, r => 4 * $_ + 2, s => 0, t => 2 * $_ + 1) }));
}

my @pi := pi-stream;
say pi;
say @pi[0] ~ '.' ~ @pi[1..100].join('');

Certainly not as elegant as it might ideally be in the long run, but it works today, calculating 101 digits of pi in 5.7 seconds.

Advertisements