Why is (round 2.5) = 2?
Jim Meehan
returns either integer or integer+1, whichever is even. Does anyone
remember why it was defined that way?
For comparison, Scheme does it the same way. fixr in ZetaLisp always
rounds up. The Lisp 1.6 manual shows a sample definition that also rounds
up. Pascal and PostScript round up.
I didn't see a 'round' operator in my books on Algol, Ada, APL, Basic, C,
Fortran, LispVM, MacLisp, ML, or Snobol.
There is one in Smalltalk-80, but from the manual, I couldn't tell what
happens in this case.
In Modula-3, the result depends on a thread-specific variable.
Erik Naggum
| In Common Lisp, round, when applied to a number of the form
| integer+0.5, returns either integer or integer+1, whichever is even.
| Does anyone remember why it was defined that way?
I don't "remember", but when I asked the same question not long ago, I was
told that it was mathematically correct, which indeed it is.
(loop for x from 0 to 99 sum (+ 1/2 x))
=> 5000
(loop for x from 0 to 99 sum (round (+ 1/2 x)))
=> 5000
if round "rounded up", you would get
(loop for x from 0 to 99 sum (ceiling (+ 1/2 x)))
=> 5050
that is, for a random distribution of numbers, adding values after rounding
will yield Pentium-size errors if (round x) == (floor (+ 1/2 x)).
#<Erik>
--
sufficiently advanced political correctness is indistinguishable from irony
Barry Margolin
>In Common Lisp, round, when applied to a number of the form integer+0.5,
>returns either integer or integer+1, whichever is even. Does anyone
>remember why it was defined that way?
Because that's the way that numerical analysts prefer. It doesn't bias
rounding in any particular direction -- it rounds up just as much as it
rounds down.
Rounding to even is the convention that I learned in elementary school --
it's not just a computer thing.
--
Barry Margolin
BBN Planet Corporation, Cambridge, MA
bar...@bbnplanet.com
Sean Luke
>Rounding to even is the convention that I learned in elementary school --
>it's not just a computer thing.
Strange. I learned rounding .5 up, as did everyone I've talked to so far.
Where _did_ you go to school? :-) :-)
Sean Luke U Maryland at College Park
se...@cs.umd.edu Today's Chemical: Aluminum Zirconium Tetrachlorohydrex GLY
Dan Britt
|> In Common Lisp, round, when applied to a number of the form integer+0.5,
|> returns either integer or integer+1, whichever is even. Does anyone
|> remember why it was defined that way?
|>
|> rounds up. The Lisp 1.6 manual shows a sample definition that also rounds
|> up. Pascal and PostScript round up.
|>
|> I didn't see a 'round' operator in my books on Algol, Ada, APL, Basic, C,
|> Fortran, LispVM, MacLisp, ML, or Snobol.
|>
|> There is one in Smalltalk-80, but from the manual, I couldn't tell what
|> happens in this case.
|>
|> In Modula-3, the result depends on a thread-specific variable.
I've seen this thread before and don't remember the answer (maybe it's
ease of implementation). It seems to me that mathematically (using
infinite precision arithmetic) rounding toward an even number is wrong.
The "size" of the real number space including 0.0 through 0.49999... is
equal to that including 0.50 through 0.99999.... Thus, one should always
round anything at or above .5 up. But that's with infinite precision.
Digital representations may change things...
Dan
______________________________________________________________________
Daniel L. Britt Martin Marietta Astronautics
br...@tigercat.den.mmc.com Opinions expressed are my own,
303-977-1682 not those of my employer.
Ron Forsythe
(Dan Britt) wrote:
> I've seen this thread before and don't remember the answer (maybe it's
> ease of implementation). It seems to me that mathematically (using
> infinite precision arithmetic) rounding toward an even number is wrong.
> The "size" of the real number space including 0.0 through 0.49999... is
> equal to that including 0.50 through 0.99999.... Thus, one should always
> round anything at or above .5 up. But that's with infinite precision.
> Digital representations may change things...
Except the range is not 0.0 -> .49999...
It's 0.00...01 -> .49999...
Consider breaking the range up like this:
0 | 1 2 3 4 | 5 | 6 7 8 9 | 10
even| round down | ? | round up | odd
Always rounding up results in 5 cases that lead to rounding up and 4 to rounding
down. Rounding to even numbers gives equal probability that .5 will be rounded
up as rounded down (at least over the range from -infinity to infinity).
I think that we round to even rather than to odd numbers has to do with the
fact that 0 is even.
In article <3mtu0f$s...@mimsy.cs.umd.edu>, se...@jujube.cs.umd.edu (Sean
Luke) wrote:
> Strange. I learned rounding .5 up, as did everyone I've talked to so far.
> Where _did_ you go to school? :-) :-)
>
> Sean Luke U Maryland at College Park
Don't trust everything that you learn in school. ;)
Ron Forsythe U Maryland at College Park
ro...@src.umd.edu
John Somerville
to do with Lisp per se. If you round in this fashion, you will avoid bias
in a collection or list of numbers.
Erik Naggum
| Rounding to even is the convention that I learned in elementary school
| -- it's not just a computer thing.
[Sean Luke]
| Strange. I learned rounding .5 up, as did everyone I've talked to so
| far. Where _did_ you go to school? :-) :-)
maybe it's more prudent to ask _when_? (or maybe not. :) (my parents, both
engineers, had never heard of anything but rounding .5 up, either.)
last time we discussed this, one guy from South America chimed in and said
that he also learned round-to-even in elementary school. an ex who grew up
in Argentina had never heard of it. dunno. may we conclude that Lisp has
something to tell people all the way from elementary school up, these days?
Dan Britt
|> In article <1995Apr17....@den.mmc.com>, br...@tigercat.den.mmc.com
|> (Dan Britt) wrote:
|>
|> > I've seen this thread before and don't remember the answer (maybe it's
|> > ease of implementation). It seems to me that mathematically (using
|> > infinite precision arithmetic) rounding toward an even number is wrong.
|> > The "size" of the real number space including 0.0 through 0.49999... is
|> > equal to that including 0.50 through 0.99999.... Thus, one should always
|> > round anything at or above .5 up. But that's with infinite precision.
|> > Digital representations may change things...
|>
|> Except the range is not 0.0 -> .49999...
|> It's 0.00...01 -> .49999...
|>
|> Consider breaking the range up like this:
|> 0 | 1 2 3 4 | 5 | 6 7 8 9 | 10
|> even| round down | ? | round up | odd
|>
|> Always rounding up results in 5 cases that lead to rounding up and 4 to rounding
|> down. Rounding to even numbers gives equal probability that .5 will be rounded
|> up as rounded down (at least over the range from -infinity to infinity).
Except that in the range 0 | 1 ... 9 | 10, zero equals ten (with respect
to rounding). And, the real number line _does_ include integers, so the
range is 0 (exactly, not 0.00...01) through 0.49999.... There are exactly
as many real numbers between 0 and 0.49999... inclusive as there are between
0.5 and 0.99999... inclusive, so the habit of rounding .5 down half of the
time means rounding down more often than rounding up. Finite precision
arithmetic may either mitigate or exacerbate that; I don't know. But this
subject has to do with open vs closed intervals on the real number line. The
interval [0, .5) is the same size as the interval [.5, 1) (though it's been
so long I might have the symbols reversed), and that [.5 means include .5,
whereas .5) means don't include it. That's why so many of us were
taught to round .5 up:
|> > Strange. I learned rounding .5 up, as did everyone I've talked to so far.
Dan
Mark C. Chu-Carroll
>>>>> "Sean" == Sean Luke <se...@jujube.cs.umd.edu> writes:
In article <3mtu0f$s...@mimsy.cs.umd.edu> se...@jujube.cs.umd.edu (Sean Luke) writes:
Sean> Barry Margolin (bar...@nic.near.net) wrote:
>> Rounding to even is the convention that I learned in elementary
>> school -- it's not just a computer thing.
Sean> Strange. I learned rounding .5 up, as did everyone I've talked
Sean> to so far. Where _did_ you go to school? :-) :-)
How about New Jersey?
Always rounding up actually produces arithmetic error. When you're
rounding, you should always round towards the integer that's closest
to the actual value. But n.5 is *not* closer to n+1 than it is to n -
it's exactly half way in between. If you always round upwards, then
you're biasing your numbers towards the high end.
Always rounding towards even is a simple trick that eliminates the
error - half the time you round up, half the time you round down, so
on average the error will be cancelled out.
<MC>
--
|| Mark Craig Chu-Carroll: <MC> || "A libertarian is just a republican
|| CIS Grad, U of Delaware || who takes drugs"
|| PGP Key Available, by finger || - Bob Black
|| car...@cis.udel.edu ||
Erik Naggum
| Except that in the range 0 | 1 ... 9 | 10, zero equals ten (with
| respect to rounding). And, the real number line _does_ include
| integers, so the range is 0 (exactly, not 0.00...01) through
| 0.49999.... There are exactly as many real numbers between 0 and
| 0.49999... inclusive as there are between 0.5 and 0.99999... inclusive,
| so the habit of rounding .5 down half of the time means rounding down
| more often than rounding up. Finite precision arithmetic may either
| mitigate or exacerbate that; I don't know. But this subject has to do
| with open vs closed intervals on the real number line. The interval [0,
| .5) is the same size as the interval [.5, 1) (though it's been so long
| I might have the symbols reversed), and that [.5 means include .5,
| whereas .5) means don't include it.
I don't know whether this is a useful way to see it, but it does show that
round-up is a better solution under the stated premises. the question is
whether those premises are optimal. I don't think so.
instead of looking at the size of the ranges [0,.5) and [.5,1), we should
look at the range of numbers that round to a given integer. e.g., the
numbers that round to zero are in the range [-.5,+.5). this range is
slightly off balance, and it is this imbalance that accumulates errors. in
a round-to-even scheme, the numbers that round to an even integer n are in
the range [n-.5,n+.5], which balances perfectly. the numbers that round to
an odd integer n is in the range (n-.5,n+.5), which also balances. this
balance yields correct results.
Risto Bell /CAD
In article <1995Apr17....@den.mmc.com> br...@tigercat.den.mmc.com (Dan Britt) writes:
D> In article <jmeehan-1504...@machine.mv.us.adobe.com>, jme...@mv.us.adobe.com (Jim Meehan) writes:
D> |> In Common Lisp, round, when applied to a number of the form integer+0.5,
D> |> returns either integer or integer+1, whichever is even. Does anyone
D> |> remember why it was defined that way?
D> |>
D> |> For comparison, Scheme does it the same way. fixr in ZetaLisp always
D> |> rounds up. The Lisp 1.6 manual shows a sample definition that also rounds
D> |> up. Pascal and PostScript round up.
D> |>
D> |> I didn't see a 'round' operator in my books on Algol, Ada, APL, Basic, C,
D> |> Fortran, LispVM, MacLisp, ML, or Snobol.
D> |>
D> |> There is one in Smalltalk-80, but from the manual, I couldn't tell what
D> |> happens in this case.
D> |>
D> |> In Modula-3, the result depends on a thread-specific variable.
D> I've seen this thread before and don't remember the answer (maybe it's
D> ease of implementation). It seems to me that mathematically (using
D> infinite precision arithmetic) rounding toward an even number is wrong.
D> The "size" of the real number space including 0.0 through 0.49999... is
D> equal to that including 0.50 through 0.99999.... Thus, one should always
D> round anything at or above .5 up. But that's with infinite precision.
D> Digital representations may change things...
D> Dan
D> ______________________________________________________________________
D> Daniel L. Britt Martin Marietta Astronautics
D> br...@tigercat.den.mmc.com Opinions expressed are my own,
D> 303-977-1682 not those of my employer.
My two cents and apologies if it's redundant, I missed part of the thread.
Your range definitions seem incorrect to me. [0.0-0.499...] (square brackets
for inclusive or closed ranges) includes the target of rounding down: 0.0. If
you want to make this comparison shouldn't the other range be [0.5-1.0]? Now
it seems clear that 0.5 is by definition precisely in the center and by
arbitrarily including it only in the upper range, that range has a larger
"size."
Technically I think one can prove that .499... == .5 and .99... == 1.0, so may
be the ranges should be described as (0.0-0.5] and [0.5-1.0) (parenthesis for
exclusive or open ranges), again leaving it arbitrary how you treat 0.5.
I was never taught the round-to-even practice, but it sounds like a simple
pseudo-random way of being "fair" and not playing favorites, so that after
many computations perhaps there is less accumulation of error or bias.
--
-Risto r...@cypress.com Consortia are formed by losers. --T.J. Rodgers
Don Geddis
> | There are exactly as many real numbers between 0 and 0.49999... inclusive
> | as there are between 0.5 and 0.99999... inclusive
Since this has been posted a couple of times in this thread, and it appears
to have been accepted without question, I just want to point out that it's
actually wrong. Or, more specifically, it is correct, but in a particularly
meaningless sense that doesn't contribute to the rounding discussion.
Infinities have orders, and you need tricks like diagonalization to compare
them. So, for example, there are more real numbers than there are rational
ones (quotient of two integers), even though there are infinite numbers of
both. Reals are more "dense".
But there are the SAME number of positive integers as there are just integers,
even though the second set includes the first.
Consequence? Well, yes there are as many real numbers between [0,.499...] as
[.5,.999...]. But there are also as many reals between 0 and 10, or just
reals altogether, as are in either of those two sets. So such an equivalence
doesn't help you at all in deciding whether to include .5 in one set or not,
because the size of the set doesn't change whether you put .5 in or take it
out.
(Also: .499... is EXACTLY the same as .5, so in fact your sets overlap.)
In any case, as others have pointed out, you round .5 to even in order to
minimize accumulated error over large numbers of numeric computations.
-- Don
--
Don Geddis Ged...@CS.Stanford.EDU http://www.stanford.edu/~geddis/
"Where are we going?" "Nowhere." "So what's the rush?" -- The Lost Boys
William D Clinger
quantum nature of computer arithmetic. ("Quantum" as in mathematics,
not physics.)
To be specific, let's discuss IEEE double precision arithmetic. To
be brief, let's call an IEEE double precision number a flonum.
Because most real numbers cannot be represented exactly by a flonum,
each flonum represents a range of real numbers. The flonum 1.5, for
example, is the best flonum approximation to every real number in the
closed interval
[1.49999999999999988897769753748434595763683319091796875,
1.50000000000000011102230246251565404236316680908203125]
Half of these real numbers are closer to 1.0 than to 2.0, and the
other half are closer to 2.0 than to 1.0. Regardless of whether
we round 1.5 to 1.0 or to 2.0, half of the real numbers represented
by 1.5 are being rounded to the wrong integer. We can't help that.
But we can make up for it in a statistical sense by rounding up half
the time and by rounding down half the time, when we round a flonum
whose decimal representation ends in .5. For example, we could have
the round procedure keep track of what it did the last time it rounded
a flonum ending in .5, so it could do the opposite next time. But it
is more efficient to round to even, and the statistical effect is
almost the same. (The statistical properties of alternate rounding
might be a little better for some applications, but rounding to even
might be a little better for others.)
So that's why we round flonums to even.
By the way, the number of flonums in the range [n, n+1) is finite
for all integers n. Furthermore the number of flonums in that range
depends upon n. For example, there are more than 2^61 flonums in
[0, 1), but only 2^52 flonums in [1, 2), and only 2^51 flonums in
[2, 3).
This has little to do with the round-to-even rule, but I thought
some of you might be interested regardless.
William Clinger
Bill Wallace
numbers. Over the reals, the probability p(x==n.5)=0 (that is
the probability that a random variable x is equal to an integer +0.5
is zero.) Thus, since those values occur so seldomly (never exactly
in fact), you could simply round to 0 and be done with it. Rounding
to n is as good as rounding to 0 or rounding to n+1. Convention has
it that rounding goes to n.
Over the integers, the problem doesn't occur.
Fractions are like reals in this respect.
Thus, we only have fixed-point or floating point as an approximation
of real numbers. Here, we might really get n.5 and want to round
to minimize the error. For that situation, we want to examine the
probabilities of getting x=n.5 based on the real value of x. Then,
one wants to assign n.5 to n or n+1 based on the probabilities. Under
the assumption that there is an equal length on both sides of n.5,
in the reals, that get assigned to n.5 in our representation, then
assigning with equal probability to n and n+1 is the right thing
to do to minimize errors overall. An approximation to this is to
round to even numbers. It will still cause more errors than a true
random, but it is better than always assigning in one direction.
Bill
PS 0.9999... = 1.0 Proof:
let x=0.9999...
then 10x=9.9999999
Take 10x-x = 9x = 9.999999.... - 0.999999....
= 9.0000...
divide both sides by 9
x = 1.0 QED
Larry Hunter
Dan Britt says:
There are exactly as many real numbers between 0 and 0.49999... inclusive
as there are between 0.5 and 0.99999... inclusive, so the habit of
rounding .5 down half of the time means rounding down more often than
rounding up.
We interrupt this discussion of rounding for a little mathematical truth.
The first clause of Britt's statement is true, but it in no way supports his
conclusion. It is also true that there are exactly as many real numbers
between 0.000001 and 0.0000011 as there are between 0 and 100. There is
precisely an uncountably infinite number of real numbers between *any* pair
of real numbers. In fact, that's what makes them uncountably infinite.
That is, that fact is a key part of the usual proof that you cannot put
reals in one to one correspondence with integers.
Of course, this has nothing to do with rounding in LISP because digital
computers have a hard time with irrational numbers. That's why picky people
choose to call the real-ish looking (technical term!) numbers computers use
"floating point."
We now return you to your regularly scheduled pointless battle. :-)
Larry
--
Lawrence Hunter, PhD.
National Library of Medicine
Bldg. 38A, 9th floor
Bethesda. MD 20894 USA
tel: +1 (301) 496-9300
fax: +1 (301) 496-0673
internet: hun...@nlm.nih.gov
encryption: RIPEM via server; PGP via "finger hun...@work.nlm.nih.gov"