From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00,
	REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,e41c540121b84783
X-Google-Attributes: gid103376,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news1.google.com!news2.google.com!news4.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!newsfeed.arcor.de!news.arcor.de!not-for-mail
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Subject: Re: How to use "infinite" ?
Newsgroups: comp.lang.ada
User-Agent: 40tude_Dialog/2.0.14.1
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Reply-To: mailbox@dmitry-kazakov.de
Organization: cbb software GmbH
References: <jK6vf.3234$zc1.764@amstwist00>
 <ckgbli1bp6gj$.1b2lhn1y2j3y2$.dlg@40tude.net>
 <43BDACAF.C20E2840@fakeaddress.nil> <3Arvf.3306$zc1.1420@amstwist00>
Date: Fri, 6 Jan 2006 15:38:31 +0100
Message-ID: <ws0ebgpxajxz$.vxmtb68gfo6r.dlg@40tude.net>
NNTP-Posting-Date: 06 Jan 2006 15:38:23 MET
NNTP-Posting-Host: 1c278280.newsread4.arcor-online.net
X-Trace: 
 DXC=eYO18>6?Ghna0B5i45NL;d:ejgIfPPlddjW\KbG]kaMhA@_25la3nbb5[<kQiL3G4j[6LHn;2LCVn[<mhadbfdUkQ8[9>H45;Ki
X-Complaints-To: usenet-abuse@arcor.de
Xref: g2news1.google.com comp.lang.ada:2457
Date: 2006-01-06T15:38:23+01:00
List-Id: <comp.lang.ada>

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