* how to round integers
@ 2003-06-16 2:55 Cephus�
2003-06-16 4:03 ` Charles LaCour
` (3 more replies)
0 siblings, 4 replies; 16+ messages in thread
From: Cephus� @ 2003-06-16 2:55 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers
2003-06-16 2:55 how to round integers Cephus�
@ 2003-06-16 4:03 ` Charles LaCour
2003-06-16 12:12 ` Cephus�
2003-06-16 21:59 ` Jeffrey Creem
2003-06-16 10:09 ` Martin Dowie
` (2 subsequent siblings)
3 siblings, 2 replies; 16+ messages in thread
From: Charles LaCour @ 2003-06-16 4:03 UTC (permalink / raw)
[-- 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
>
>
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers
2003-06-16 2:55 how to round integers Cephus�
2003-06-16 4:03 ` Charles LaCour
@ 2003-06-16 10:09 ` Martin Dowie
2003-06-16 10:49 ` David C. Hoos
2003-06-16 12:18 ` how to round integers (Figured it out!) Cephus�
3 siblings, 0 replies; 16+ messages in thread
From: Martin Dowie @ 2003-06-16 10:09 UTC (permalink / raw)
"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;
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers
2003-06-16 2:55 how to round integers Cephus�
2003-06-16 4:03 ` Charles LaCour
2003-06-16 10:09 ` Martin Dowie
@ 2003-06-16 10:49 ` David C. Hoos
2003-06-16 12:18 ` how to round integers (Figured it out!) Cephus�
3 siblings, 0 replies; 16+ messages in thread
From: David C. Hoos @ 2003-06-16 10:49 UTC (permalink / raw)
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
>
>
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers
2003-06-16 4:03 ` Charles LaCour
@ 2003-06-16 12:12 ` Cephus�
2003-06-16 21:59 ` Jeffrey Creem
1 sibling, 0 replies; 16+ messages in thread
From: Cephus� @ 2003-06-16 12:12 UTC (permalink / raw)
[-- 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...
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers (Figured it out!)
2003-06-16 2:55 how to round integers Cephus�
` (2 preceding siblings ...)
2003-06-16 10:49 ` David C. Hoos
@ 2003-06-16 12:18 ` Cephus�
2003-06-16 12:34 ` David C. Hoos
3 siblings, 1 reply; 16+ messages in thread
From: Cephus� @ 2003-06-16 12:18 UTC (permalink / raw)
[-- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers (Figured it out!)
2003-06-16 12:18 ` how to round integers (Figured it out!) Cephus�
@ 2003-06-16 12:34 ` David C. Hoos
2003-06-16 12:36 ` Cephus�
0 siblings, 1 reply; 16+ messages in thread
From: David C. Hoos @ 2003-06-16 12:34 UTC (permalink / raw)
[-- 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
>
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers (Figured it out!)
2003-06-16 12:34 ` David C. Hoos
@ 2003-06-16 12:36 ` Cephus�
2003-06-16 13:12 ` David C. Hoos
0 siblings, 1 reply; 16+ messages in thread
From: Cephus� @ 2003-06-16 12:36 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers (Figured it out!)
2003-06-16 12:36 ` Cephus�
@ 2003-06-16 13:12 ` David C. Hoos
2003-06-17 4:44 ` Robert I. Eachus
0 siblings, 1 reply; 16+ messages in thread
From: David C. Hoos @ 2003-06-16 13:12 UTC (permalink / raw)
[-- 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
>
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers
2003-06-16 4:03 ` Charles LaCour
2003-06-16 12:12 ` Cephus�
@ 2003-06-16 21:59 ` Jeffrey Creem
1 sibling, 0 replies; 16+ messages in thread
From: Jeffrey Creem @ 2003-06-16 21:59 UTC (permalink / raw)
"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.
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers (Figured it out!)
2003-06-16 13:12 ` David C. Hoos
@ 2003-06-17 4:44 ` Robert I. Eachus
2003-06-17 19:20 ` Jeffrey Carter
0 siblings, 1 reply; 16+ messages in thread
From: Robert I. Eachus @ 2003-06-17 4:44 UTC (permalink / raw)
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;
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers (Figured it out!)
2003-06-17 4:44 ` Robert I. Eachus
@ 2003-06-17 19:20 ` Jeffrey Carter
2003-06-18 9:32 ` Robert I. Eachus
0 siblings, 1 reply; 16+ messages in thread
From: Jeffrey Carter @ 2003-06-17 19:20 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers (Figured it out!)
2003-06-17 19:20 ` Jeffrey Carter
@ 2003-06-18 9:32 ` Robert I. Eachus
2003-06-18 18:07 ` Jeffrey Carter
0 siblings, 1 reply; 16+ messages in thread
From: Robert I. Eachus @ 2003-06-18 9:32 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers (Figured it out!)
2003-06-18 9:32 ` Robert I. Eachus
@ 2003-06-18 18:07 ` Jeffrey Carter
2003-06-19 0:34 ` Robert I. Eachus
0 siblings, 1 reply; 16+ messages in thread
From: Jeffrey Carter @ 2003-06-18 18:07 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers (Figured it out!)
2003-06-18 18:07 ` Jeffrey Carter
@ 2003-06-19 0:34 ` Robert I. Eachus
2003-06-19 23:40 ` Jeffrey Carter
0 siblings, 1 reply; 16+ messages in thread
From: Robert I. Eachus @ 2003-06-19 0:34 UTC (permalink / raw)
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;
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: how to round integers (Figured it out!)
2003-06-19 0:34 ` Robert I. Eachus
@ 2003-06-19 23:40 ` Jeffrey Carter
0 siblings, 0 replies; 16+ messages in thread
From: Jeffrey Carter @ 2003-06-19 23:40 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 16+ messages in thread
end of thread, other threads:[~2003-06-19 23:40 UTC | newest]
Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-06-16 2:55 how to round integers Cephus�
2003-06-16 4:03 ` Charles LaCour
2003-06-16 12:12 ` Cephus�
2003-06-16 21:59 ` Jeffrey Creem
2003-06-16 10:09 ` Martin Dowie
2003-06-16 10:49 ` David C. Hoos
2003-06-16 12:18 ` how to round integers (Figured it out!) Cephus�
2003-06-16 12:34 ` David C. Hoos
2003-06-16 12:36 ` Cephus�
2003-06-16 13:12 ` David C. Hoos
2003-06-17 4:44 ` Robert I. Eachus
2003-06-17 19:20 ` Jeffrey Carter
2003-06-18 9:32 ` Robert I. Eachus
2003-06-18 18:07 ` Jeffrey Carter
2003-06-19 0:34 ` Robert I. Eachus
2003-06-19 23:40 ` Jeffrey Carter
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox