view release on metacpan or  search on metacpan

lib/Math/Prime/FastSieve.pm  view on Meta::CPAN

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

=over 4

=item * C<primes()>
A list of all primes within the sieve.

=item * C<ranged_primes( $lower, $upper )>
A list of all primes >= C<$lower>, and <= C<$upper>.

=item * C<isprime($n)>
=item * C<is_prime($n)>
A primality test for any integer within the bounds of the sieve.  C<is_prime()>
is synonymous for C<isprime()>, mostly because I got tired of forgetting
how to spell the method.

=item * C<nearest_le($n)>
Find the nearest prime less than or equal to C<$n> within the bounds of
the sieve.

=item * C<nearest_ge($n)>
Find the nearest prime greater or equal to C<$n> within the bounds of
the sieve.

=item * C<count_sieve()>
A count of all primes in the sieve.

=item * C<count_le($n)>
A a count of all primes less than or equal to C<$n> within the bounds of
the sieve.

=item * C<nth_prime($n)>
Return the C<$n>th prime, within the bounds of the sieve.

=back

Because the sieve is created when the object is instantiated, many of
the tests you might call on the sieve object will execute quite quickly.
Each of the subs and methods documented below will also attempt to describe
the computational and memory complexity of the function.

=head1 The Standard Interface

=head2 Objective

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

=head3 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 C<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 C<$n>.

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

=over 4

=item * 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 C<$n>s (where "large" depends
on your system, of course).

=item * The sieve's bits only represent odd numbers (memory optimization).

=item * Only sifts and tests odd integers. (2 is handled as a special case.)

=item * Returns an array-ref rather than a potentially huge (slow) list.

=item * Other micro-optimizations to squeeze a few cycles out here
and there.

=back

The result is a prime number generator that is...fast.  It operates in
O( n log log n ) time, with a O(n) memory growth rate.

=head1 The Object Oriented Interface

=head2 Objective

Where the standard interface wraps the sieve constructor and the sieve
accessor in a single function called C<primes()>, the object oriented
interface places the sieve constructor in
C<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 slightly faster if you just want a big list.  But
the object interface is still very fast, and provides greater flexibility,
including the ability to use C<ranged_primes()> to process primes in smaller,
more memory efficient chunks.


=head3 new()

Class method of C<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 C<new()> is an O(n log log n) operation.  The memory growth is at a
rate that is 1/8th the rate of growth of C<$n>.