in reply to Re^7: Number functions.. primes (ugly code runs faster)
in thread Number functions I have lying around

why aren't you eliminating the numbers which end with 2, 4, 5, 6, 8, and 0 before doing any math

If you want you can, but how do you spot those numbers? you are using a regex that, as you can guess, is slower than math checks. Theese numbers will be catched with the modulo operator anyway, as choroba explained.
Also the regex in the original code is also not correct: you skip 2 and 5. 
perl -e "map {print qq($_ ) unless $_ =~/(2|4|5|6|8|0)$/ } @ARGV" 2 3 
+5 7 11 13 17 19 23 29 37
3 7 11 13 17 19 23 29 37

[download]
i used a different regex (and precompiled in the bench program using qr'\d[245680]$'): 
perl -e "map {print qq($_ ) unless $_ =~/\d[245680]$/ } @ARGV" 2 3 5 7
+ 11 13 17 19 23 29 37
2 3 5 7 11 13 17 19 23 29 37

[download]
About saving time skipping numbers ending with some fixed digit, as said, the regex solution is slower: with this code: 

use strict;
use warnings;

use Benchmark qw{ cmpthese };

my $skipper_regex = qr'\d[245680]$';

sub primes_original {
    my $n = shift;
    return if $n < 2;

    my @primes = (2);
    for my $i (3 .. $n) {
        my $sqrt = sqrt $i;
        my $notprime;
        for my $p (@primes) {
            last if $p > $sqrt;

            $notprime = 1, last if 0 == $i % $p;
        }
        push @primes, $i unless $notprime;
    }
    return @primes
}

sub primes_skipper {
    my $n = shift;
    return if $n < 2;

    my @primes = (2);
    for my $i (3 .. $n) {
        next if $i =~ $skipper_regex;
        my $sqrt = sqrt $i;
        my $notprime;
        for my $p (@primes) {
            last if $p > $sqrt;

            $notprime = 1, last if 0 == $i % $p;
        }
        push @primes, $i unless $notprime;
    }
    return @primes
}

##

sub primes_opt_till_11 {
    my $n = shift;
    return if $n < 2;

    my @primes = (2);
    for my $i (3 .. $n) {
                if($i > 2 || $i % 2 == 0){next}
                if($i > 3 || $i % 3 == 0){next}
                if($i > 5 || $i % 5 == 0){next}
                if($i > 7 || $i % 7 == 0){next}
                if($i > 11 || $i % 11 == 0){next}

        my $sqrt = sqrt $i;
        my $notprime;
        for my $p (@primes) {
            last if $p > $sqrt;

            $notprime = 1, last if 0 == $i % $p;
        }
        push @primes, $i unless $notprime;
    }
    return @primes
}
##
use Test::More tests => 1;
is_deeply([primes_original(10000)], [primes_skipper(10000)], "same");

cmpthese(-10,
        {
primes_original => 'primes_original (10000)',
primes_skipper  => 'primes_skipper  (10000)',
primes_opt_till_11  => 'primes_opt_till_11  (10000)',
 });

[download]
You will see a significant decreese of speed if you skip numbers using a regex: 
1..1
ok 1 - same
                     Rate    primes_skipper   primes_original primes_o
+pt_till_11
primes_skipper     33.5/s                --              -35%         
+      -94%
primes_original    51.4/s               53%                --         
+      -90%
primes_opt_till_11  519/s             1448%              909%         
+        --

[download]

HtH
L*
There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

Replies are listed 'Best First'.
Re^9: Number functions.. primes (ugly code runs faster)
by Lady_Aleena (Priest) on Apr 08, 2015 at 19:02 UTC

    Here are some of the problems.

    • Some made assumptions I knew the regex was slowing down my code. I had no idea the regex was the problem.
    • Some made assumptions of my prowess in math. If it isn't addition, subtraction, multiplication, or division; I won't think to use it. So, using sqrt is confusing.
    • Only aaron_baugher commented directly on my code and showed me where I overdid it with the check for divisibility by 9. Everyone else wrote their own versions without commenting on the code I provided first.
    • No one commented their code! I'm still stuck back at choroba's first prime example at the square root test. Adding the use of square roots still bothers me for some reason.

    Like with many car shows my hubby watches where the show glosses over a lot, it is like you took the logo off the car, trashed the car, and put the logo on another car. I still don't know what is so wrong with the original car (function) that the only thing worth saving was the logo (function name). So take one part out at a time, explain why it is broken, then install the new part telling the audience why the new part is better. Pretty please?

    No matter how hysterical I get, my problems are not time sensitive. So, relax, have a cookie, and a very nice day!
    Lady Aleena
[reply]
[d/l]
      I also struggle with Math!!

      A number cannot be prime if it is a perfect square. 16 is perfect square of 4. 16 not prime.

      A number is only prime if two other integers cannot be multiplied together to equal that number.

      Take 37, sqrt = 6.08

      • So as you iterate over the numbers..
      • 37 % 2 == 0, nope. Another way to say is that 2 * something = 37 with no remainder
      • 37 % 3 == 0, nope. Another way to say is that 3 * something = 37 with no remainder
      • 37 % 4 == 0, nope. Another way to say is that 4 * something = 37 with no remainder
      • 37 % 5 == 0, nope. Another way to say is that 5 * something = 37 with no remainder
      • 37 % 6 == 0, nope. Another way to say is that 6 * something = 37 with no remainder

      Our next number would be 7. But we know that 6.08 times any number smaller than 6.08 is < 37 and 6.08 times any number larger than 6.08 is > 37

      So, in our next iteration, 7 * something = 37 with no remainder, for that something to multiply 7 and make 37, would *have* to be smaller than 6.08, and we already tested all those.

      Does that sound right?
[reply]
[reply]

In Section Cool Uses for Perl