* 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 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 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 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 (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 (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