Skip Menu |
 

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

Report information
The Basics
Id: 62743
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() 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>
Download (untitled) / with headers
text/plain 544b
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.
Download (untitled) / with headers
text/plain 735b
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.
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>
Download (untitled) / with headers
text/plain 278b
"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.
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).


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.