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)

History Show all quoted text
  Fri Nov 05 15:40:29 2010 user42 [...] zip.com.au - Ticket created
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.
  Thu Dec 09 11:44:16 2010 STBEY [...] cpan.org - Correspondence added
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.
  Thu Dec 09 11:44:17 2010 The RT System itself - Status changed from 'new' to 'open'
  Thu Dec 09 11:44:17 2010 STBEY [...] cpan.org - Status changed from 'open' to 'stalled'
  Wed Feb 12 18:10:03 2014 DANAJ [...] cpan.org - Correspondence added
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
  Wed Feb 12 18:10:03 2014 The RT System itself - Status changed from 'stalled' to 'open'