This queue is for tickets about the Bit-Vector CPAN distribution.

Report information
The Basics
Id:
62740
Status:
open
Priority:
Low/Low
Queue:

People
Owner:
Nobody in particular
Requestors:
user42 [...] zip.com.au
Cc:
AdminCc:

BugTracker
Severity:
(no value)
Broken in:
(no value)
Fixed in:
(no value)



Subject: Primes() step j += 2*i for less work
Date: Sat, 06 Nov 2010 06:38:29 +1100
To: bug-Bit-Vector@rt.cpan.org
From: Kevin Ryde <user42@zip.com.au>
In Bit::Vector 7.1 BitVector_Primes(), as an optimization I wonder if the "j" loop could increment by "j += 2*i" instead of "j += i". The even numbers are already cleared by the 0xAAAA initializer are they?, leaving only odd multiples of i needing attention. Not sure if 2*i would risk overflow if bits==2^32-1, or near there, or make more big sizes where it might overflow. Perhaps the loop condition would be j <= bits-2*i before incrementing, with bits-2*i itself not underflowing because i <= sqrt(bits) so bits >= 2*i ... if that sounds right.
On Fri Nov 05 15:40:29 2010, user42@zip.com.au wrote:
Show quoted text
> In Bit::Vector 7.1 BitVector_Primes(), as an optimization I wonder if > the "j" loop could increment by "j += 2*i" instead of "j += i". The > even numbers are already cleared by the 0xAAAA initializer are they?, > leaving only odd multiples of i needing attention. > > Not sure if 2*i would risk overflow if bits==2^32-1, or near there, or > make more big sizes where it might overflow. Perhaps the loop condition > would be j <= bits-2*i before incrementing, with bits-2*i itself not > underflowing because i <= sqrt(bits) so bits >= 2*i ... if that sounds > right.
Ok, I might investigate this the next time I prepare a new release. But this may take a long time. Sorry.
When/if you do look at it, I recommend looking at Math::Prime::FastSieve's primes function, which is very similar but runs 5-7x faster. This simple change to the inner loop probably suffices: if (BIT_VECTOR_TST_BIT(addr,i)) for ( ; j < bits; j += 2*i ) BIT_VECTOR_CLR_BIT(addr,j) There are of course lots of alternative methods for sieving, but the above is pretty good for a monolithic sieve. Time for counting to 10**9: 0.02s Math::Prime::Util (print count) 4.8s Math::Prime::Util (forced to create monolithic sieve) 10.4s Math::GMPz::eratosthenes (modified for count only) 10.7s Math::Prime::FastSieve 11.9s Bit::Vector with change above 68.9s Bit::Vector


This service runs on Request Tracker, is sponsored by The Perl Foundation, and maintained by Best Practical Solutions.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.