How to use "infinite" ?

How to use "infinite" ?

[Reinert Korsnes]

Hi,

is it a natural way to use "infinite" in Ada95 ?

What I mean is that I would like a "number" X (= "infinite")
such that:

(i + X = X) = true

for any normal (say) Integer i.

reinert

Re: How to use "infinite" ?

[Dmitry A. Kazakov]

On Thu, 05 Jan 2006 11:42:22 +0100, Reinert Korsnes wrote:

> is it a natural way to use "infinite" in Ada95 ?

Which way, you didn't specify any!

> What I mean is that I would like a "number" X (= "infinite")
> such that:
> 
> (i + X = X) = true
> 
> for any normal (say) Integer i.

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;
   function "+" (Left : Infinite_Integer; Right : Finite_Integer
      return Infinite_Integer;
   function "+" (Left, Right : Infinite_Integer)
      return Infinite_Integer;
   . . .
   --
   -- Relational operations
   --
   function "=" (Left : Finite_Integer; Right : Infinite_Integer)
      return Boolean;
   function "=" (Left : Infinite_Integer; Right : Finite_Integer
      return Boolean;
   function "=" (Left, Right : Infinite_Integer)
      return Boolean;
   . . .
private
   --
   -- Some appropriate implementation
   --
   . . .
end Integers_With_Infinity_Ideals;

BTW, for relational operations you could use tri-state logic:

   (infinity = infinity) = uncertain

instead of Boolean logic.

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

Re: How to use "infinite" ?

[Gautier Write-only]

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.).
______________________________________________________________
Gautier     --     http://www.mysunrise.ch/users/gdm/index.htm
Ada programming -- http://www.mysunrise.ch/users/gdm/gsoft.htm

NB: For a direct answer, e-mail address on the Web site!

Re: How to use "infinite" ?

[Reinert Korsnes]

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

reinert


> ______________________________________________________________
> Gautier     --     http://www.mysunrise.ch/users/gdm/index.htm
> Ada programming -- http://www.mysunrise.ch/users/gdm/gsoft.htm
> 
> NB: For a direct answer, e-mail address on the Web site!

Re: How to use "infinite" ?

[Dmitry A. Kazakov]

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