| Subject: | Enhancement: faster Lucky Number sieve |
The Lucky number sieve used in version 56 is extremely slow.
time perl -MMath::NumSeq::LuckyNumbers -E 'my $seq =
Math::NumSeq::LuckyNumbers->new; foreach my $i (1 .. 50_000) {
my($i,$value) = $seq->next; }'
takes 1m 17s. It also has no support for ith().
Attached is a version that takes 4.5s for the same range. Using ith($i)
takes 5.2s.
It is the sieve I used for computing Lucky primes in Math::Prime::Util,
and regenerates the entire range every time we expand. It could be
rewritten to just sieve the new range and would be much better for this
use, but I thought I'd submit this as an example. The constants it uses
for expansion could use tweaking also, but these seem to be working.
The pathological case for this non-incremental code would be someone
constantly making a new object, retrieving the first couple numbers,
then throwing away the object.
My notes from primes.pl:
# First do a (very basic) lucky number sieve to generate A000959.
# Evens removed for k=1:
# my @lucky = map { $_*2+1 } (0 .. int(($end-1)/2));
# Remove the 3rd elements for k=2:
# my @lucky = grep { my $m = $_ % 6; $m == 1 || $m == 3 } (0 .. $end);
# Remove the 4th elements for k=3:
# my @lucky = grep { my $m = $_ % 21; $m != 18 && $m != 19 }
# grep { my $m = $_ % 6; $m == 1 || $m == 3 }
# map { $_*2+1 } (0 .. int(($end-1)/2));
The code implements a more memory efficient version of the k=3 start.
| Subject: | lucky-code.pl |
sub rewind {
my ($self) = @_;
$self->{'i'} = $self->i_start;
$self->{'array'} = [];
}
sub next {
my ($self) = @_;
### LuckyNumbers next(): "i=$self->{'i'}"
my $i = $self->{'i'};
my $count = scalar @{$self->{'array'}};
if ($count == 0) {
$self->{'array'} = [ _luckygen( 1, 5000 ) ];
} elsif ($i > $count) {
my $last = $self->{'array'}->[-1];
my $newlast = $last + int(10000 * log($last));
$self->{'array'} = [ _luckygen( 1, $newlast ) ];
}
return ($self->{'i'}++, $self->{'array'}->[$i-1]);
}
sub ith {
my ($self, $i) = @_;
my $count = scalar @{$self->{'array'}};
if ($i > $count) {
my $est = $i * 1.6*log($i) + 10;
$self->{'array'} = [ _luckygen( 1, $est ) ];
}
return $self->{'array'}->[$i-1];
}
sub _luckygen {
my ($start, $end) = @_;
my @lucky;
my $n = 1;
while ($n <= $end) {
my $m21 = $n % 21;
push @lucky, $n unless $m21 == 18 || $m21 == 19;
push @lucky, $n+2 unless $m21 == 16 || $m21 == 17;
$n += 6;
}
delete $lucky[-1] if $lucky[-1] > $end;
for (my $k = 3; $k < scalar @lucky; $k++) {
my $skip = $lucky[$k];
my $index = $skip-1;
last if $index > $#lucky;
do {
splice(@lucky, $index, 1);
$index += $skip-1;
} while ($index <= $#lucky);
}
shift @lucky while $lucky[0] < $start;
return @lucky;
}