Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

I am a brand new perl user but I have plenty of C++ experiance in coding. Right now I am writing a optimization program. What I have thuse far is this: 

@result=grid(2,-2,2,-2,4,1e-15,1000);
print"\n*@result*";
($user,$system,$cuser,$csystem) = times;
print "\n***\n$user\n***";


sub grid($_)
{
    my $max_rsd = $_[0];
    my $min_rsd = $_[1];
    my $max_shift = $_[2];
    my $min_shift = $_[3];
    my $resolution = $_[4];
    my $precision = $_[5];
    my $loopcount = 0; 
    my $delta_rsd = ($max_rsd-$min_rsd)*(1/$resolution);
    my $delta_shift = ($max_shift-$min_shift)*(1/$resolution);
    my @memory = (0,0,10000);
    
    do
    {    
        
#******Find Min Value*******
        for($i=$min_rsd;$i<=$max_rsd;$i=$i+$delta_rsd)
        {
    #print "(i: $i, Max: $max_rsd, Min: $min_rsd,\n $min_rsd+$delta_rs
+d)";        
            for($j=$min_shift;$j<=$max_shift;$j=$j+$delta_shift)
            {
                my $mse = function($i, $j);#*********************
$temp=$min_shift+$delta_shift;
    print "(j: $j, Max: $max_shift, Min: $min_shift,\n d: $delta_shift
+ +: $temp";
                if($mse < $memory[2])
                {
                    @memory = ($i, $j, $mse);
                    #print "($memory[0],$memory[1])";
                }
if($temp==$min_shift){print" true)\n";}
else{print" false)\n";}
            }     
        }

        #******Focus Parameters*******
        #$max_rsd = $memory[0]+$delta_rsd;
        #$min_rsd = $memory[0]-$delta_rsd;
        #$max_shift = $memory[1]+$delta_shift;
        #$min_shift = $memory[1]-$delta_shift;
        #$delta_rsd = ($max_rsd-$min_rsd)*(1/$resolution);
        #$delta_shift = ($max_shift-$min_shift)*(1/$resolution);
print"($memory[0], $max_rsd, $min_rsd,\n $delta_rsd)";

        if($memory[0] == $max_rsd or $memory[0] == $min_rsd)
        {
            $max_rsd = $memory[0]+$delta_rsd*$resolution*(1/2);
            $min_rsd = $memory[0]-$delta_rsd*$resolution*(1/2);
            $max_shift = $memory[1]+$delta_shift*$resolution*(1/2);
            $min_shift = $memory[1]-$delta_shift*$resolution*(1/2);
        }
        else
        {    
            $max_rsd = $memory[0]+$delta_rsd*(1/2);
            $min_rsd = $memory[0]-$delta_rsd*(1/2);
            $max_shift = $memory[1]+$delta_shift*(1/2);
            $min_shift = $memory[1]-$delta_shift*(1/2);
            $delta_rsd = ($max_rsd-$min_rsd)*(1/$resolution);
            $delta_shift = ($max_shift-$min_shift)*(1/$resolution);
        }

        $loopcount++;
        if($max_rsd == $min_rsd){print " e\n";}
        else{print " n\n";}
    }
    while((2*$delta_rsd>$precision));#and ($loopcount<$_[6]));    
    #while(($delta_rsd!=0) and ($delta_shift!=0) and ($loopcount<$_[6]
+));    
    return @memory;
}

sub function($_)  #arbitary function...will be given in the partually 
+written program
{
    return ($_[0]-50.02)**2+2;
}

[download]

From what I can tell the logic is good. The issue is that the program gets caught in the infinate loop below: 

for($j=$min_shift;$j<=$max_shift;$j=$j+$delta_shift)
            {
                my $mse = function($i, $j);#*********************
$temp=$min_shift+$delta_shift;
    print "(j: $j, Max: $max_shift, Min: $min_shift,\n d: $delta_shift
+ +: $temp";
                if($mse < $memory[2])
                {
                    @memory = ($i, $j, $mse);
                    #print "($memory[0],$memory[1])";
                }
if($temp==$min_shift){print" true)\n";}
else{print" false)\n";}
            }

[download]

From what I can gather, the $j should be increasing in defined increments of $delta_shift but I don't know if it is or not. The $temp and $min_shift appear as the same number on the screen but when I ask the computer if they are the same it tells me no.

My theory is this: the computer can only store a certain precision of a number. $min_shift is at the limit when I try to add $delta_shift to it so it is never really added to the number which would mean the number never increments as it should getting it stuck in an infinate loop. Could someone please take a look at it and let me know if I am right and then how I might go about fixing it. Thanks.

20060719 Janitored by Corion: Added formatting, code tags, as per Writeup Formatting Tips

Replies are listed 'Best First'.
Re: Infinite loop but no reason why
by philcrow (Priest) on Jul 19, 2006 at 13:48 UTC
    First, Perl's for( ; ; ) loop works just like the one in C (from which it was stolen).

    Second, no matter the language, it is not a good idea to compare floating point numbers for equality. Your hunch is correct, precision issues defeat equality. Usually you want to compare the numbers within some tolerance like this: 

      if ( abs( $first_num - $second_num ) < $small_num ) ) {
     ...
  }

    [download]
    where small_num is your tolerance for various errors (try .0005 or some such).

    Alternatively, you could round them to the same precision and compare.

    Phil

[reply]
[d/l]
Re: Infinite loop but no reason why
by Ovid (Cardinal) on Jul 19, 2006 at 14:43 UTC

    Looking at your code reveals several errors which could be caught with some error checking. For the specific section of code you point out, I note that you have this line:

    my $mse = function( $i, $j );

    But the function only uses one of those arguments:

    sub function($_) #arbitary function...will be given in the partually w
+ritten program
{
    return ( $_[0] - 50.02 )**2 + 2;
}

    [download]

    There a several problems here. First, the ($_) isn't doing anything. You think you're using a prototype but you're not. I'd remove it. How you actually want to handle your errors is a different story. Here's one way:

    use Carp qw/croak/; # put near the top of your program

sub function {
    if ( @_ != 2) {
        croak("function() requires two arguments");
    }
    my ( $x, $y ) = @_;
    # ... body of function
}

    [download]

    I also note that grid() is passed one more argument than you are using. You either need to test the number of arguments you are passing or test the value of each argument explicitly.

    Also, as noted above, you're trying to compare floating point numbers with ==. That's bad and is likely to fail. Instead, you want to determine the what precision is acceptable and round the numbers to that and do a string compare (with eq). Or you could try the Math::Precision module (I haven't used it) or something similar.

    To round the numbers and do a string compare, here's what perldoc perlop suggests (though it notes that this is expensive):

        sub fp_equal {
        my ($X, $Y, $POINTS) = @_;
        my ($tX, $tY);
        $tX = sprintf("%.${POINTS}g", $X);
        $tY = sprintf("%.${POINTS}g", $Y);
        return $tX eq $tY;
    }

    [download]

    Cheers,
    Ovid

    New address of my CGI Course.

[reply]
[d/l]
[select]
          sub fp_equal {
        my ($X, $Y, $POINTS) = @_;
        my ($tX, $tY);
        $tX = sprintf("%.${POINTS}g", $X);
        $tY = sprintf("%.${POINTS}g", $Y);
        return $tX eq $tY;
    }

    fp_equal($x, $y, 3);

      [download]

      could be replaced with 

          sub fp_equal {
        return abs($_[0] - $_[1]) < $_[2];
    }

    fp_equal($x, $y, 0.001);

      [download]

      Pros:

      • Faster because it doesn't convert the numbers to strings.
      • Supports arbitrary precisions (e.g. +-10, +-0.5), not just negative powers of 10.
[reply]
[d/l]
[select]

        I personally prefer relative precision, rather than absolute values, as you frequently don't know what the scale of the number is going to be for these sorts of calculations:

        sub fp_equal {
  my ($x,$y,$precision) = @_;
  $precision ||= 0.000001;

  return 1 if (! defined($x) and ! defined($y) );
  return 0 if (! defined($x) or  ! defined($y) );
  return 1 if ($x == $y);     # for 0 == 0
  ($x,$y) = ($y,$x) if (!$y); # for $y == 0
  return ( abs ( 1 - $x/$y ) <= $precision ) ? 1 : 0;
}

        [download]

        Update: I made an assumption based on the halving of the precision in the OP's problem that this was doing some sort of numerical analysis. ikegami is right in that sometimes you're looking at stepped measurements over a finite range, and so an absolute precision is necessary. (Most of my floating point comparisons are in scientific measurements, and I use relative precision so I don't have to have different definitions of precision for the units used and range of the measurements)

[reply]
[d/l]

Back to Seekers of Perl Wisdom