There's more than one way to do things PerlMonks

### Re: To Findout Prime number

by andreas1234567 (Vicar)
 on Feb 08, 2008 at 08:30 UTC ( #666930=note: print w/replies, xml ) Need Help??

in reply to To Findout Prime number

merlyn wrote an interesting column that uses the classic Sieve of Eratosthenes for finding primes. It includes clever use of the vec operator. Omitting the print it finds all primes below 1 million in 10 seconds on a mediocre i386:
```\$ time perl -w
use strict;
my \$UPPER = 1_000_000;
my \$sieve = "";
GUESS: for (my \$guess = 2; \$guess <= \$UPPER; \$guess++) {
next GUESS if vec(\$sieve,\$guess,1);
#print "\$guess\n";
for (my \$mults = \$guess * \$guess; \$mults <= \$UPPER; \$mults += \$guess
+) {
vec(\$sieve,\$mults,1) = 1;
}
}
__END__

real    0m10.003s
user    0m2.191s
sys     0m0.003s
There's an interesting animation here that shows how the algorithm works.

--
Andreas

Replies are listed 'Best First'.
Re^2: To Findout Prime number
by lodin (Hermit) on Feb 08, 2008 at 13:45 UTC

It includes clever use of the vec operator.

Maybe there's historical reasons for using vec over substr, but nowadays it's much faster to use substr. The for my \$foo (\$from .. \$to) { ... } construct is also slightly more efficiently than for (my \$foo = \$from; \$foo <= \$to; \$foo++) { ... }. My guess is that the C-style loop was used as the "range loop" wasn't optimized back then and actually generated a list of, in this case, a million numbers.

I changed the for loop and did a direct translation to using substr instead of vec, and here's the results:

```Benchmark: running substr, vec for at least 60 CPU seconds...
substr: 61 wallclock secs (62.41 usr +  0.02 sys = 62.42 CPU) @  1
+.09/s (n=68)
vec: 58 wallclock secs (60.64 usr +  0.02 sys = 60.66 CPU) @  0
+.73/s (n=44)
s/iter    vec substr
vec      1.38     --   -33%
substr  0.918    50%     --
Here's the code:
```use strict;
use warnings;
use Benchmark qw(cmpthese timethese);

my %subs;

######################################################################
+#########

my \$UPPER = 1_000_000;

\$subs{vec} = sub {
my \$sieve = "";
GUESS: for my \$guess (2 .. \$UPPER) {
next GUESS if vec(\$sieve,\$guess,1);
#print "\$guess\n";
for (my \$mults = \$guess * \$guess; \$mults <= \$UPPER; \$mults +=
+\$guess) {
vec(\$sieve,\$mults,1) = 1;
}
}
};

\$subs{substr} = sub {
my \$sieve = '0' x (\$UPPER + 1);
GUESS: for my \$guess (2 .. \$UPPER) {
next GUESS if substr(\$sieve,\$guess,1);
#print "\$guess\n";
for (my \$mults = \$guess * \$guess; \$mults <= \$UPPER; \$mults +=
+\$guess) {
substr(\$sieve,\$mults,1,1);
}
}
};

######################################################################
+#########

cmpthese(timethese(-60, \%subs));

lodin

nowadays it's much faster to use substr
I re-ran your benchmark on Linux 2.6.9 i686, perl v5.8.5 built for i386-linux-thread-multi. The difference was much less than what you encountered.
```\$ perl -w 666965.pl
Benchmark: running substr, vec for at least 60 CPU seconds...
substr: 67 wallclock secs (60.69 usr +  0.03 sys = 60.72 CPU) @  0
+.58/s (n=35)
vec: 66 wallclock secs (61.33 usr +  0.04 sys = 61.37 CPU) @  0
+.54/s (n=33)
s/iter    vec substr
vec      1.86     --    -7%
substr   1.73     7%     --
On Linux 2.6.22-10-386 i686, perl v5.10.0 (different hardware than above):
```Benchmark: running substr, vec for at least 60 CPU seconds...
substr: 62 wallclock secs (61.69 usr +  0.05 sys = 61.74 CPU) @  0
+.44/s (n=27)
vec: 61 wallclock secs (60.81 usr +  0.05 sys = 60.86 CPU) @  0
+.39/s (n=24)
s/iter    vec substr
vec      2.54     --   -10%
substr   2.29    11%     --
Update Mon Feb 11 12:13:38 CET 2008: Added perl 5.10 benchmark on lodin's request.
--
Andreas

Create A New User
Node Status?
node history
Node Type: note [id://666930]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (5)
As of 2018-05-26 22:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (194 votes). Check out past polls.

Notices?