loop problem with exit condition

loop problem with exit condition

[Ada novice]

Hi,
    I'm putting a simple code below with two loops. The Outer loop
ranges from -44.88 to 67.32 and should be subdivided equally in 300
points. The Inner loop ranges from 0.001 to 0.35 and should also be
subdivided in 300 points. I would like the limits of the range to be
included i.e. Outer loop has as first value -44.88 and last value as
67.32 . Inner loop has as first value 0.001 and last value as 0.35 .
Here's my code:

with Ada.Text_IO;
with Ada.Long_Float_Text_IO;
with Ada.Integer_Text_IO;



procedure Try is

   Count : Integer;
   Outer : Long_Float;
   Outer_Start : constant := -44.88;
   Outer_Limit : constant := 67.32;
   Outer_Step : constant := (Outer_Limit - Outer_Start)/299.0;

   Inner : Long_Float;
   Inner_Start : constant := 0.001;
   Inner_Limit : constant := 0.35;
   Inner_Step : constant := (Inner_Limit - Inner_Start)/99.0;


begin

   Count := 0;
   Outer := Outer_Start;


   loop
        Inner := Inner_Start;

        loop
          Count := Count + 1;

          exit when Inner > Inner_Limit - Inner_Step;

          Inner := Inner + Inner_Step;

   end loop;

      exit when Outer > Outer_Limit - Outer_Step;

      Outer := Outer + Outer_Step;


end loop;


      Ada.Text_IO.New_Line(2);
      Ada.Text_IO.Put("Inner after loop is (should be 0.35) ");
      Ada.Long_Float_Text_IO.Put (Item => Inner, Fore => 3, Aft  => 3,
Exp  => 0);
      Ada.Text_IO.New_Line(2);
      Ada.Text_IO.Put("Count after loop is ");
      Ada.Integer_Text_IO.Put (Item => Count);



end Try;


I am not able to get this working fine. The total time that both loops
should be entered must be 300 * 100 = 30k. I'm getting only Count as
29,700 and inner to be 0.346  (I understand that this is cause by my
exit condition).

How to create loops that follow my specifications?


Thanks a lot..

Re: loop problem with exit condition

[Ada novice]

One small mistake: Inner range is divided into 100 steps (not 300) as
I wrote. But the number is irrelevant and the code should
work fine with all limits.

Thanks.

Re: loop problem with exit condition

[Dmitry A. Kazakov]

On Sun, 26 Sep 2010 01:16:37 -0700 (PDT), Ada novice wrote:

> One small mistake: Inner range is divided into 100 steps (not 300) as
> I wrote. But the number is irrelevant and the code should
> work fine with all limits.

You have accumulation of errors, which typical when floating-point numbers
of same sign are summed. As the sum grows, addition looses more and more of
its precision. There are several strategies how to handle this problem. But
in your case the simplest way to remove bias would be to multiply the step:

with Ada.Text_IO;             use Ada.Text_IO;
with Ada.Long_Float_Text_IO;  use Ada.Long_Float_Text_IO;

procedure Try is
   Count : Integer;
   Outer : Long_Float;
   Outer_Start : constant := -44.88;
   Outer_Step  : constant := (67.32 - Outer_Start) / 299.0;

   Inner : Long_Float;
   Inner_Start : constant := 0.001;
   Inner_Step  : constant := (0.35 - Inner_Start) / 99.0;
begin
   Count := 0;
   Outer := Outer_Start;
   for I in 1..300 loop
      Outer := Outer_Start + Outer_Step * Long_Float (I - 1);
      for J in 1..100 loop
         Count := Count + 1;
         Inner := Inner_Start + Inner_Step * Long_Float (J - 1);
      end loop;
   end loop;
   Put ("Inner after loop is (should be 0.35) ");
   Put (Item => Inner, Fore => 3, Aft  => 3, Exp  => 0);
   New_Line;
   Put_Line ("Count after loop is" & Integer'Image (Count));
end Try;

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: loop problem with exit condition

[Ada novice]

Thanks a lot. You have provided me with a very clean code that does
its job well.
As I was working with Long_Float precision I was tempted to believe
that floating-point
accumulation errors wouldn't have such an adverse effect. Apart that,
I wasn't thinking very
much of using the For loop instead with its unity increment (I come
from a Matlab background).

When writing a For loop, I read that it's good practice to put e.g.
For I in Range 1..300  as
just putting For I in 1..300 will not tell the compiler what kind of
number representation it must
have for the numbers 1 and 300.


Thanks again.
YC

Re: loop problem with exit condition

[Yannick Duchêne (Hibou57)]

Le Sun, 26 Sep 2010 11:10:24 +0200, Dmitry A. Kazakov  
<mailbox@dmitry-kazakov.de> a écrit:
> in your case the simplest way to remove bias would be to multiply the  
> step:
> […]
>          Inner := Inner_Start + Inner_Step * Long_Float (J - 1);

I did not knew that. Why is an iterative addition less accurate than a  
multiplication ? Does it have something to deal with adjustment of the  
exponent ? (the one of the float's internal representation)

-- 
Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour  
les chiens.

Re: loop problem with exit condition

[Niklas Holsti]

Yannick Duchêne (Hibou57) wrote:
> Le Sun, 26 Sep 2010 11:10:24 +0200, Dmitry A. Kazakov 
> <mailbox@dmitry-kazakov.de> a écrit:
>> in your case the simplest way to remove bias would be to multiply the 
>> step:
>> […]
>>          Inner := Inner_Start + Inner_Step * Long_Float (J - 1);
> 
> I did not knew that. Why is an iterative addition less accurate than a 
> multiplication ? Does it have something to deal with adjustment of the 
> exponent ? (the one of the float's internal representation)

Yes. If you add two floating-point numbers A+B, and the binary exponent 
Ae of A is larger than the exponent Be of B, the mantissa of B will be 
shifted right by Ae-Be bits before being added to the mantissa of A, so 
the addition loses ("shifts out") about this many of the less 
significant bits of the mantissa of B. You are effectively adding A+Bt, 
where Bt is B with the lost bits set to zero (assuming positive numbers 
-- I haven't figured out what happens with negative numbers).

If you compute A+N*B by iteratively adding B to A, N times, you are 
effectively computing the approximation A+N*Bt (more or less; if the 
binary exponent of the growing sum becomes larger than Ae, you will lose 
even more precision). The error is N*(B-Bt), thus growing with N.

In the formula A+N*B, as suggested by Dmitry (and as indeed is good 
practice), the multiplication N*B is as accurate as the floating-point 
representation allows -- no mantissa bits are lost by exponent 
adjustments. If the product is X, the addition A+X is again as accurate 
as possible. Some bits of the smaller term (A or X) may again be lost in 
the addition, but this loss is not cumulative.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: loop problem with exit condition

[Dmitry A. Kazakov]

On Tue, 26 Oct 2010 10:02:32 +0300, Niklas Holsti wrote:

> Yannick Duchêne (Hibou57) wrote:
>> Le Sun, 26 Sep 2010 11:10:24 +0200, Dmitry A. Kazakov 
>> <mailbox@dmitry-kazakov.de> a écrit:
>>> in your case the simplest way to remove bias would be to multiply the 
>>> step:
>>> […]
>>>          Inner := Inner_Start + Inner_Step * Long_Float (J - 1);
>> 
>> I did not knew that. Why is an iterative addition less accurate than a 
>> multiplication ? Does it have something to deal with adjustment of the 
>> exponent ? (the one of the float's internal representation)
> 
> Yes. If you add two floating-point numbers A+B, and the binary exponent 
> Ae of A is larger than the exponent Be of B, the mantissa of B will be 
> shifted right by Ae-Be bits before being added to the mantissa of A, so 
> the addition loses ("shifts out") about this many of the less 
> significant bits of the mantissa of B. You are effectively adding A+Bt, 
> where Bt is B with the lost bits set to zero (assuming positive numbers 
> -- I haven't figured out what happens with negative numbers).
> 
> If you compute A+N*B by iteratively adding B to A, N times, you are 
> effectively computing the approximation A+N*Bt (more or less; if the 
> binary exponent of the growing sum becomes larger than Ae, you will lose 
> even more precision). The error is N*(B-Bt), thus growing with N.
> 
> In the formula A+N*B, as suggested by Dmitry (and as indeed is good 
> practice), the multiplication N*B is as accurate as the floating-point 
> representation allows -- no mantissa bits are lost by exponent 
> adjustments. If the product is X, the addition A+X is again as accurate 
> as possible. Some bits of the smaller term (A or X) may again be lost in 
> the addition, but this loss is not cumulative.

For more complicated cases there exist summation algorithms reducing
precision loss, e.g. the Kahan algorithm:

   http://en.wikipedia.org/wiki/Kahan_summation_algorithm

(Numeric methods are exiting)

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: loop problem with exit condition

[Brian Drummond]

On Tue, 26 Oct 2010 04:59:30 +0200, Yannick Duch�ne (Hibou57)
<yannick_duchene@yahoo.fr> wrote:

>Le Sun, 26 Sep 2010 11:10:24 +0200, Dmitry A. Kazakov  
><mailbox@dmitry-kazakov.de> a �crit:
>> in your case the simplest way to remove bias would be to multiply the  
>> step:
>> [�]
>>          Inner := Inner_Start + Inner_Step * Long_Float (J - 1);
>
>I did not knew that. Why is an iterative addition less accurate than a  
>multiplication ? Does it have something to deal with adjustment of the  
>exponent ? (the one of the float's internal representation)

An iterative addition and a multiplication both have rounding error bounded by
epsilon.

N iterative additions versus one multiplication, however...

- Brian