The following is a real bug that appeared in real code by yours truly. (Code which was written late at night under pressure. *ahem*)

I think that trying to see what causes a possible infinite loop in this code is rather instructive. 

sub init_selections {
  my $self = shift;
  my $slice_count = shift;

  my $cur_balances = $self->{cur_balances};
  my $balance = 0;
  $balance += $_ foreach @$cur_balances;

  my @selections;
  my $select = 0;
  my $cur_balance = $cur_balances->[0];
  foreach my $i (1..$slice_count) {
    # Move move selected forward until we are at the current
    # position.
    while ($cur_balance < ($balance * $i / $slice_count)) {
      $cur_balance += $cur_balances->[++$select];
    }
    push @selections, $select;
  }
  return $self->{selections} = \@selections;
}

[download]
(Assume that the cur_balances are all positive numbers greater than 10,000, and their sum is under 2 billion.)

UPDATE
Oops, forgot to ask. Please hide answers as described in How to present spoilers :-). Thanks.

UPDATE 2
mdillon pointed out to me that I should mention that "billion" here is the US billion, ie 10**9. Also the slice count may be assumed to be an integer in the range 5-100.

Replies are listed 'Best First'.
Re: Instructive bug
by mpeppler (Vicar) on Mar 05, 2002 at 16:39 UTC
    It's got to be the 
    $balance * $i / $slice_count

    [download]
    that is causing the problem. My guess is that $balance * $i ends up greater than 32 bits, so it converts to a float, and when divided by $slice_count it ends up larger than $cur_balance even when $i == $slice_count.

    Michael

[reply]
[d/l]
      That's what I thought too, but won't $cur_balance just keep getting bigger until it's larger than $balance anyway?

      UPDATE: No, it won't. It will run out of balances, and if there's a floating point error (inaccuracy?) the loop might never end.

[reply]
      You have the right idea. I actually got floats earlier than the 32-bit barrier though. Can anyone other than mpeppler guess why?

      And for perrin, what I did about it was put in a slight fudge factor to handle small roundoffs, and on the inner loop I put a fatal check for overrunning the balances array in case the hack failed. I have had no problems since.

[reply]
        Well, it seems rather as if you were dealing with money here, in which case I imagine that you started out with floating-point values, no?


        If God had meant us to fly, he would *never* have given us the railroads.
            --Michael Flanders

[reply]
        The division will cause a floating point coversion, I believe.
[reply]

      Spoiler? ...don't cheat

      I think that the reason tilly noted that the sum is less that 2 billion was to indicate that the 32-bit barrier is not the problem.

      update: I just realized that you said that $balance * $i could have 32 bit problems, not $balance; my bad.

[reply]
[d/l]
[select]
Re: Instructive bug
by japhy (Canon) on Mar 05, 2002 at 17:14 UTC
    Since I have no way of knowing exactly what type of data you have...
    I think it might be 
    while ($cur_balance < ($balance * $i / $slice_count)) {
  $cur_balance += $cur_balances->[++$select];
}

    [download]
    that is killing you. If the data is such that @$cur_balances can be exhausted, then the while loop will never end because $cur_balances->[++$select] will keep returning 0.

    _____________________________________________________
    Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a (from-home) job
    s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

[reply]
[d/l]
[select]
Re: Instructive bug
by mdillon (Priest) on Mar 05, 2002 at 21:24 UTC
    While in a /msg exchange with tilly trying to understand why I was having a hard time with the details of floating-point imprecision when representing some decimal fractions as binary fractions, I brought up a system called "Standard Decimal Arithmetic". Since tilly thought the link I sent him would be relevant to this discussion (and I'd say it's a good read nevertheless), I'm posting it hear for folks to check out: Standard Decimal Arithmetic. There is a little talk here of this making it into Perl 6.

    Update: for those daunted or otherwise unwilling to browse, a lot of good info is available in one place here.

[reply]
Re: Instructive bug
by hakkr (Chaplain) on Mar 05, 2002 at 17:06 UTC

    I brought down a server once by accidently writing a function that had an unintended recursive call in a loop.

    Cue 10000's of DBI connections and bang.
    I make sure I don't give my variables the same names as subs now;)

    I'd say it's infinite cos your loops test conditions are never satisified :)

    my guess is you got bad things going on with negative numbers
[reply]

Back to Meditations