Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

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.

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:

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";

The C++ version:

#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; }

...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:

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";

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:

..... (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.

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.

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.

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.

Update: 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.


Dave


In reply to "Free to wrong pool" error. by davido

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others exploiting the Monastery: (8)
    As of 2014-12-18 05:42 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (42 votes), past polls