note
moritz
<p>Ever since I've read about them, I've been fascinated by [https://en.wikipedia.org/wiki/Pi#Spigot_algorithms|spigot algorithms] for producing digits of pi.
<p>The basic idea for those algorithms is that most "interesting" transcendental numbers (like pi, e, ln(2)) have a pretty simple representation if the base is allowed (in a regular pattern) for each digit. Then the task of computing the first $N first digits is just that of a base conversion. And the fascinating part is that you can work with integers only-
<p>To stay a bit on topic, I've ported [http://stackoverflow.com/questions/4084571/implementing-the-spigot-algorithm-for-pi#4085325|this C implementation] of a spigot algorithm for pi to Perl 6:
<code>
sub pi-spigot(Int $digits) {
my $len = 1 + floor 10 * $digits / 3;
my @a = 2 xx $len;
my Int $nines = 0;
my Int $predigit = 0;
join '', gather for 1 .. ($digits + 1) -> $j {
my Int $q = 0;
loop (my int $i = $len; $i > 0; $i = $i - 1) {
my int $x = 10 * @a[$i - 1] + $q * $i;
@a[$i - 1] = $x % ( 2 * $i - 1);
$q = $x div (2 * $i - 1);
}
@a[0] = $q % 10;
$q div= 10;
if $q == 9 {
++$nines;
}
elsif $q == 10 {
take $predigit + 1, 0 xx $nines;
$nines = 0;
$predigit = 0;
}
else {
take $predigit;
$predigit = $q;
take 9 xx $nines;
$nines = 0;
}
}
}
multi MAIN($n = 100) {
say pi-spigot($n.Int);
}
multi MAIN('test') {
use Test;
plan 1;
is pi-spigot(100),
'0314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706',
'it works';
}
</code>
<p>Since Rakudo is still pretty slow for this kind of stuff, I've traded a bit of readabilty for speed by using a native int in the inner loop, which means that Rakudo can inline most operators, but means I have to write <c>$i = $i - 1</c> instead of <c>$i--</c> (because native ints are value types, and you cannot (yet?) pass them as writable values to routines, so the -- operator cannot work on them).</p>
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-616540">
[http://perl6.org/|Perl 6 - the future is here, just unevenly distributed]
</div></div>
992580
992580