Re: How to use "infinite" ?

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Fri, 06 Jan 2006 11:25:02 +0100, Reinert Korsnes wrote:

> Gautier Write-only wrote:
> 
>> Dmitry A. Kazakov:
>> 
>>> You should define an abstract data type to represent the set of integer
>>> numbers + ideals you want (such as "negative infinity", "positive
>>> infinity") . For example a universal package could be generic:
>>> 
>>> generic
>>>    type Finite_Integer is range <>;
>>> package Integers_With_Infinity_Ideals is
>>>    type Infinite_Integer is private;
>>>    --
>>>    -- Unary operations
>>>    --
>>>    function "+" (Left : Infinite_Integer) return Infinite_Integer;
>>>    function "-" (Left : Infinite_Integer) return Infinite_Integer;
>>>    --
>>>    -- Dyadic operations
>>>    --
>>>    function "+" (Left : Finite_Integer; Right : Infinite_Integer)
>>>       return Infinite_Integer;
>> [...]
>> 
>> Great idea, you just drafted a (or the first ?) computer package for
>> nonstandard analysis!
>> 
>> I strongly suggest to use the (hem...) standard wording of nonstandard
>> analysis for the types (unlimited, infinitesimal, etc.).
> 
> :-)
> 
> well, for my limited "hack-programming" I would
> like to replace the following with something simpler:
> 
> if a /= Integer'Last and b /= Integer'Last then
>    if a >  a + b then
>       a := a + b;
>    end if;
> end if;
> 
> I tried to represent "infinite" with Integer'Last -
> directly from the mathematical specification/problem formulation 
> given. Maybe it is not a good idea.
> 
> Note, by the way, that the construct above
> may be rather ugly if a and b are complex expressions....

You have to decide what you want. Code simplicity is achieved by
abstraction. ADT hides nasty implementation details.

As for memory vs. performance trade-off, well, if you want a dense
representation, then you have to pay for that. Further you have to decide
how often infinity could appear. If it is a rare beast, then you could
indeed use integer arithmetic, catch Constraint_Error on overflows to
perform analysis on infinity.

If you have a suspicion that exception handling could take too much time,
you could use modular numbers instead. Something like:

   Positive_Infinity : constant Infinite_Integer;
   Negative_Infinity : constant Infinite_Integer;
   Undefined         : constant Infinite_Integer;
      -- If you want to sum infinities of different signs, you will need
      -- this ideal as well
private
   Bits : constant := 32;
   type Ring is mod 2**Bits; -- Reserve two upper numbers for ideals
   PI : constant Ring := 2**(Bits - 1) - 1;
   UI : constant Ring := 2**(Bits - 1);
   NI : constant Ring := 2**(Bits - 1) + 1;

   type Infinite_Integer is new Ring;
   Positive_Infinity : constant Infinite_Integer := Infinite_Integer (PI);
   Undefined         : constant Infinite_Integer := Infinite_Integer (UI);
   Negative_Infinity : constant Infinite_Integer := Infinite_Integer (NI);

--
-- + Implementation, looks lengthy, but it is one + and 3 comparisons
--
function "+" (Left, Right : Infinite_Integer)  return Infinite_Integer is
   L : constant Ring := Ring (Left);
   R : constant Ring := Ring (Right);
   Result : constant Ring := L + R;
begin
   if L < PI then
      if R < PI then
         -- Left and Right are positive
         if Result < PI then
            return Infinite_Integer (Result);
         else
            return Positive_Infinity; -- Positive overflow
         end if;
      elsif R > NI then
         -- Left is positive, Right is negative
         return Infinite_Integer (Result); -- Can't overflow
      else
         return Right; -- Infinity swallows Left
      end if;
   elsif L > NI then
      if R < PI then
         -- Left and Right are negative
         return Infinite_Integer (Result);
      elsif R > NI then
         -- Left is negative, Right is positive
         if Result > NI then
            return Infinite_Integer (Result);
         else
            return Negative_Infinity; -- Negative overflow
         end if;
      else
         return Right; -- Infinity swallows Left
      end if;
   else
      if R < PI or else R > NI then
         return Left; -- Infinity swallows Right
      else
         if L = PI then
            if R = PI then
               return Positive_Infinity;
            end if;
         elsif L = NI then
            if R = NI then
               return Negative_Infinity;
            end if;
         end if;
         return Undefined;
             -- Cannot figure out the result, maybe Constraint_Error
             -- exception were more appropriate here
      end if;
   end if;
end "+";   

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