David Oswald
2012-05-25 08:10:01 UTC
I've uploaded a new version of Math::Prime::FastSieve: v0.10.
This version is still based on Inline::CPP. At some future point I
may use InlineX::CPP2XS to remove the Inline::CPP dependency, but for
now I like it how it is.
Here are the most significant changes:
- Implemented an END{ Inline->init(); } block to prevent M54 warnings.
(Rob's suggestion).
- Increment inner 'j' loops at +=2 instead of just ++ ( 20-30% performance
improvement for primes(), and even better for the OO constructor.
(Dana's suggestion)
- EXPERIMENTAL support for long int data type. Perls built with long int
support are now able to go past the 2.14 billion limitation imposed by
standard ints. However, I haven't tested on a 32 bit Perl, so it may not
fare well in smoke testing. If the smoke tests start throwing up FAILs, I
will roll back the change, and possibly re-implement it behind
preprocessor guards. (Longs were another of Dana's suggestions).
- TO-DO: Dana also suggested trimming the sieve size in half by eliminating
evens from it. We're already NOT spending time iterating over evens, but
to keep the algorithm's math simple, a sieve of 1 .. 100000 has 100000 bits.
As Dana pointed out, it could contain just 50000 bits representing odd
integers, thereby saving some memory.
I may implement that later on, but
I think in the past I benchmarked it and found the math to be more
expensive. More work needs to be done there to work out the details of a
computationally cheap means of cutting the sieve's memory footprint
in half.
One other note: Perl SV's support an 'unsigned' data type, and my
functions mostly work with unsigned longs internally. They even
specify unsigned longs as return type in some cases. However,
whenever I try to specify unsigned long as a parameter type,
compilation fails. I think it may be an Inline::C or Inline::CPP
issue, either in the grammar parsing or in the typemaps.
Dave
This version is still based on Inline::CPP. At some future point I
may use InlineX::CPP2XS to remove the Inline::CPP dependency, but for
now I like it how it is.
Here are the most significant changes:
- Implemented an END{ Inline->init(); } block to prevent M54 warnings.
(Rob's suggestion).
- Increment inner 'j' loops at +=2 instead of just ++ ( 20-30% performance
improvement for primes(), and even better for the OO constructor.
(Dana's suggestion)
- EXPERIMENTAL support for long int data type. Perls built with long int
support are now able to go past the 2.14 billion limitation imposed by
standard ints. However, I haven't tested on a 32 bit Perl, so it may not
fare well in smoke testing. If the smoke tests start throwing up FAILs, I
will roll back the change, and possibly re-implement it behind
preprocessor guards. (Longs were another of Dana's suggestions).
- TO-DO: Dana also suggested trimming the sieve size in half by eliminating
evens from it. We're already NOT spending time iterating over evens, but
to keep the algorithm's math simple, a sieve of 1 .. 100000 has 100000 bits.
As Dana pointed out, it could contain just 50000 bits representing odd
integers, thereby saving some memory.
I may implement that later on, but
I think in the past I benchmarked it and found the math to be more
expensive. More work needs to be done there to work out the details of a
computationally cheap means of cutting the sieve's memory footprint
in half.
One other note: Perl SV's support an 'unsigned' data type, and my
functions mostly work with unsigned longs internally. They even
specify unsigned longs as return type in some cases. However,
whenever I try to specify unsigned long as a parameter type,
compilation fails. I think it may be an Inline::C or Inline::CPP
issue, either in the grammar parsing or in the typemaps.
Dave
--
David Oswald
daoswald-***@public.gmane.org
David Oswald
daoswald-***@public.gmane.org