perlquestion
davido
<p>A student I know asked me to help him find a bug in a C++ program that was using a brute force approach to finding all primes between 1 and n. The problem wasn't hard to find, and not very interesting. But with a few spare minutes on a Sunday I rewrote his C++ program using "C'ish Perl", and in so doing seem to have stumbled into a real bug.</p>
<p>Here's an example of the initial Perl code, which is almost an exact literal translation of the C++ code, and which DOES NOT exhibit the bad behavior:
</p>
<readmore>
<c>
use strict;
use warnings;
use v5.12;
use constant TOP => 1000000;
say "1 is prime.";
say "2 is prime.";
my $found = 2; # We already found 1 and 2.
for( my $i = 3; $i < TOP; $i += 2 ) {
my $qualifies = 1;
for( my $j = $i - 2; $j > 1; $j -= 2 ) {
if( $i % $j == 0 ){
$qualifies = 0;
last;
}
}
if( $qualifies ) {
say "$i is prime.";
$found++;
}
}
say "Found $found primes between 1 and ", TOP, ".\n";
</c>
</readmore>
<p>The C++ version:
</p>
<readmore>
<c>
#include <iostream>
using namespace std;
// First 501 primes are found from 1 to 3571
const int SEARCH_TO = 1000000;
const int SEARCH_START = 3;
/*
* You can double check by comparing with the link below:
* http://en.wikipedia.org/wiki/List_of_prime_numbers
* to verify accuracy.
*/
int main() {
cout << "1 is a prime number." << endl;
cout << "2 is a prime number." << endl;
int found = 2;
int i;
for ( i = SEARCH_START; i < SEARCH_TO; i+=2 ) {
int qualifies = 1;
for ( int j = i-2 ; j > 1; j-=2 ){
if ( i % j == 0 ) {
qualifies = 0;
break;
}
}
if ( qualifies ) {
cout << i << " is a prime number." <<endl;
found++;
}
}
cout << "Found " << found << " primes in range "
<< 1 << " to " << SEARCH_TO << ".\n";
return 0;
}
</c>
</readmore>
<p>...and that worked fine; no bad behavior. Then I decided to look at it without a flag, by labeling the outer loop and using "next LABEL" to short circuit to it. Here is an example:</p>
<c>
use strict;
use warnings;
use v5.12;
use constant TOP => 1000000;
say "1 is prime.";
say "2 is prime.";
my $found = 2; # We already found 1 and 2.
OUTER: for( my $i = 3; $i < TOP; $i += 2 ) {
for( my $j = $i - 2; $j > 1; $j -= 2 ) {
( not $i % $j ) && next OUTER;
}
say "$i is prime.";
$found++;
}
say "Found $found primes between 1 and ", TOP, ".\n";
</c>
<p>After watching numbers scroll past me for a few moments I hit CTRL-C (windows console), and was surprised to get an error message from the "this shouldn't happen" category:</p>
<c>
..... (long list of primes omitted )....
59753 is prime.
59771 is prime.
59779 is prime.
59791 is prime.
59797 is prime.
59809 is prime. <-------I hit CTRL-C after this iteration.
Out of memory!
Use of uninitialized value $j in modulus (%) at primes.pl line 17.
Use of uninitialized value $i in modulus (%) at primes.pl line 17.
Illegal modulus zero at primes.pl line 17.
Free to wrong pool 2f4d50 not 1000 during global destruction.
</c>
<p>I ran it a few other times. Sometimes there was no problem. Sometimes the output from the end of the run had a bunch of "line noise" after the last prime. And a couple times it said, "Panic..." with a similar error message.</p>
<p>This post isn't about how to efficiently generate primes, or how to write such code elegantly. I'll be the first to admit this is a C-ish style approach, and the algorithm used is dumb brute force.</p>
<p>The question is, does anyone know why there's an error occurring here? The errors generated really are in the category of errors that we shouldn't see. Since I can't produce it on 100% of the runs, I don't know how to wrap it all in a test that would demonstrate the bug reliably. If I could at least generate it 100% of the time (and without requiring the intervention of "CTRL-C" keyboard input) I might be able to send in a meaningful bug report.</p>
<p><b>Update:</b> A couple of responses (as well as my own testing on Linux) have led me to believe this problem is not going to manifest itself on Linux. While I haven't heard from any Mac users, I suspect this is a problem only under a Windows environment. Whether or not it's limited to Strawberry Perl, or only to version 5.12.3, I don't know yet.</p>
<div class="pmsig"><div class="pmsig-281137">
<br /><p>Dave</p>
</div></div>