Dave Cross: Still Munging Data With Perl: Online event - Mar 17 Learn more

#!/usr/bin/env perl
use strict;
use Benchmark qw/:all/;
use Devel::Size qw/total_size/;
*mpu_isprime = \&Math::Prime::Util::is_prime;
my $count = shift || -1;
my @numlist;
my @testnums = (0..1000, 5_000_000 .. 5_001_000, 30037, 20359*41117, 92987*65171, 27361*31249, 70790191, 3211717*9673231);
my $ip_subs = {
#"Abigail" => sub { my$r;$r=abigail($_) for @numlist; $r;},
"Rosetta" => sub { my$r;$r=rosetta($_) for @numlist; $r;},
"Rosetta2"=> sub { my$r;$r=rosetta2($_) for @numlist; $r;},
"DJ" => sub { my$r;$r=dj($_) for @numlist; $r;},
"DJ2" => sub { my$r;$r=dj2($_) for @numlist; $r;},
"DJ3" => sub { my$r;$r=dj3($_) for @numlist; $r;},
"DJ4" => sub { my$r;$r=dj4($_) for @numlist; $r;},
"MPU" => sub { my$r;$r=mpu_isprime($_) for @numlist; $r;},
};
my %verify = (
0 => 0,
1 => 0,
2 => 1,
3 => 1,
4 => 0,
5 => 1,
6 => 0,
7 => 1,
13 => 1,
20 => 0,
377 => 0,
70790191 => 1,
);
# Verify
while (my($name, $sub) = each (%$ip_subs)) {
while (my($n, $v_ip) = each (%verify)) {
@numlist = ($n);
#print "$name($n): ", $sub->(), "\n";
my $isprime = ($sub->() ? 1 : 0);
die "$name($n) = $isprime, should be $v_ip\n" unless $isprime == $v_ip;
}
}
for my $n (0 .. 50000) {
die "dj($n) != mpu($n)" unless dj($n) == mpu_isprime($n);
die "dj2($n) != mpu($n)" unless dj2($n) == mpu_isprime($n);
die "dj3($n) != mpu($n)" unless dj3($n) == mpu_isprime($n);
die "dj4($n) != mpu($n)" unless dj4($n) == mpu_isprime($n);
die "rosetta($n) != mpu($n)" unless rosetta($n) == mpu_isprime($n)/2;
die "rosetta2($n) != mpu($n)" unless rosetta2($n) == mpu_isprime($n)/2;
}
print "Done with verification, starting benchmark\n";
@numlist = @testnums;
cmpthese($count, $ip_subs);
sub rosetta {
my $n = shift;
$n % $_ or return 0 for 2 .. sqrt $n;
$n > 1;
}
sub rosetta2 {
my $p = shift;
if ($p == 2) {
return 1;
} elsif ($p <= 1 || $p % 2 == 0) {
return 0;
} else {
my $limit = sqrt($p);
for (my $i = 3; $i <= $limit; $i += 2) {
return 0 if $p % $i == 0;
}
return 1;
}
}
# Terrifically clever, but useless for large numbers
sub abigail {
('1' x shift) !~ /^1?$|^(11+?)\1+$/
}
sub dj {
my($n) = @_;
return 0 if $n < 2; # 0 and 1 are composite
return 2 if ($n == 2) || ($n == 3) || ($n == 5); # 2, 3, 5 are prime
# multiples of 2,3,5 are composite
return 0 if (($n % 2) == 0) || (($n % 3) == 0) || (($n % 5) == 0);
my $q;
foreach my $i (qw/7 11 13 17 19 23 29 31 37 41 43 47 53 59/) {
$q = int($n/$i); return 2 if $q < $i; return 0 if $n == ($q*$i);
}
my $i = 61; # mod-30 loop
while (1) {
$q = int($n/$i); last if $q < $i; return 0 if $n == ($q*$i); $i += 6;
$q = int($n/$i); last if $q < $i; return 0 if $n == ($q*$i); $i += 4;
$q = int($n/$i); last if $q < $i; return 0 if $n == ($q*$i); $i += 2;
$q = int($n/$i); last if $q < $i; return 0 if $n == ($q*$i); $i += 4;
$q = int($n/$i); last if $q < $i; return 0 if $n == ($q*$i); $i += 2;
$q = int($n/$i); last if $q < $i; return 0 if $n == ($q*$i); $i += 4;
$q = int($n/$i); last if $q < $i; return 0 if $n == ($q*$i); $i += 6;
$q = int($n/$i); last if $q < $i; return 0 if $n == ($q*$i); $i += 2;
}
2;
}
sub dj2 {
my($n) = @_;
return 2 if ($n == 2) || ($n == 3) || ($n == 5); # 2, 3, 5 are prime
return 0 if $n < 7; # everything else below 7 is composite
# multiples of 2,3,5 are composite
return 0 if (($n % 2) == 0) || (($n % 3) == 0) || (($n % 5) == 0);
foreach my $i (qw/7 11 13 17 19 23 29 31 37 41 43 47 53 59/) {
return 2 if $i*$i > $n;
return 0 if ($n % $i) == 0;
}
my $limit = int(sqrt($n));
my $i = 61; # mod-30 loop
while (1) {
return 0 if ($n % $i) == 0; $i += 6; last if $i > $limit;
return 0 if ($n % $i) == 0; $i += 4; last if $i > $limit;
return 0 if ($n % $i) == 0; $i += 2; last if $i > $limit;
return 0 if ($n % $i) == 0; $i += 4; last if $i > $limit;
return 0 if ($n % $i) == 0; $i += 2; last if $i > $limit;
return 0 if ($n % $i) == 0; $i += 4; last if $i > $limit;
return 0 if ($n % $i) == 0; $i += 6; last if $i > $limit;
return 0 if ($n % $i) == 0; $i += 2; last if $i > $limit;
}
2;
}
sub dj3 {
my($n) = @_;
return 2 if ($n == 2) || ($n == 3) || ($n == 5); # 2, 3, 5 are prime
return 0 if $n < 7; # everything else below 7 is composite
# multiples of 2,3,5 are composite
return 0 if (($n % 2) == 0) || (($n % 3) == 0) || (($n % 5) == 0);
foreach my $i (qw/7 11 13 17 19 23 29 31 37 41 43 47 53 59/) {
return 2 if $i*$i > $n;
return 0 if ($n % $i) == 0;
}
my $limit = int(sqrt($n));
my $i = 61; # mod-30 loop
while (($i+30) <= $limit) {
return 0 if ($n % $i) == 0; $i += 6;
return 0 if ($n % $i) == 0; $i += 4;
return 0 if ($n % $i) == 0; $i += 2;
return 0 if ($n % $i) == 0; $i += 4;
return 0 if ($n % $i) == 0; $i += 2;
return 0 if ($n % $i) == 0; $i += 4;
return 0 if ($n % $i) == 0; $i += 6;
return 0 if ($n % $i) == 0; $i += 2;
}
while (1) {
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 6;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 4;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 2;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 4;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 2;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 4;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 6;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 2;
}
2;
}
sub dj4 {
my($n) = @_;
return 2 if ($n == 2) || ($n == 3) || ($n == 5); # 2, 3, 5 are prime
return 0 if $n < 7; # everything else below 7 is composite
# multiples of 2,3,5 are composite
return 0 if (($n % 2) == 0) || (($n % 3) == 0) || (($n % 5) == 0);
foreach my $i (qw/7 11 13 17 19 23 29/) {
return 2 if $i*$i > $n;
return 0 if ($n % $i) == 0;
}
my $limit = int(sqrt($n));
my $i = 31;
while (($i+30) <= $limit) {
return 0 if ($n % $i) == 0; $i += 6;
return 0 if ($n % $i) == 0; $i += 4;
return 0 if ($n % $i) == 0; $i += 2;
return 0 if ($n % $i) == 0; $i += 4;
return 0 if ($n % $i) == 0; $i += 2;
return 0 if ($n % $i) == 0; $i += 4;
return 0 if ($n % $i) == 0; $i += 6;
return 0 if ($n % $i) == 0; $i += 2;
}
while (1) {
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 6;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 4;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 2;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 4;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 2;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 4;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 6;
last if $i > $limit; return 0 if ($n % $i) == 0; $i += 2;
}
2;
}