/ 
Math-Prime-FastSieve-0.01
River stage one • 1 direct dependent • 2 total dependents
/ Math::Prime::FastSieve

NAME

Math::Prime::FastSieve - Generate a list of all primes less than 'n'. Do it quickly. Possibly faster than any other method on CPAN.

While we're at it, supply a few additional tools that a Prime Sieve facilitate.

VERSION

Version 0.01

SYNOPSIS

This module provides an optimized implementation of the Sieve of Eratosthenes, and uses it to return a list of all primes up to any integer specified, within the limitations of addressable memory.

Additionally the module provides access to other Prime-related functions that are facilitated as a by-product of having a really fast Prime Sieve.

At the time of writing, the primes function will return all primes up to 'n' faster than any other module I can find on CPAN (including Math::Prime::XS). While a segmented sieve (which this isn't) would extend the range of primes accessible, the fact that this module uses a bit-sieve means that primes over a billion are easily within reach of most modern systems.

# The simple (and fastest) interface:
use Math::Prime::FastSieve qw( primes );

my $aref = primes( 5_000_000 );



#The object (far more flexible) interface.

# Create a new sieve and flag all primes less or equal to n.
my $sieve = Math::Prime::FastSieve::Sieve->new( 5_000_000 );

my $aref = $sieve->primes( 5_000_000 );
my $result = $sieve->isprime( 17 );
my $less_or_equal = $sieve->nearest_le( 42 );
my $greater_or_equal = $sieve->nearest_ge( 42 );
my $num_found = $sieve->count_sieve();
my $quantity_le = $sieve->count_le( 42 );
my $fourty_second_prime = $sieve->nth( 42 );

EXPORT

Exports nothing by default. If you ask nicely it will export the single subroutine, primes.

SUBROUTINES/METHODS

This module provides two modus operandi. The simplest also happens to be the fastest way of generating a list of all primes up to and including $n. That is via a direct call to the primes($n) function.

The more powerful way to use this module is via its object oriented interface. With that approach, the constructor (new($n)) creates a prime sieve flagging all primes from 2 to $n inclusive, and returins a Sieve object. That object may then be queried by way of accessor methods to get at any of the following:

  • primes() A list of all primes within the sieve.

  • isprime($n) A primality test for any integer within the bounds of the sieve.

  • nearest_le($n) Find the nearest prime less than or equal to $n within the bounds of the sieve.

  • nearest_ge($n) Find the nearest prime greater or equal to $n within the bounds of the sieve.

  • count_sieve() A count of all primes in the sieve.

  • count_le($n) A a count of all primes less than or equal to $n within the bounds of the sieve.

  • nth_prime($n) Return the $nth prime, within the bounds of the sieve.

Because the sieve is created when the object is instantiated, many of the tests you might call on the sieve object can be either O(n), O(log n), or even O(1), depending on the test.

The Standard Interface

Objective

Provide a fast and simple means of generating a big list of prime numbers.

primes()

This is a regular function (ie, not an object method).

Pass a positive integer as its parameter. Returns a reference to an array of all prime numbers 2 .. $n.

This function is implemented in C++ using Inline::CPP, which in turn binds it to Perl via XS. The method used is the Sieve of Eratosthenes. The sieve is one of the fastest known methods of generating a list of primes up to $n.

This implementation makes several optimizations beyond the cannonical Sieve, including:

  • Uses a bit vector as a sieve: A memory optimization that allows the sieve to scale well without consuming so much memory that your system grinds to a stand-still for large $ns (where "large" depends on your system, of course).

  • Only sifts and tests odd integers.

  • Returns an array-ref rather than a potentially huge (slow) list.

  • Other micro-optimizations to squeeze a few cycles out here and there.

The result is a prime number generator that is...fast.

The Object Oriented Interface

Objective

Where the standard interface wraps the sieve constructor and the sieve accessor in a single function called primes(), the object oriented interface places the sieve constructor in Math::Prime::FastSieve::Sieve-new()>, and leaves the interpretation of the sieve's results to separate accessor methods. The advantage is that if you don't really need "a big list", but instead need other functionality that may be computationally (and memory) cheaper to obtain from the sieve, you can get at those results without constructing a huge list of primes.

The standard interface is faster. But the object interface is still very fast, and provides greater flexibility.

new()

Class method of Math::Prime::FastSieve::Sieve Requires a single integer parameter that represents the largest value to be held in the sieve. For example:

my $sieve = Math::Prime::FastSieve::Sieve->new( 1_000_000_000 );

This will create a Sieve object that flags all integers from 2 to 1 billion that are prime.

Calling new() is an O(n log log n) operation

DESTROY()

You don't need to call this yourself, but it does exist. When your Sieve object falls out of scope and DESTROY() is automatically invoked by Perl, the bit sieve held in your Sieve object will be freed.

primes()

This works just like the standard primes() function, except that it is a member function of your Sieve object, and also (behind the scenes) it doesn't need to create a sieve of prime flags since new() already did that for you. You must call primes() with an integer parameter. The integer must be less than or equal to the integer value previously passed to the new() constructor. primes() returns a reference to an array of all prime numbers from 2 to the integer passed to it.

Passing an out-of-bounds integer will result in a return value of an array ref pointing to an empty array.

my $primes_ref = $sieve->primes( 1_000_000_000 );
my $primes_ref = $sieve->primes( 50 );

The primes() method is an O(n) operation for both time and memory.

isprime()

Pass a parameter consisiting of a single integer within the range of the Sieve object. Returns true if the integer is prime, false otherwise. If the integer is out of the Sieve object's bounds, the result will be false.

if( $sieve->isprime(42) ) {
    say "42 is prime.";
} else {
    say "42 isn't prime.";
}

This is an O(1) operation.

nearest_le()

The nearest_le() method returns the closest prime that is less than or equal to its integer parameter. Passing an out of bounds parameter will return a 0.

my $nearest_less_or_equal = $sieve->nearest_le( 42 );

Since the nearest prime is never very far away, this is an O( log log n ) operation.

nearest_ge()

Like the nearest_le() method, but this method returns the prime that is greater than or equal to the input parameter. If the input param. is out of range, or if the next prime is out of range, a 0 is returned.

my $nearest_greater_or_equal = $sieve->nearest_ge( 42 );

This is also an O( log log n ) operation.

By adding one to the return value and passing that new value as a parameter to the nearest_ge() method again and again in a loop it is easy to iterate through a list of primes without generating them all at once. Of course it's not going to be as fast as getting the big list all at once, but you can't have everything in life, now can you?

count_sieve()

Takes no input parameter. Counts all of the primes in the sieve and returns the count. The first time this is called on a Sieve object the count takes O(n) time. Subsequent calls benefit from the first run being cached, and thus become O(1) time.

count_le()

Pass an integer within the range of the sieve as a parameter. Return value is a count of how many primes are less than or equal to that integer. If the value passed as a parameter is the same as the size of the sieve, the results are cached for future calls to count_sieve().

This is an O(n) operation.

nth_prime()

This method returns the n-th prime, where n is the cardinal index in the sequence of primes. For example:

say $sieve->nth_prime(1) # prints 2: the first prime is 2.
say $sieve->nth_prime(3) # prints 5: the third prime is 5.

If there is no nth prime in the bounds of the sieve 0 is returned.

Implementation Notes

The sieve is implemented as a bit sieve using a C++ vector<bool>. All integers from 0 to $n are represented in the sieve (evens too). A bit sieve is highly efficient from a memory standpoint. However, because the extra cycles needed to represent only odd numbers in the sieve are too computationally expensive to justify, the sieve doesn't bother with that one potential additional memory optimization. It just seemed that the speed tradeoff wasn't worthwhile.

So, while a bit sieve was used for memory efficiency, just about every other optimization favored reducing time complexity.

Furthermore, all functions and methods are implemented in C++ by way of Inline::CPP. In fact, the sieve itself is never exposed to Perl (this decision is both a time and memory optimization).

Installation

There is a dependancy: Inline::CPP (Inline C++). Inline::CPP has Inline::C, Inline, and Parse::RecDescent as dependancies. Additionally, your system must have a C++ compiler that is compatible with the compiler used to build Perl. In theory it all these dependancies may sound like a big pain. In practice, most users should be able to install this module with the familiar incantations:

cpan Math::Prime::FastSieve

Or download and unpack the tarball, and...

perl Makefile.PL
make
make test
make install

Using the cpan shell, cpanm, or cpanplus will have the added benefit of pulling in and building the dependencies automatically.

AUTHOR

David Oswald, <davido at cpan.org>

BUGS

Please report any bugs or feature requests to bug-math-prime-FastSieve at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Math-Prime-FastSieve. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

You can find documentation for this module with the perldoc command.

perldoc Math::Prime::FastSieve

You can also look for information at:

ACKNOWLEDGEMENTS

This module is made possible by Inline::CPP, which wouldn't be possible without the hard work of the folks involved in the Inline and Inline::C project.

LICENSE AND COPYRIGHT

Copyright 2011 David Oswald.

This program is free software; you can redistribute it and/or modify it under the terms of either: the GNU General Public License as published by the Free Software Foundation; or the Artistic License.

See http://dev.perl.org/licenses/ for more information.