faster code

1 files changed, 46 insertions, 7 deletions

diff --git a/challenge-159/james-smith/perl/ch-2.pl b/challenge-159/james-smith/perl/ch-2.pl
index 5c86128a4d..7d22c8df6d 100644
--- a/challenge-159/james-smith/perl/ch-2.pl
+++ b/challenge-159/james-smith/perl/ch-2.pl
@@ -13,26 +13,65 @@ my @TESTS = (
   [  5, -1 ],
   [ 10,  1 ],
   [ 20,  0 ],
+## The following are good examples where the second algorithm works well!
+  [ 2,   -1 ],
+  [ 6,   1 ],
+  [ 30,   -1 ],
+  [ 210,   1 ],
+  [ 2310,   -1 ],
+  [ 30030,   1 ],
+  [ 510510,  -1 ],
+  [ 9699690, 1 ],
+  [ 6895531,   -1 ],
+  [ 206865930,  1 ],
+  [ 223092870, -1 ],
+  [ 6469693230, 1 ],
 );
 
-is( moebius(    $_->[0]), $_->[1] ) foreach @TESTS;
-is( moebius_exp($_->[0]), $_->[1] ) foreach @TESTS;
+warn "exp";
+is( moebius_exp(     $_->[0] ), $_->[1] ) for @TESTS;
+warn "opt";
+is( moebius_div_opt( $_->[0] ), $_->[1] ) for @TESTS;
+timethis( 500_000, sub { moebius_div_opt( $_->[0] ) for @TESTS } );
+warn "div";
+is( moebius_div(     $_->[0] ), $_->[1] ) for @TESTS;
+timethis(     100, sub { moebius_div(     $_->[0] ) for @TESTS } );
+warn "dumb";
+is( moebius(         $_->[0] ), $_->[1] ) for @TESTS;
+timethis(       5, sub { moebius(         $_->[0] ) for @TESTS } );
 
 done_testing();
 
 sub moebius {
   my ($n,$p,$r) = (shift,1,1);
   return -1 if is_prime($n);
-  $n%($p**2) ? ($n%$p && ($r=-$r)) : return 0 while ($p = next_prime $p) < $n;
+  $n%($p**2) ? ($n%$p || ($r=-$r)) : return 0 while ($p = next_prime $p) <= $n;
+  $r;
+}
+
+sub moebius_div {
+  my ($n,$p,$r) = (shift,1,1);
+  return -1 if is_prime $n;
+  $n%($p**2) ? ( $n%$p || ($r=-$r,$n/=$p)) : return 0 while ($p = next_prime $p) && $n>1;
+  $r;
+}
+
+sub moebius_div_opt {
+  my ($n,$p,$r) = (shift,1,1);
+  return -1 if is_prime $n;
+  $n%$p || ($r=-$r,$n/=$p) && ( $n%$p ? ( (is_prime $n) && (return -$r) ) : return 0 ) while ($p = next_prime $p)**2 <= $n;
   $r;
 }
 
 sub moebius_exp {
   my ($n,$p,$r) = (shift,1,1);
-  return -1 if is_prime($n);
-  while( ($p = next_prime $p ) < $n ) {
-    return 0 unless $n%($p**2);
-    $r=-$r unless $n%$p;
+  return -1 if is_prime $n;
+  while( ($p = next_prime $p )**2 <= $n ) {
+    next if $n%$p;
+    $r=-$r;
+    $n/=$p;
+    return 0 unless $n%$p;
+    return -$r if is_prime $n;
   }
   $r;
 }