view release on metacpan or  search on metacpan

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

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>.


=head3 primes()

This works just like the standard C<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 C<new()> already
did that for you.  You must call C<primes()> with an integer parameter.
The integer must be less than or equal to the integer value previously
passed to the C<new()> constructor.  C<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 C<primes()> method is an O(n) operation for both time and memory.

=head3 ranged_primes()

This behaves exactly like the C<primes()> method, except that you
specify a lower and upper limit within the bounds of the sieve.  The
return value is a reference to an array holding all prime numbers
greater than or equal to the lower limit, and less than or equal to the
upper limit.

The purpose of this method is to allow you to create a sieve ( with
C<new()> ), and then get results in a segmented form.  The reasons this
may be desirable are two-fold:  First, you may only need a subset.
Second, this gives you finer control over how much memory is gobbled up
by the list returned.  For a huge sieve the sieve's memory footprint is
much smaller than the list of integers that are flagged as prime.  By
dealing with that list in chunks you can have a sieve of billions of
prime flags, but never hold that big of a list of integers in memory
all at once.

    my $primes_ref = $sieve->ranged_primes( 5, 16 );
    # $primes_ref now holds [ 5, 7, 11, 13 ].

The time complexity of this method is O(n) where 'n' is the upper limit
minus the lower limit.  So a range of 5_000_000 .. 5_000_010 consumes as
much time as 100 .. 110.


=head3 isprime()
=head3 is_prime()

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.";
    }

C<is_prime()> is a synonym for C<isprime()>.  They're the same method; I
just grew tired of forgetting which spelling to use when calling the
method.

This is an O(1) operation.


=head3 nearest_le()

The C<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 C<0>.

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

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


=head3 nearest_ge()

Like the C<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 C<0> is returned.

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

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

By adding one to the return value and passing that new value as a
parameter to the C<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?


=head3 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.


=head3 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 C<count_sieve()>.

This is an O(n) operation.


=head3 nth_prime()

This method returns the n-th prime, where C<$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 C<0> is returned.




=head1 Implementation Notes

The sieve is implemented as a bit sieve using a C++ vector<bool>.  All odd
integers from 3 to C<$n> are represented based on their index within the
sieve. The only even prime, 2, is handled as a special case.  A bit sieve is
highly efficient from a memory standpoint because obviously it only consumes
one byte per eight integers. This sieve is further optimized by reperesenting
only odd integers in the sieve.  So a sieve from 0 .. 1_000_000_000 only needs
500_000_000 bits, or 59.6 MB.

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).

A side effect of using a bit sieve is that the sieve itself actually
requires far less memory than the integer list of primes sifted from it.
That means that the memory bottleneck with the C<primes()> function, as
well as with the C<primes()> object method is not, in fact, the sieve,
but the list passed back to Perl via an array-ref.

If you find that your system memory isn't allowing you to call C<primes>
with as big an integer as you wish, use the object oriented interface.
C<new> will generate a sieve up to the largest integer your system.  Then
rather than calling the C<primes> method, use C<ranged_primes>, or
C<nearest_ge> to iterate over the list. Of course this is slightly slower, but
it beats running out of memory doesn't it?

NOTE: As of version 0.10, support for long ints is built into
Math::Prime::FastSieve.  If your version of Perl was built with support for
long ints, you can create sieve sizes well over the 2.14 billion limit that
standard ints impose.

=head1 DEPENDENCIES

You will need:  L<Inline|Inline>, L<Inline::C|Inline::C> (which is packaged
with Inline), L<Parse::RecDescent|Parse::RecDescent>,
L<Inline::MakeMaker|Inline::MakeMaker>,
L<ExtUtils::MakeMaker|ExtUtils::MakeMaker> (core), and
L<Test::More|Test::More> (core).

=head1 CONFIGURATION AND ENVIRONMENT

In addition to the module dependencies listed in the previous section, your
system must have a C++ compiler that is compatible with the compiler used to
build Perl.  You may need to install one.  Additionally, if your Perl was
built with long integer support, this module will take advantage of that
support.

While it may sound like there are a lot of dependencies and configuration
requirements, in practice, most users should be able to install this module
with the familiar incantations: