Wednesday, March 3, 2010

Lazy Sieve of Eratosthenes, sidetracked

A Hacker News article about the Sieve of Eratosthenes got me thinking about how to do a lazy, infinite Sieve in Perl 6. (I didn't read the whole article, because I wanted to produce my own implementation first!) Unfortunately, my attempt to do so turned up what seems to be a very major bug lurking in Rakudo's gather / take.

Basically, my notion was this. The Sieve essentially consists of crossing off multiples from a list each time you find a new prime. So what if instead of taking the list to be a fixed limited, fixed array of numbers, you made it an actual infinite lazy list? All you need is a function which, given two infinite lists of numbers, takes the least element at the front of the lists and returns that. Then you when find a new prime, you take your existing list and use that function to merge in the list of multiples of the new prime.

So I started to code this up, and instantly ran into weirdness.

sub sorted-infinite-sequence-merge(Iterator $a-iterator, Iterator $b-iterator)
my $a = $a-iterator.get;
my $b = $b-iterator.get;

gather loop {
my $next = $a min $b;
# say "$a, $b, $next";
take $next;
$a = $a-iterator.get if $a == $next;
$b = $b-iterator.get if $b == $next;

sorted-infinite-sequence-merge((1..100){$_*3}), (1..100){$_*4})).batch(20).perl.say;
sorted-infinite-sequence-merge((3, 6 ... *), (4, 8 ... *)).batch(20).perl.say

That code generates the following two lists:

(3, 4, 6, 8, 9, 12, 15, 16, 18, 20, 21, 24, 27, 28, 30, 32, 33, 36, 39, 40)
(4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80)

As you can see, the first list is clearly correct. The second list (which calls the same merge function, but using source lists generated via series instead of Range) is clearly incorrect. I believe this must represent some sort of gather/take bug triggered by nested gather/take operations.


No comments:

Post a Comment