view release on metacpan or  search on metacpan

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

Since the Sieve of Eratosthenes requires one 'bit' per integer in the sieve,
the memory requirements can be high for large tests.  Additionally, as the
result set is generated, because Perl's scalars take up a lot more space than
one bit, it's even more likely the entire result set won't fit into memory.

The OO interface does provide functions that don't build a big huge
memory-hungry list.


Please report any bugs or feature requests to
C<bug-math-prime-FastSieve at rt.cpan.org>, or through the web interface
at L<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.




=head1 SUPPORT

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

    perldoc Math::Prime::FastSieve


You can also look for information at:

=over 4

=item * RT: CPAN's request tracker (report bugs here)

L<http://rt.cpan.org/NoAuth/Bugs.html?Dist=Math-Prime-FastSieve>

=item * AnnoCPAN: Annotated CPAN documentation

L<http://annocpan.org/dist/Math-Prime-FastSieve>

=item * CPAN Ratings

L<http://cpanratings.perl.org/d/Math-Prime-FastSieve>

=item * Search CPAN

L<http://search.cpan.org/dist/Math-Prime-FastSieve/>

=back


=head1 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.  There are many individuals who have contributed and continue to
contribute to the Inline project.  I won't name them all here, but they do
deserve thanks and credit.

Dana Jacobsen provided several optimizations that improved even further on
the speed and memory performance of this module.  Dana's contributions include
reducing the memory footprint of the bit sieve in half, and trimming cycles by
cutting in half the number of iterations of an inner loop in the sieve
generator.  This module started fast and got even faster (and more memory
efficient) with Dana's contributions.

=head1 SEE ALSO

L<Math::Prime::Util> is a much larger Primes library, by Dana Jacobsen.  In
some cases Math::Prime::FastSieve's object-oriented interface may be a better
fit, but generally speaking, Dana's module is a little faster, and supercedes
this module in its functionality and capabilities.

=head1 LICENSE AND COPYRIGHT

Copyright 2011-2014 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.


=cut


__DATA__

__CPP__


#include <vector>


using std::vector;


typedef vector<bool> sieve_type;
typedef vector<bool>::size_type sieve_size_t;


/* Class Sieve below.  Perl sees it as a class named
 * "Math::Prime::FastSieve::Sieve".  The constructor is mapped to
 * "new()" within Perl, and the destructor to "DESTROY()".  All other
 * methods are mapped with the same name as declared in the class.
 *
 * Therefore, Perl sees this class approximately like this:
 *
 * package Math::Prime::FastSieve;
 *
 * sub new {
 *     my $class = shift;
 *     my $n     = shift;
 *     my $self = bless {}, $class;
 *     $self->{max_n} = n;
 *     $self->{num_primes} = 0;
 *     # Build the sieve here...
 *     # I won't bother translating it to Perl.
 *     $self->{sieve} = $primes;  // A reference to a bit vector.
 *     return $self;
 *  }
 *