Bug #62743 for Bit-Vector: Primes() i*i loop vs bits=2^32-1

Fri Nov 05 16:39:10 2010 user42 [...] zip.com.au - Ticket created

Subject:	Primes() i*i loop vs bits=2^32-1
Date:	Sat, 06 Nov 2010 07:38:02 +1100
To:	bug-Bit-Vector [...] rt.cpan.org
From:	Kevin Ryde <user42 [...] zip.com.au>

In Bit::Vector 7.1 BitVector_Primes(), if bits=2^32-1 then I think the i*i in the loop test (j = i * i) < bits may overflow 32 bits. The loop runs i=65535 as it should, but the next i=65537 has i*i wrapping around to 131073, so i*i < bits is satisfied and it doesn't stop as intended. I suspect it may even end up an infinite loop if i*i never comes out equal to "bits". In any case maybe it could have a pre-calculated loop limit like floor(sqrt(bits)), or maybe an extra i <= floor(sqrt(UINT_MAX)) worked in to ensure i*i<=UINT_MAX.

Thu Dec 09 11:45:16 2010 STBEY [...] cpan.org - Correspondence added

On Fri Nov 05 16:39:10 2010, user42@zip.com.au wrote: Show quoted text

> In Bit::Vector 7.1 BitVector_Primes(), if bits=2^32-1 then I think the > i*i in the loop test > > (j = i * i) < bits > > may overflow 32 bits. The loop runs i=65535 as it should, but the next > i=65537 has i*i wrapping around to 131073, so i*i < bits is satisfied > and it doesn't stop as intended. > > I suspect it may even end up an infinite loop if i*i never comes out > equal to "bits". > > In any case maybe it could have a pre-calculated loop limit like > floor(sqrt(bits)), or maybe an extra i <= floor(sqrt(UINT_MAX)) worked > in to ensure i*i<=UINT_MAX.

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:45:17 2010 The RT System itself - Status changed from 'new' to 'open'

Thu Dec 09 11:45:17 2010 STBEY [...] cpan.org - Status changed from 'open' to 'stalled'

Fri Dec 10 17:47:13 2010 user42 [...] zip.com.au - Correspondence added

Subject:	Re: [rt.cpan.org #62743] Primes() i*i loop vs bits=2^32-1
Date:	Sat, 11 Dec 2010 09:46:27 +1100
To:	bug-Bit-Vector [...] rt.cpan.org
From:	Kevin Ryde <user42 [...] zip.com.au>

"Steffen Beyer via RT" <bug-Bit-Vector@rt.cpan.org> writes: Show quoted text

> > long time

If you don't want to fix it immediately then start with a die or something if the bits size requested is too big, so it doesn't go into an infinite loop for large but otherwise apparently valid vectors.

Fri Dec 10 17:47:14 2010 The RT System itself - Status changed from 'stalled' to 'open'

Thu Feb 13 21:17:00 2014 DANAJ [...] cpan.org - Correspondence added

I realize this is old and relates to RTs 62744 and 62740 -- I just looked at it and thought I'd write down what I saw. Compile with N_word set to uint32_t, or run on a 32-bit machine. perl -Iblib/lib -Iblib/arch -MBit::Vector -E 'my $v = Bit::Vector->new(2**32-1); $v->Primes(); say $v->Norm()' shows bad behaviour (the inner loop wraps around). An ugly patch: #include <math.h> // In header N_word ilimit; // at top of function ilimit = (N_word) (sqrt(bits)+0.0001); for ( i = 3; i <= ilimit; i += 2 ) { if (BIT_VECTOR_TST_BIT(addr,i)) { N_word jlimit = bits-2*i; for (j = i*i ; j < bits; j += 2*i) { BIT_VECTOR_CLR_BIT(addr,j) if (j > jlimit) break; } } } Now correctly finishes in ~ 1 minute. No overflow for i. The j loop could probably be done cleaner -- this just adds an extra test so we stop if the next addition would push us over 'bits'. This includes the fixes to implement the SoE (skip composites and increment by 2*i).