Skip Menu |
 

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

Report information
The Basics
Id: 62744
Status: stalled
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() not mark i=composite for less work
Date: Sat, 06 Nov 2010 07:40:41 +1100
To: bug-Bit-Vector [...] rt.cpan.org
From: Kevin Ryde <user42 [...] zip.com.au>
Download (untitled) / with headers
text/plain 417b
Nosing around the code of Bit::Vector 7.1 BitVector_Primes(), as an optimization I wonder if the "j" loop doing BIT_VECTOR_CLR_BIT() can be skipped when i=composite. Eg. multiples of i=15 don't have to be marked as they're already covered by previous i=3 or i=5. Marking only primes found thus far is fairly usual I think. I suppose it'd be a check BIT_VECTOR_TST_BIT(addr,i) and ought to save a good bit of work.
Download (untitled) / with headers
text/plain 594b
On Fri Nov 05 16:41:42 2010, user42@zip.com.au wrote: Show quoted text
> Nosing around the code of Bit::Vector 7.1 BitVector_Primes(), as an > optimization I wonder if the "j" loop doing BIT_VECTOR_CLR_BIT() can be > skipped when i=composite. Eg. multiples of i=15 don't have to be marked > as they're already covered by previous i=3 or i=5. > > Marking only primes found thus far is fairly usual I think. I suppose > it'd be a check BIT_VECTOR_TST_BIT(addr,i) and ought to save a good bit > of work.
Ok, I might investigate this the next time I prepare a new release. But this may take a long time. Sorry.


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.