how to round integers

how to round integers

[Cephus�]

I am trying to remember the "golden rule" for integer division rounding.

I am trying to average something (both integers) and I can't remember how to
round without using floating point.

Like say I am trying to divide 26/3  --- I would get 8 remainder 2

but that should round up to 9. How can I do this? I know it has something to
do with the dividend....but I can't for the life of me remember. thanks!

Beau

Re: how to round integers

[Charles LaCour]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 707 bytes --]

You would get 8 2/3 which becomes 8.66666....  This rounds up to nine
because .6 >= .5

I'm not an Ada programmer, but this question is not about Ada so I thought
it would be ok.

"Cephus�" <beau@hiwaay.net> wrote in message
news:veqcdrsf7o7q57@corp.supernews.com...
> I am trying to remember the "golden rule" for integer division rounding.
>
> I am trying to average something (both integers) and I can't remember how
to
> round without using floating point.
>
> Like say I am trying to divide 26/3  --- I would get 8 remainder 2
>
> but that should round up to 9. How can I do this? I know it has something
to
> do with the dividend....but I can't for the life of me remember. thanks!
>
> Beau
>
>

Re: how to round integers

[Cephus�]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 968 bytes --]



Charles LaCour wrote:
> You would get 8 2/3 which becomes 8.66666....  This rounds up to nine
> because .6 >= .5
>
> I'm not an Ada programmer, but this question is not about Ada so I
> thought it would be ok.
>
> "Cephus�" <beau@hiwaay.net> wrote in message
> news:veqcdrsf7o7q57@corp.supernews.com...
>> I am trying to remember the "golden rule" for integer division
>> rounding.
>>
>> I am trying to average something (both integers) and I can't
>> remember how to round without using floating point.
>>
>> Like say I am trying to divide 26/3  --- I would get 8 remainder 2
>>
>> but that should round up to 9. How can I do this? I know it has
>> something to do with the dividend....but I can't for the life of me
>> remember. thanks!
>>
>> Beau

no you can't do this because if you don't specifically type cast an integer
into a float, you have no decimals. So if you say 26/3, you just get 8 in
your variable...in other words it truncates the integer...

Re: how to round integers

[Jeffrey Creem]

"Charles LaCour" <clacour1@cox.net> wrote in message
news:VkbHa.72213$%42.66485@fed1read06...
> You would get 8 2/3 which becomes 8.66666....  This rounds up to nine
> because .6 >= .5
>
> I'm not an Ada programmer, but this question is not about Ada so I thought
> it would be ok.
>

Oh well..Thanks for trying.  You are correct that this is not about Ada but
you are incorrect
about the answer. Integer math (C, Ada, C++, etc) truncates. It does not
round. It would not matter
if the fraction were 0.99999999   it would still truncate.

If you did the work in float and converted to an integer, it would of course
round but I don't think that is what the original poster was asking.

Re: how to round integers

[Martin Dowie]

"Cephus�" <beau@hiwaay.net> wrote in message news:<veqcdrsf7o7q57@corp.supernews.com>...
> I am trying to remember the "golden rule" for integer division rounding.
> 
> I am trying to average something (both integers) and I can't remember how to
> round without using floating point.
> 
> Like say I am trying to divide 26/3  --- I would get 8 remainder 2
> 
> but that should round up to 9. How can I do this? I know it has something to
> do with the dividend....but I can't for the life of me remember. thanks!

This works :-)


with Ada.Text_IO; use Ada.Text_IO;

procedure Demo is

   procedure Calculate (Value, Devisor : Integer;
                        Result, Remainder : out Integer) is
   begin
      Remainder := Value rem Devisor;
      Result    := (Value - Remainder) / Devisor;
   end Calculate;

   Result, Remainder : Integer;
begin
   Calculate(26, 3, Result, Remainder);
   Put_Line (Integer'Image (Result) & " " & Integer'Image(Remainder));
end Demo;

Re: how to round integers

[David C. Hoos]

Declare the following function:

function Rounded_Divide (Dividend : Integer; Divisor : Integer) return
Integer
is
begin
   return (Dividend + Divisor - 1) / Divisor;
end Rounded_Divide;

Then compute average as follows:

Average := Rounded_Divide (Sum_Of_Values, Number_Of_Values);

"Cephus�" <beau@hiwaay.net> wrote in message
news:veqcdrsf7o7q57@corp.supernews.com...
> I am trying to remember the "golden rule" for integer division rounding.
>
> I am trying to average something (both integers) and I can't remember how
to
> round without using floating point.
>
> Like say I am trying to divide 26/3  --- I would get 8 remainder 2
>
> but that should round up to 9. How can I do this? I know it has something
to
> do with the dividend....but I can't for the life of me remember. thanks!
>
> Beau
>
>
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada
>
>

Re: how to round integers (Figured it out!)

[Cephus�]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 757 bytes --]



Cephus� wrote:
> I am trying to remember the "golden rule" for integer division
> rounding.
>
> I am trying to average something (both integers) and I can't remember
> how to round without using floating point.
>
> Like say I am trying to divide 26/3  --- I would get 8 remainder 2
>
> but that should round up to 9. How can I do this? I know it has
> something to do with the dividend....but I can't for the life of me
> remember. thanks!
>
> Beau

I figured it out. Thanks for the help (although I was asking how to do
something, not the code to do it, usually you would never get that in a
newsgroup).

All you do is REM the divisor and dividend. Then double it. If that number
is greater than the divisor, then add one. Otherwise don't...

Beau

Re: how to round integers (Figured it out!)

[David C. Hoos]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1140 bytes --]

It's simpler to just add one less than the divisor to the dividend before
dividing.


"Cephus�" <beau@hiwaay.net> wrote in message
news:verddee9cbo317@corp.supernews.com...
>
>
> Cephus� wrote:
> > I am trying to remember the "golden rule" for integer division
> > rounding.
> >
> > I am trying to average something (both integers) and I can't remember
> > how to round without using floating point.
> >
> > Like say I am trying to divide 26/3  --- I would get 8 remainder 2
> >
> > but that should round up to 9. How can I do this? I know it has
> > something to do with the dividend....but I can't for the life of me
> > remember. thanks!
> >
> > Beau
>
> I figured it out. Thanks for the help (although I was asking how to do
> something, not the code to do it, usually you would never get that in a
> newsgroup).
>
> All you do is REM the divisor and dividend. Then double it. If that number
> is greater than the divisor, then add one. Otherwise don't...
>
> Beau
>
>
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada
>

Re: how to round integers (Figured it out!)

[Cephus�]

David C. Hoos wrote:
> It's simpler to just add one less than the divisor to the dividend
> before dividing.


well look at if the total is 25. in your example, 25+3-1 = 27. That would
give you 27/3 = 9

but it is really 25/3 which equals 8 remainder 1 which is not enough to
round up...

Beau

Re: how to round integers (Figured it out!)

[David C. Hoos]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 940 bytes --]

You are quite right.  I was thinking of the algorithm which always
rounds up if there is any remainder -- e.g., if you need to know how
many boxes are required to ship N items, if M items will fit in a box.

The algorithm you need (which will do the job without any comparisons
and conditional operations is

  (Dividend + Dividend + Divisor) / (Divisor + Divisor)

"Cephus�" <beau@hiwaay.net> wrote in message
news:vereehn58o9be1@corp.supernews.com...
>
>
> David C. Hoos wrote:
> > It's simpler to just add one less than the divisor to the dividend
> > before dividing.
>
>
> well look at if the total is 25. in your example, 25+3-1 = 27. That would
> give you 27/3 = 9
>
> but it is really 25/3 which equals 8 remainder 1 which is not enough to
> round up...
>
> Beau
>
>
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada
>

Re: how to round integers (Figured it out!)

[Robert I. Eachus]

David C. Hoos wrote:
> You are quite right.  I was thinking of the algorithm which always
> rounds up if there is any remainder -- e.g., if you need to know how
> many boxes are required to ship N items, if M items will fit in a box.
> 
> The algorithm you need (which will do the job without any comparisons
> and conditional operations is
> 
>   (Dividend + Dividend + Divisor) / (Divisor + Divisor)
> 
> "Cephus�" <beau@hiwaay.net> wrote in message
> news:vereehn58o9be1@corp.supernews.com...

Unless it causes Constraint_Error. ;-)  If you really want to implement 
a divide with rounding in Ada, I'd use the algorithm above, plus an 
exception handler that used a more complex version that avoided 
overflow.  Something like the version below.  Incidently, notice that 
this package will not work correctly with modular types--and can't be 
instantiated with them in any case.

It would also be interesting if someone tried this version, one that 
didn't need an exception handler, and one that had no exception handler 
and no temporary variables, and checked the execution speed.  (Which one 
will win will depend on the compiler and the optimization levels, so 
there is no "right" answer.)

with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Rounding is

   generic
     type Int is range <>;
   function Rounding(Dividend, Divisor: Int) return Int;

   function Rounding(Dividend, Divisor: Int) return Int is
   begin
     return (Dividend + Dividend + Divisor) / (Divisor + Divisor);
   exception
     when Constraint_Error =>
       declare
         Temp: Int;
       begin
         Temp := Dividend rem Divisor;
         if Temp > Int'Last/2 or else Temp * 2 >= Divisor
         then return Dividend/Divisor + 1;
         -- Divisor is always less than or equal to Int'Last
         else return Dividend/Divisor;
         end if;
       end;
   end Rounding;

   function Round is new Rounding(Integer);

begin

   Put_Line(" Rounding (2,3) is " & Integer'Image(Round(2,3)));
   Put_Line(" Rounding (7,5) is " & Integer'Image(Round(7,5)));
   Put_Line(" Rounding (25, 10) is " & Integer'Image(Round(25,10)));
   Put_Line(" Rounding (1_000_000_000, 1_500_000_000) is " &
                   Integer'Image(Round(1_000_000_000, 1_500_000_000)));
   Put_Line(" Rounding (1_000_000_000, 2_000_000_000) is " &
                   Integer'Image(Round(1_000_000_000, 2_000_000_000)));
   Put_Line(" Rounding (1_500_000_000, 2_000_000_000) is " &
                   Integer'Image(Round(1_500_000_000, 2_000_000_000)));
   Put_Line(" Rounding (1_500_000_000, 2_000_000_001) is " &
                   Integer'Image(Round(1_500_000_000, 2_000_000_001)));
   Put_Line(" Rounding (1_500_000_000, Integer'Last) is " &
                   Integer'Image(Round(1_500_000_000, Integer'Last)));
end Test_Rounding;

Re: how to round integers (Figured it out!)

[Jeffrey Carter]

Robert I. Eachus wrote:
>   function Rounding(Dividend, Divisor: Int) return Int is
>   begin
>     return (Dividend + Dividend + Divisor) / (Divisor + Divisor);
>   exception
>     when Constraint_Error =>
>       declare
>         Temp: Int;
>       begin
>         Temp := Dividend rem Divisor;
>         if Temp > Int'Last/2 or else Temp * 2 >= Divisor
>         then return Dividend/Divisor + 1;
>         -- Divisor is always less than or equal to Int'Last
>         else return Dividend/Divisor;
>         end if;
>       end;
>   end Rounding;
> 
>   function Round is new Rounding(Integer);

What happens in the case of negative arguments?

-- 
Jeff Carter
"C++ is like jamming a helicopter inside a Miata
and expecting some sort of improvement."
Drew Olbrich

Re: how to round integers (Figured it out!)

[Robert I. Eachus]

Jeffrey Carter wrote:
> Robert I. Eachus wrote:
> 
>>   function Rounding(Dividend, Divisor: Int) return Int is
>>   begin
>>     return (Dividend + Dividend + Divisor) / (Divisor + Divisor);
>>   exception
>>     when Constraint_Error =>
>>       declare
>>         Temp: Int;
>>       begin
>>         Temp := Dividend rem Divisor;
>>         if Temp > Int'Last/2 or else Temp * 2 >= Divisor
>>         then return Dividend/Divisor + 1;
>>         -- Divisor is always less than or equal to Int'Last
>>         else return Dividend/Divisor;
>>         end if;
>>       end;
>>   end Rounding;
>>
>>   function Round is new Rounding(Integer);
> 
> 
> What happens in the case of negative arguments?

Oops!  New version for the new requirement. ;-) And if you think it is 
messy, it is, that is the nature of division, as Intel and others have 
found out. (It is actually the corner cases that are tricky--and you 
really have to test all of them.)

Oh, the rounding is towards +inifinity, if you want anything else, you 
write it.  Or modify this, it shouldn't be too hard.

-----------------------------------------------------------------------

with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Rounding is

   generic
     type Int is range <>;
   function Rounding(Dividend, Divisor: Int) return Int;

   function Rounding(Dividend, Divisor: Int) return Int is
   begin
     if (Dividend >= 0 and Divisor > 0) or else
        (Dividend <= 0 and Divisor < 0)
     then return (Dividend + Dividend + Divisor) /
           (Divisor + Divisor);
     elsif Dividend <= 0 and Divisor > 0
     then return (Dividend + Dividend - Divisor + 1) /
          (Divisor + Divisor);
     else return (Dividend + Dividend - Divisor - 1) /
          (Divisor + Divisor);
     end if;
   exception
     when Constraint_Error =>
       if Divisor = 0 then raise Constraint_Error; end if;
       -- get the case we can't handle out of the way...
       declare
         Temp: Int;
       begin
         Temp := abs Dividend rem Divisor;
         if Divisor < 0 and Dividend > 0 then
           if Temp > -(Int'First/2)
               or else (Temp-1) * 2 >= -(Divisor + 1)
           then return Dividend/Divisor - 1;
           else return Dividend/Divisor;
           end if;
         elsif Divisor < 0 and Dividend < 0 then
           if Temp > -(Int'First/2)
               or else (Temp-1) * 2 >= -(Divisor + 2)
           then return Dividend/Divisor + 1;
           else return Dividend/Divisor;
           end if;
         elsif Divisor > 0 and Dividend > 0 then
           if Temp > Int'Last/2 or else Temp * 2 >= Divisor
           then return Dividend/Divisor + 1;
           else return Dividend/Divisor;
           end if;
        else -- Divisor > 0 and Dividend < 0 then
           if Temp > Int'Last/2 or else (Temp-1) * 2 >= Divisor - 1
           then return Dividend/Divisor - 1;
           else return Dividend/Divisor;
           end if;
         end if;
       end;
   end Rounding;

   function Round is new Rounding(Integer);

begin

   Put_Line(" Rounding (2,3) is " & Integer'Image(Round(2,3)));
   Put_Line(" Rounding (7,5) is " & Integer'Image(Round(7,5)));
   Put_Line(" Rounding (25, 10) is " & Integer'Image(Round(25,10)));
   Put_Line(" Rounding (1_000_000_000, 1_500_000_000) is " &
                   Integer'Image(Round(1_000_000_000, 1_500_000_000)));
   Put_Line(" Rounding (1_000_000_000, 2_000_000_000) is " &
                   Integer'Image(Round(1_000_000_000, 2_000_000_000)));
   Put_Line(" Rounding (1_500_000_000, 2_000_000_000) is " &
                   Integer'Image(Round(1_500_000_000, 2_000_000_000)));
   Put_Line(" Rounding (1_000_000_000, 2_000_000_001) is " &
                   Integer'Image(Round(1_00_000_000, 2_000_000_001)));
   Put_Line(" Rounding (1_500_000_000, Integer'Last) is " &
                   Integer'Image(Round(1_500_000_000, Integer'Last)));
   Put_Line(" Rounding (1_073_741_824, Integer'Last) is " &
                   Integer'Image(Round(1_073_741_824, Integer'Last)));
   Put_Line(" Rounding (1_073_741_823, Integer'Last) is " &
                   Integer'Image(Round(1_073_741_823, Integer'Last)));
   Put_Line(" Rounding (1_000_000_000, Integer'Last) is " &
                   Integer'Image(Round(1_000_000_000, Integer'Last)));

   Put_Line(" Rounding (-2,3) is " & Integer'Image(Round(-2,3)));
   Put_Line(" Rounding (-7,5) is " & Integer'Image(Round(-7,5)));
   Put_Line(" Rounding (-25, 10) is " & Integer'Image(Round(-25,10)));
   Put_Line(" Rounding (-1_000_000_000, 1_500_000_000) is " &
                   Integer'Image(Round(-1_000_000_000, 1_500_000_000)));
   Put_Line(" Rounding (-1_000_000_000, 2_000_000_000) is " &
                   Integer'Image(Round(-1_000_000_000, 2_000_000_000)));
   Put_Line(" Rounding (-1_500_000_000, 2_000_000_000) is " &
                   Integer'Image(Round(-1_500_000_000, 2_000_000_000)));
   Put_Line(" Rounding (-1_000_000_000, 2_000_000_001) is " &
                   Integer'Image(Round(-1_00_000_000, 2_000_000_001)));
   Put_Line(" Rounding (-1_500_000_000, Integer'Last) is " &
                   Integer'Image(Round(-1_500_000_000, Integer'Last)));
   Put_Line(" Rounding (-1_073_741_824, Integer'Last) is " &
                   Integer'Image(Round(-1_073_741_824, Integer'Last)));
   Put_Line(" Rounding (-1_073_741_823, Integer'Last) is " &
                   Integer'Image(Round(-1_073_741_823, Integer'Last)));
   Put_Line(" Rounding (-1_000_000_000, Integer'Last) is " &
                   Integer'Image(Round(-1_000_000_000, Integer'Last)));

   Put_Line(" Rounding (2,-3) is " & Integer'Image(Round(2,-3)));
   Put_Line(" Rounding (7,-5) is " & Integer'Image(Round(7,-5)));
   Put_Line(" Rounding (25, -10) is " & Integer'Image(Round(25,-10)));
   Put_Line(" Rounding (1_000_000_000, -1_500_000_000) is " &
                   Integer'Image(Round(1_000_000_000, -1_500_000_000)));
   Put_Line(" Rounding (1_000_000_000, -2_000_000_000) is " &
                   Integer'Image(Round(1_000_000_000, -2_000_000_000)));
   Put_Line(" Rounding (1_500_000_000, -2_000_000_000) is " &
                   Integer'Image(Round(1_500_000_000, -2_000_000_000)));
   Put_Line(" Rounding (1_000_000_000, -2_000_000_001) is " &
                   Integer'Image(Round(1_00_000_000, -2_000_000_001)));
   Put_Line(" Rounding (1_500_000_000, Integer'First) is " &
                   Integer'Image(Round(1_500_000_000, Integer'First)));
   Put_Line(" Rounding (1_073_741_824, Integer'First) is " &
                   Integer'Image(Round(1_073_741_824, Integer'First)));
   Put_Line(" Rounding (1_073_741_823, Integer'First) is " &
                   Integer'Image(Round(1_073_741_823, Integer'First)));
   Put_Line(" Rounding (1_000_000_000, Integer'First) is " &
                   Integer'Image(Round(1_000_000_000, Integer'First)));

   Put_Line(" Rounding (-2,-3) is " & Integer'Image(Round(-2,-3)));
   Put_Line(" Rounding (-7,-5) is " & Integer'Image(Round(-7,-5)));
   Put_Line(" Rounding (-25,-10) is " & Integer'Image(Round(-25,-10)));
   Put_Line(" Rounding (-1_000_000_000, -1_500_000_000) is " &
                   Integer'Image(Round(-1_000_000_000, -1_500_000_000)));
   Put_Line(" Rounding (-1_000_000_000, -2_000_000_000) is " &
                   Integer'Image(Round(-1_000_000_000, -2_000_000_000)));
   Put_Line(" Rounding (-1_500_000_000, -2_000_000_000) is " &
                   Integer'Image(Round(-1_500_000_000, -2_000_000_000)));
   Put_Line(" Rounding (-1_000_000_000, -2_000_000_001) is " &
                   Integer'Image(Round(-1_000_000_000, -2_000_000_001)));
   Put_Line(" Rounding (-1_500_000_000, Integer'First) is " &
                   Integer'Image(Round(-1_500_000_000, Integer'First)));
   Put_Line(" Rounding (-1_073_741_824, Integer'First) is " &
                   Integer'Image(Round(-1_073_741_824, Integer'First)));
   Put_Line(" Rounding (-1_073_741_823, Integer'First) is " &
                   Integer'Image(Round(-1_073_741_823, Integer'First)));
   Put_Line(" Rounding (-1_000_000_000, Integer'First) is " &
                   Integer'Image(Round(-1_000_000_000, Integer'First)));

end Test_Rounding;
-----------------------------------------------------------------------
The tests should probably be rewritten to only print results if there is 
a problem...
E:\Ada\Bug>test_rounding
test_rounding
  Rounding (2,3) is  1
  Rounding (7,5) is  1
  Rounding (25, 10) is  3
  Rounding (1_000_000_000, 1_500_000_000) is  1
  Rounding (1_000_000_000, 2_000_000_000) is  1
  Rounding (1_500_000_000, 2_000_000_000) is  1
  Rounding (1_000_000_000, 2_000_000_001) is  0
  Rounding (1_500_000_000, Integer'Last) is  1
  Rounding (1_073_741_824, Integer'Last) is  1
  Rounding (1_073_741_823, Integer'Last) is  0
  Rounding (1_000_000_000, Integer'Last) is  0
  Rounding (-2,3) is -1
  Rounding (-7,5) is -1
  Rounding (-25, 10) is -2
  Rounding (-1_000_000_000, 1_500_000_000) is -1
  Rounding (-1_000_000_000, 2_000_000_000) is  0
  Rounding (-1_500_000_000, 2_000_000_000) is -1
  Rounding (-1_000_000_000, 2_000_000_001) is  0
  Rounding (-1_500_000_000, Integer'Last) is -1
  Rounding (-1_073_741_824, Integer'Last) is -1
  Rounding (-1_073_741_823, Integer'Last) is  0
  Rounding (-1_000_000_000, Integer'Last) is  0
  Rounding (2,-3) is -1
  Rounding (7,-5) is -1
  Rounding (25, -10) is -2
  Rounding (1_000_000_000, -1_500_000_000) is -1
  Rounding (1_000_000_000, -2_000_000_000) is  0
  Rounding (1_500_000_000, -2_000_000_000) is -1
  Rounding (1_000_000_000, -2_000_000_001) is  0
  Rounding (1_500_000_000, Integer'First) is -1
  Rounding (1_073_741_824, Integer'First) is  0
  Rounding (1_073_741_823, Integer'First) is  0
  Rounding (1_000_000_000, Integer'First) is  0
  Rounding (-2,-3) is  1
  Rounding (-7,-5) is  1
  Rounding (-25,-10) is  3
  Rounding (-1_000_000_000, -1_500_000_000) is  1
  Rounding (-1_000_000_000, -2_000_000_000) is  1
  Rounding (-1_500_000_000, -2_000_000_000) is  1
  Rounding (-1_000_000_000, -2_000_000_001) is  0
  Rounding (-1_500_000_000, Integer'First) is  1
  Rounding (-1_073_741_824, Integer'First) is  1
  Rounding (-1_073_741_823, Integer'First) is  0
  Rounding (-1_000_000_000, Integer'First) is  0

Re: how to round integers (Figured it out!)

[Jeffrey Carter]

Robert I. Eachus wrote:
> Jeffrey Carter wrote:
> 
>> Robert I. Eachus wrote:
>>
>>>   function Round is new Rounding(Integer);
>>
>> What happens in the case of negative arguments?
> 
> Oops!  New version for the new requirement. ;-) And if you think it is 
> messy, it is, that is the nature of division, as Intel and others have 
> found out. (It is actually the corner cases that are tricky--and you 
> really have to test all of them.)

Not really a new requirment. Your generic specification clearly allows 
instantiation with subtypes that include negative values (such as your 
instantiation with Integer), so clearly the function is intended to 
handle negative arguments :)

Yes, it is messy. So I would have made it a generic package, with the 
following declarations:

subtype Natural_Int  is Int range 0 .. Int'Last;
subtype Positive_Int is Int range 1 .. Int'Last;

function Rounding (Dividend : Natural_Int; Divisor : Positive_Int)
return Int;

Then your original algorithm would be fine.

-- 
Jeff Carter
"You tiny-brained wipers of other people's bottoms!"
Monty Python & the Holy Grail

Re: how to round integers (Figured it out!)

[Robert I. Eachus]

Jeffrey Carter wrote:

> Then your original algorithm would be fine.

I would say my elaboration of David C. Hoos version.  But it was a point 
worth making, and since I have written this sort of stuff several times, 
might as well put up the "right" answer for the general case.

But what I really should do is write the one-liner package that converts 
to float to do the divide, then converts back to the integer type (done):

   generic
     type Int is range <>;
   function Rounding2(Dividend, Divisor: Int) return Int;

   function Rounding2(Dividend, Divisor: Int) return Int is
   begin
     return Int(Long_Float(Dividend)/Long_Float(Divisor));
   end Rounding2;

Note that this package will round away from zero.  But the interesting 
thing to do of course, is compare the two packages on timing (program at 
end):

E:\Ada\Bug>time_rounding
time_rounding
  Iteration  1 Round = 49.000 Round2 = 9.640
  Iteration  2 Round = 48.979 Round2 = 9.658
  Iteration  3 Round = 49.010 Round2 = 9.661
  Iteration  4 Round = 49.001 Round2 = 9.643
  Iteration  5 Round = 49.381 Round2 = 9.645

  Averages     Round = 49.074 Round2 = 9.650

First note that your milage may definitely vary, this was on a 700 MHz 
Athlon Classic.  Second, the program as written will sit and churn, in 
my case for over 5 minutes.  Third, no those results are not surprising. 
  By using the floating point divide, ON THIS PROCESSOR, the divides 
have one execution pipe to themselves, which is unused in the other 
version.  Other architectures have different designs.  For example some 
use the same pipe for integer and floating point divides.  And finally 
version 2 works out to 2.59 iterations per microsecond.  Not bad for all 
the work done there.  (I didn't play with other options, including 
unrolling loops and inlining the code.)

-----------------------------------------------------------------------
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Calendar; use Ada.Calendar;
with Ada.Numerics.Discrete_Random;
procedure Time_Rounding is

   subtype Int is Integer range -Integer'Last..Integer'Last;
   package Int_Rand is new Ada.Numerics.Discrete_Random(Int);
   -- I want random numbers that are closed over division.
   -- Integer'First/-1 overflows.

   Gen: Int_Rand.Generator;
   function Rand(G: in Int_Rand.Generator := Gen)
       return Integer renames Int_Rand.Random;

   type Int_Array is array(1..5_000) of Integer;
   A,B, Results : Int_Array;
   Temp: Integer;
   Maximum: Integer;
   Number_Of_Iterations: constant Integer := 5;
   Times: array(Integer range 1..2, 1..Number_Of_Iterations) of Duration;

   Start, Stop: Time;

   package Duration_IO is new Fixed_IO(Duration);

   procedure Put_Time(Seconds: Duration;
             Fore: Field := 1;
             Aft: Field := 3;
             Exp: Field := 0) renames Duration_IO.Put;

   generic
     type Int is range <>;
   function Rounding(Dividend, Divisor: Int) return Int;

   generic
     type Int is range <>;
   function Rounding2(Dividend, Divisor: Int) return Int;

   function Rounding(Dividend, Divisor: Int) return Int is
   begin
     if (Dividend >= 0 and Divisor > 0) or else
        (Dividend <= 0 and Divisor < 0)
     then return (Dividend + Dividend + Divisor) /
           (Divisor + Divisor);
     elsif Dividend <= 0 and Divisor > 0
     then return (Dividend + Dividend - Divisor + 1) /
          (Divisor + Divisor);
     else return (Dividend + Dividend - Divisor - 1) /
          (Divisor + Divisor);
     end if;
   exception
     when Constraint_Error =>
       if Divisor = 0 then raise Constraint_Error; end if;
       -- get the case we can't handle out of the way...
       declare
         Temp: Int;
       begin
         Temp := abs Dividend rem Divisor;
         if Divisor < 0 and Dividend > 0 then
           if Temp > -(Int'First/2)
               or else (Temp-1) * 2 >= -(Divisor + 1)
           then return Dividend/Divisor - 1;
           else return Dividend/Divisor;
           end if;
         elsif Divisor < 0 and Dividend < 0 then
           if Temp > -(Int'First/2)
               or else (Temp-1) * 2 >= -(Divisor + 2)
           then return Dividend/Divisor + 1;
           else return Dividend/Divisor;
           end if;
         elsif Divisor > 0 and Dividend > 0 then
           if Temp > Int'Last/2 or else Temp * 2 >= Divisor
           then return Dividend/Divisor + 1;
           else return Dividend/Divisor;
           end if;
        else -- Divisor > 0 and Dividend < 0 then
           if Temp > Int'Last/2 or else (Temp-1) * 2 >= Divisor - 1
           then return Dividend/Divisor - 1;
           else return Dividend/Divisor;
           end if;
         end if;
       end;
   end Rounding;

   function Round is new Rounding(Integer);

   function Rounding2(Dividend, Divisor: Int) return Int is
   begin
     return Int(Long_Float(Dividend)/Long_Float(Divisor));
   end Rounding2;

   function Round2 is new Rounding2(Integer);

begin

  -- Initialize Random Number Generator;

  Int_Rand.Reset(Gen, 1234); --  I want repeatable results.

  -- Initialize Arrays

   for I in Int_Array'Range loop
     A(I) := Rand;
     B(I) := Rand;
     while B(I) = 0 loop
       B(I) := Rand;
     end loop; -- Don't want divide by zero errors.

   end loop;

  -- Test rounding algorithms, and as a side effect load caches.

   for I in Int_Array'Range loop
     Maximum := Integer'First;
     for J in Int_Array'Range loop
       Temp := Round(A(I), B(J));
       if Round2(A(I), B(J)) /= Temp then
         Put_Line("For " & Integer'Image(A(I)) & Integer'Image(B(I)) & " 
the results are "
            & Integer'Image(Temp) & " and " & Integer'Image(Round2(A(I), 
B(J))) & '.');

       -- There could be some differences.  Assuming the values are 
independent and
       -- uniformly distributed the rounding will be different if:
       -- 1. A(I) and B(J) have opposite signs.
       -- 2. A(I) is even.
       -- 3. B(J) mod A(I) = A(I)/2;
       -- The first two constraints eliminate 3/4 of the cases.  For the 
others, there
       -- will be Integer'Last/A(I) + Integer'Last mod A(I) > A(I)/2 
(math, not Ada!)
       -- Easy enough to write a program to get the probability per 
pair: 1.16415E-10.
       -- Of course, if I wanted to check the computations, I could 
choose A & B in a
       -- way that increases the odds.  For example, make B small and 
always even.

       end if;
       if Temp > Maximum then Maximum := Temp; end if;
     end loop;
     Results(I) := Maximum;
   end loop;

   -- Now do it for timings.

   for Iteration in 1..Number_Of_Iterations loop
     Start := Clock;
       for I in Int_Array'Range loop
       Maximum := Integer'First;
       for J in Int_Array'Range loop
         Temp := Round(A(I), B(J));
         if Temp > Maximum then Maximum := Temp; end if;
       end loop;
       Results(I) := Maximum;
     end loop;
     Stop := Clock;
     Times(1, Iteration) := Stop-Start;

     Start := Clock;
       for I in Int_Array'Range loop
       Maximum := Integer'First;
       for J in Int_Array'Range loop
         Temp := Round2(A(I), B(J));
         if Temp > Maximum then Maximum := Temp; end if;
       end loop;
       Results(I) := Maximum;
     end loop;
     Stop := Clock;
     Times(2, Iteration) := Stop-Start;

   end loop;

   declare
     Sum1, Sum2: Duration := 0.0;
   begin
     for I in 1..Number_Of_Iterations loop
       Sum1 := Sum1 + Times(1,I);
       Sum2 := Sum2 + Times(2,I);
       Put(" Iteration " & Integer'Image(I) & " Round = "); 
Put_Time(Times(1,I));
       Put(" Round2 = "); Put_Time(Times(2,I)); New_Line;
     end loop;
     New_Line;

     Put(" Averages    " & " Round = "); 
Put_Time(Sum1/Number_Of_Iterations);
     Put(" Round2 = "); Put_Time(Sum2/Number_Of_Iterations); New_Line;
   end;

end Time_Rounding;

Re: how to round integers (Figured it out!)

[Jeffrey Carter]

Thanks for the timings. I suspected that converting to floating-point 
would be faster.

Robert I. Eachus wrote:
> 
>   generic
>     type Int is range <>;
>   function Rounding2(Dividend, Divisor: Int) return Int;
> 
>   function Rounding2(Dividend, Divisor: Int) return Int is
>   begin
>     return Int(Long_Float(Dividend)/Long_Float(Divisor));
>   end Rounding2;

Except that Long_Float is (technically) not portable; implementations 
are not required to define Long_Float. So I guess the fully portable way 
to implement this would be

with System;
function Rounding2 (Dividend, Divisor: Int) return Int is
    type Big is digits System.Max_Digits;
begin -- Rounding2
    return Int (Big (Dividend) / Big (Divisor) );
end Rounding2;

-- 
Jeff Carter
"You cheesy lot of second-hand electric donkey-bottom biters."
Monty Python & the Holy Grail