RE: [MacPerl] Prime Numbers

["Creede Lambard (Volt Computer)" <a-creela@microsoft.com>]

> -----Original Message-----
> From: bart.lateur@skynet.be [mailto:bart.lateur@skynet.be]
> Sent: Tuesday, August 17, 1999 12:10 AM
> To: MacPerl Mailing List
> Subject: Re: [MacPerl] Prime Numbers
> 
> 
> On Mon, 16 Aug 1999 17:48:06 GMT, Bart Lateur wrote:
> 
> 
> >So a different algorithm should be able to give a large speed boost.
> 
> Here's my code. Let the benchmarks begin! ;-)

OK, but I don't know how you're going to beat this one. It reports that
computation takes between 0 and 2 seconds on my 9600. Remember the other day
when I was joking about Eratosthenes' Sieve? Well, it's not quite so much of
a joke if you don't actually use a million-character string (which I haven't
yet tried, by the way):

#!perl -w ---------------------------------------------------
#
# eratosthenes.pl version 0.3
# an implementation of Eratosthenes' Sieve
# (c) 1999 Creede Lambard. Distributed under the same terms as Perl.
#

$limit = 1000;
$sqrt_of_limit = ($limit ** .5);
$report = 0;
$screen_print = 0;
$file_print = 0;
@primes = ();
$seed = 3;

if ($file_print)
{
    open FILE,">Macintosh HD:Desktop Folder:Primes" or die "Can't open file
'Primes': $!";
}

$start = time;
$primes[2] = 1;
while ($seed <= $sqrt_of_limit)
{
    unless (defined($primes[$seed]))
    {
	    for ( $i = $seed * $seed; $i <= $limit; $i += ($seed + $seed))
	    {
	        $primes[$i] = 0;
	    }
    }
    $seed += 2;
}

if ($report)
{
    &lprint("2, ");
	for ($i = 3; $i <= $limit; $i += 2)
	{
	     &lprint("$i") unless (defined($primes[$i])); 
	}
}

$end = time;

if ($file_print)
{
    close FILE;
}

print "\nComputation took ",$end-$start," seconds.\n";

sub lprint
{
    my ($line) = @_;
    $line .= "\n";
    if ($screen_print) { print $line; }
    if ($file_print) { print FILE $line; }
}

__END__

#
#
#
----------------------------------------------------------------------------
---

Of course I counted only the time to actually generate the primes, not to
print them out. Watching them print might be doable, but I do still have
work to do.

There are a couple of optimizations here. First, this script makes the
assumption that 2 is a special case. We can ignore any even number higher
than 2 and just drop 2 into our list of primes (or, as this is implemented,
our non_list, since only composites are defined in the array). We also make
this a special case if we're printing out the results. Second, if we are
going up through the list of primes, starting and 2 and going on through 3,
5, 7, etc. to prime p, any primes below p * p will already have been found.
So, we can start our check at p * p. However, since we know p is an odd
number, we know p+1 is going to be even, so we only need to check the series
p * (p+2), p * (p*4), etc. 

The if($report) block is necessary for primes higher than about 1000,
because it takes so long to print out the list. (It takes much less time if
you print everything with no line breaks, but it sure confuses your Mac.
When I tried it on a million entries it took about 20 seconds to figure the
primes, then 10 seconds to print everything out, then about 10 more seconds
of (presumably) garbage collection and shutting down.) 

Anyway this looks to me like it's a pretty well slimmed-down algorithm,
though I'm sure there's room for optimization. What do you-all think?

-- Creede

===== Want to unsubscribe from this list?
===== Send mail with body "unsubscribe" to macperl-request@macperl.org