Re: Renaming Fixed Point Mutiplicative operator in Ada 95

[eachus@spectre.mitre.org (Robert I. Eachus)]

In article <matthew_heaney-ya023680002105981805050001@news.ni.net> matthew_heaney@acm.org (Matthew Heaney) writes:

  > I'm confused by your answer, because a fixed point divide returns universal
  > fixed. How does one get a divide by zero exception, since 1) we've proven z
  > is in fact not zero, and 2) the universal fixed result has infinite range?

   You won't get a divide by zero, but with fixed point it is possible
to have a divide by a value whose abolute value is less than one, and
where the result overflows.  Explicitly testing for that condition is
possible but painful.  (In what follows, assume that type Fixed is
represented as a signed 32-bit integer.  The general case requires
using additional instantiation tricks which would clutter up the
discussion, especially if your compiler supports 64-bit fixed types
and no 64 bit integer type.)

   First specify the operation:

   generic
     type Fixed is delta <>;
     with procedure Handle_Error;
   function Divide(X,Y: Fixed) return Fixed;

   function Divide(X,Y: Fixed) return Fixed is
     type Integer_32 is range -2**31..2**31-1;
   begin
-- The initial problem has three overflow cases, and one where
-- overflow can't occur:

-- 1) Divisor is zero.

   if Y = 0.0 then Handle_Error;

-- 2) Get rid of Fixed'Small >= 1.0;

   elsif Fixed'Small >= 1.0 then return X/Y;

-- 3) X and Y have the same sign, and X/Y > Fixed'Last
--    Note a special case here: for a full range type where X =
--    Fixed'First, division by -1.0 will cause overflow.
    elsif X > 0.0 and Y > 0.0 then

--    We want to test whether there will be an overflow, without
--    causing the overflow.  Using mathematical not computer
--    arithmetic, X/Y is equivalent to (X * Fixed'Small) / (Y *
--    Fixed'Small) overflow occurs only when this result is strictly
--    greater than Fixed'Last/Fixed'Small.  (There are values greater
--    than Fixed'Last which can legitimately be rounded to Fixed'Last,
--    but they can't be generated by a Fixed * Fixed multiply if 1.0
--    is a model number of the type.)

      if Integer_32(X / Fixed'Small) / Integer_32(Y / Fixed'Small) >
        Integer_32(Fixed'Last / Fixed'Small)
      then Handle_Error;
      else return X/Y;
      end if;

-- Note that dividing by Fixed'Small and converting to integer is a no-op.
-- Yes there is one extra integer divide here, but the divides by
-- Fixed'Small should all be either optimized away or special cased 
-- by the compiler.  If not, replace them with Unchecked_Conversions.

-- You can change the computation above to use an integer multiply:
--     if abs Integer_32(X / Fixed'Small) > 
--       abs (Integer_32(Y / Fixed'Small)) *
--         Integer_32(Fixed'Last / Fixed'Small)
--    then...
-- but now there is a problem with overflow on the multiply.  Since
-- one factor is a constant, you can compute for any type the value
-- where the overflow will occur and just omit the calculation if Y is
-- above that value.  But we also know that, excluding the special
-- case mentioned above if abs Y >= 1.0, overflow can't occur.  Since
-- the special case can't happen below, I'll demonstrate there.

-- 3) X and Y have opposite signs, and X/Y < Fixed'First

    else
      if abs Y < 1.0 and then
          abs Integer_32(X / Fixed'Small) <
            - ( abs (Integer_32(Y / Fixed'Small)) *
                Integer_32(Fixed'First / Fixed'Small))
      
      then Handle_Error;
      else return X/Y;
      end if;
    end if;
  end Divide;

  -- Note that this code is NOT guarenteed to work if 1.0 is not an
  -- integer multiple of Fixed'Small.


--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...