Skip Menu |
 

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

Report information
The Basics
Id: 62740
Status: open
Priority: 0/
Queue: Bit-Vector

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

Bug Information
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>
Download (untitled) / with headers
text/plain 552b
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.
Download (untitled) / with headers
text/plain 733b
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.
Download (untitled) / with headers
text/plain 694b
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 is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

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