Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: Sieve of Eratosthenes with closures

by tilly (Archbishop)
on Jul 21, 2003 at 00:14 UTC ( #276112=note: print w/replies, xml ) Need Help??


in reply to Sieve of Eratosthenes with closures

Not all prime number sieves are the Sieve of Eratosthenes.

The key insight that makes the Sieve of Eratosthenes so nice is that for each prime you only have to do an operation on multiples of that prime. This causes the running time to be just slightly supralinear (IIRC it is O(n*log(log(n))) to get all the primes up to n) rather than being close to O(n**1.5) (yours should be O(n**1.5/log(n)).

Here is an actual Sieve of Eratosthenes implemented with closures. It isn't that fast, but it scales right. Memory usage should scale O(sqrt(n)).

#! /usr/bin/perl -w use strict; sub build_sieve { my $n = 0; my @upcoming_factors = (); my ($next_small_p, $sub_iter); my $gives_next_square = 5; return sub { LOOP: { if (not $n++) { return 2; # Special case } if (not defined $upcoming_factors[0]) { if ($n == $gives_next_square) { if (not defined ($sub_iter)) { # Be lazy to avoid an infinite loop... $sub_iter = build_sieve(); $sub_iter->(); # Throw away 2 $next_small_p = $sub_iter->(); } push @{$upcoming_factors[$next_small_p]}, $next_small_p; $next_small_p = $sub_iter->(); my $next_p2 = $next_small_p * $next_small_p; $gives_next_square = ($next_p2 + 1)/2; shift @upcoming_factors; redo LOOP; } else { shift @upcoming_factors; return 2*$n-1; } } else { foreach my $i (@{$upcoming_factors[0]}) { push @{$upcoming_factors[$i]}, $i; } shift @upcoming_factors; redo LOOP; } } } } # Produce as many primes as are asked for, or 100. my $sieve = build_sieve(); print $sieve->(), "\n" for 1..(shift || 100);

Replies are listed 'Best First'.
Re: Re: Sieve of Eratosthenes with closures
by SyN/AcK (Scribe) on Jul 21, 2003 at 04:23 UTC
    Wow, this looks like some complex stuff. How exactly would this be benneficial in a program? Or is it basically just concept and application?
      Closures allow you to organize code differently. The resulting style is as distinct from OO and procedural as they are from each other.

      Right now Dominus is writing a book on the subject. You can find some information in this article on iterators, a number of my nodes talk about closures a bit, see Why I like functional programming for one of the better ones. Or you can search for more information.

      Of course in this case the technique is just for fun. A somewhat shorter implementation of a sieve of Eratosthenes is:

      sub sieve { grep{@_[map$a*$_,$_..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop } print join " ", sieve(100);
      (Implementation due to tye at (tye)Re3: (Golf): Sieve of Eratosthenes.)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://276112]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (6)
As of 2019-08-21 10:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?