Maths error

[Dennis Lee Bieber]

*grin* - I was around at that time, and some of the inappropriate habits
almost forced by the lack of processing power still linger in my mind,
like - "Don't use division if you can possibly avoid it, - its EXPENSIVE!"
- it seems so silly nowadays.

I seem to have missed that period... The campus mainframe had
hardware floating point (and hardware 32 digit packed BCD too -- I
recall the term where us FORTRAN flunkies were whizzing along whilst the
COBOL cabal basically froze for a month... the BCD logic board had
failed and finding parts for a Xerox Sigma 6 in late 70s took some
time).

As an old slide rule user - I can agree with this - if you know the order
of the answer, and maybe two points after the decimal, it will tell you
if the bridge will fall down or not. Having an additional fifty decimal

Or knowledge of a decent chemistry/physics class... wherein it is
emphasized that if the inputs only had x-digits, any results after
manipulation should have, at most, the same x-digits (after all, a
quantity on a scale that comes to x.xx units really means a range from
(x.xx - 0.005) to (x.xx + 0.005).


{My 8th grade teacher was a bit worried at seeing me with a slipstick
<G>; and my HighSchool Trig/Geometry teacher only required 3 significant
digits for answers -- even though half the class had calculators by
then}
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[Nick Maclaren]

|>
|> *grin* - I was around at that time, and some of the inappropriate habits
|> almost forced by the lack of processing power still linger in my mind,
|> like - "Don't use division if you can possibly avoid it, - its EXPENSIVE!"
|> - it seems so silly nowadays.

Yes, indeed, but that one is actually still with us! Integer division
is done by software on a few systems, and floating-point division is
often not vectorisable or pipelines poorly. But, except for special
cases of little relevance to Python, it is not the poison that it was
back then.

|> As an old slide rule user - I can agree with this - if you know the order
|> of the answer, and maybe two points after the decimal, it will tell you
|> if the bridge will fall down or not. Having an additional fifty decimal
|> places of accuracy does not really add any real information in these
|> cases. Its nice of course if its free, like it has almost become - but
|> I think people get mesmerized by the numbers, without giving any
|> thought to what they mean - which is probably why we often see
|> threads complaining about the "error" in the fifteenth decimal place..

Agreed. But the issue is really error build-up, and algorithms that are
numerically 'unstable' - THEN, such subtle differences do matter. You
still aren't interested in more than a few digits in the result, but you
may have to sweat blood to get them.

|> > [*] Assuming signed magnitude, calculate the answer truncated towards
|> > zero but keep track of whether it is exact. If not, force the last
|> > bit to 1. An old, cheap approximation to rounding.
|> >
|> This is not so cheap - its good solid reasoning in my book -
|> after all, "something" is a lot more than "nothing" and should
|> not be thrown away...

The "cheap" means "cheap in hardware" - it needs very little logic,
which is why it was used on the old, discrete-logic, machines.

I have been told by hardware people that implementing IEEE 754 rounding
and denormalised numbers needs a horrific amount of logic - which is
why only IBM do it all in hardware. And the decimal formats are
significantly more complicated.

What I don't know is how much precision this approximation loses when
used in real applications, and I have never found anyone else who has
much of a clue, either.


Regards,
Nick Maclaren.

 

[Tim Peters]

[Nick Maclaren]
[Hendrik van Rooyen]

I would have thought that this sort of thing was a natural consequence
of rounding errors - if I round (or worse truncate) a binary, I can be
off by at most one, with an expectation of a half of a least
significant digit, while if I use hex digits, my expectation is around
eight, and for decimal around five...

Which, in all cases, is a half ULP at worst (when rounding -- as
everyone does now).

So it would seem natural that errors would propagate
faster on big base systems, AOTBE, but this may be
a naive view..

I don't know of any current support for this view. It the bad old days,
such things were often confused by architectures that mixed non-binary
bases with "creative" rounding rules (like truncation indeed), and it
could be hard to know where to "pin the blame".

What you will still see stated is variations on Kahan's telegraphic
"binary is better than any other radix for error analysis (but not very
much)", listed as one of two techincal advantages for binary fp in:

http://www.cs.berkeley.edu/~wkahan/MktgMath.pdf

It's important to note that he says "error analysis", not "error
propagation" -- regardless of base in use, rounding is good to <= 1/2
ULP. A fuller elementary explanation of this can be found in David
Goldberg's widely available "What Every Computer Scientist Should Know
About Floating-Point", in its "Relative Error and Ulps" section. The
short course is that rigorous forward error analysis of fp algorithms is
usually framed in terms of relative error: given a computed
approximation x' to the mathematically exact result x, what's the
largest possible absolute value of the mathematical

r = (x'-x)/x

(the relative error of x')? This framework gets used because it's more-
or-less tractable, starting by assuming inputs are exact (or not, in
which case you start by bounding the inputs' relative errors), then
successively computing relative errors for each step of the algorithm.
Goldberg's paper, and Knuth volume 2, contain many introductory examples
of rigorous analysis using this approach.

Analysis of relative error generally goes along independent of FP base.
It's at the end, when you want to transform a statement about relative
error into a statement about error as measured by ULPs (units in the
last place), where the base comes in strongly. As Goldberg explains,
the larger the fp base the sloppier the relative-error-converted-to-ULPs
bound is -- but this is by a constant factor independent of the
algorithm being analyzed, hence Kahan's "... better ... but not very
much". In more words from Goldberg:

Since epsilon [a measure of relative error] can overestimate the
effect of rounding to the nearest floating-point number by the
wobble factor of B [the FP base, like 2 for binary or 10 for
decimal], error estimates of formulas will be tighter on machines
with a small B.

When only the order of magnitude of rounding error is of interest,
ulps and epsilon may be used interchangeably, since they differ by
at most a factor of B.

So that factor of B is irrelevant to most apps most of the time. For a
combination of an fp algorithm + set of inputs near the edge of giving
gibberish results, of course it can be important. Someone using
Python's decimal implementation has an often very effective workaround
then, short of writing a more robust fp algorithm: just boost the
precision.

 

[Hendrik van Rooyen]

{My 8th grade teacher was a bit worried at seeing me with a slipstick
<G>; and my HighSchool Trig/Geometry teacher only required 3 significant
digits for answers -- even though half the class had calculators by
then}

LOL - I haven't seen the word "slipstick" for yonks...

I recall an SF character known as "Slipstick Libby",
who was supposed to be a Genius - but I forget
the setting and the author.

It is something that has become quietly extinct, and
we did not even notice.

We should start a movement for reviving them -
on grounds of their "greenness" - they use no
batteries...

Fat chance.

- Hendrik

 

[Hendrik van Rooyen]

The "cheap" means "cheap in hardware" - it needs very little logic,
which is why it was used on the old, discrete-logic, machines.

I have been told by hardware people that implementing IEEE 754 rounding
and denormalised numbers needs a horrific amount of logic - which is
why only IBM do it all in hardware. And the decimal formats are
significantly more complicated.

What I don't know is how much precision this approximation loses when
used in real applications, and I have never found anyone else who has
much of a clue, either.

I would suspect that this is one of those questions which are simple
to ask, but horribly difficult to answer - I mean - if the hardware has
thrown it away, how do you study it - you need somehow two
different parallel engines doing the same stuff, and comparing the
results, or you have to write a big simulation, and then you bring
your simulation errors into the picture - There be Dragons...

- Hendrik

 

[Hendrik van Rooyen]

[Nick Maclaren]
[Hendrik van Rooyen]

I would have thought that this sort of thing was a natural consequence
of rounding errors - if I round (or worse truncate) a binary, I can be
off by at most one, with an expectation of a half of a least
significant digit, while if I use hex digits, my expectation is around
eight, and for decimal around five...

Which, in all cases, is a half ULP at worst (when rounding -- as
everyone does now).

So it would seem natural that errors would propagate
faster on big base systems, AOTBE, but this may be
a naive view..

I don't know of any current support for this view. It the bad old days,
such things were often confused by architectures that mixed non-binary
bases with "creative" rounding rules (like truncation indeed), and it
could be hard to know where to "pin the blame".

What you will still see stated is variations on Kahan's telegraphic
"binary is better than any other radix for error analysis (but not very
much)", listed as one of two techincal advantages for binary fp in:

http://www.cs.berkeley.edu/~wkahan/MktgMath.pdf

It's important to note that he says "error analysis", not "error
propagation" -- regardless of base in use, rounding is good to <= 1/2
ULP. A fuller elementary explanation of this can be found in David
Goldberg's widely available "What Every Computer Scientist Should Know
About Floating-Point", in its "Relative Error and Ulps" section. The
short course is that rigorous forward error analysis of fp algorithms is
usually framed in terms of relative error: given a computed
approximation x' to the mathematically exact result x, what's the
largest possible absolute value of the mathematical

r = (x'-x)/x

(the relative error of x')? This framework gets used because it's more-
or-less tractable, starting by assuming inputs are exact (or not, in
which case you start by bounding the inputs' relative errors), then
successively computing relative errors for each step of the algorithm.
Goldberg's paper, and Knuth volume 2, contain many introductory examples
of rigorous analysis using this approach.

Analysis of relative error generally goes along independent of FP base.
It's at the end, when you want to transform a statement about relative
error into a statement about error as measured by ULPs (units in the
last place), where the base comes in strongly. As Goldberg explains,
the larger the fp base the sloppier the relative-error-converted-to-ULPs
bound is -- but this is by a constant factor independent of the
algorithm being analyzed, hence Kahan's "... better ... but not very
much". In more words from Goldberg:

Since epsilon [a measure of relative error] can overestimate the
effect of rounding to the nearest floating-point number by the
wobble factor of B [the FP base, like 2 for binary or 10 for
decimal], error estimates of formulas will be tighter on machines
with a small B.

When only the order of magnitude of rounding error is of interest,
ulps and epsilon may be used interchangeably, since they differ by
at most a factor of B.

So that factor of B is irrelevant to most apps most of the time. For a
combination of an fp algorithm + set of inputs near the edge of giving
gibberish results, of course it can be important. Someone using
Python's decimal implementation has an often very effective workaround
then, short of writing a more robust fp algorithm: just boost the
precision.

Thanks Tim, for taking the trouble. - really nice explanation.

My basic error of thinking ( ? - more like gut feel ) was that the
bigger bases somehow lose "more bits" at every round,
forgetting that half a microvolt is still half a microvolt, whether
it is rounded in binary, decimal, or hex...

- Hendrik

 

[Nick Maclaren]

|>
|> > What you will still see stated is variations on Kahan's telegraphic
|> > "binary is better than any other radix for error analysis (but not very
|> > much)", listed as one of two techincal advantages for binary fp in:
|> >
|> > http://www.cs.berkeley.edu/~wkahan/MktgMath.pdf

Which I believe to be the final statement of the matter. It was a minority
view 30 years ago, but I now know of little dissent.

He has omitted that mid-point invariant as a third advantage of binary,
but I agree that it could be phrased as "one or two extra mathematical
invariants hold for binary (but not very important ones)".

|> My basic error of thinking ( ? - more like gut feel ) was that the
|> bigger bases somehow lose "more bits" at every round,
|> forgetting that half a microvolt is still half a microvolt, whether
|> it is rounded in binary, decimal, or hex...

That is not an error, but only a mistake

Yes, you have hit the nail on the head. Some people claimed that some
important algorithms did that, and that binary was consequently much
better. If it were true, then the precision you would need would be
pro rata to the case - so the decimal equivalent of 64-bit binary would
need 160 bits.

Experience failed to confirm their viewpoint, and the effect was seen
in only artificial algorithms (sorry - I can no longer remember the
examples and am reluctant to waste time trying to reinvent them). But
it was ALSO found that the converse was not QUITE true, either, and the
effective numerical precision is not FULLY independent of the base.

So, at a wild guesstimate, 64-bit decimal will deliver a precision
comparable to about 56-bit binary, and will cause significant numerical
problems to a FEW applications. Hence people will have to convert to
the much more expensive 128-bit decimal format for such work.

Bloatware rules. All your bits are belong to us.


Regards,
Nick Maclaren.

 

[Nick Maclaren]

|> >
|> I would suspect that this is one of those questions which are simple
|> to ask, but horribly difficult to answer - I mean - if the hardware has
|> thrown it away, how do you study it - you need somehow two
|> different parallel engines doing the same stuff, and comparing the
|> results, or you have to write a big simulation, and then you bring
|> your simulation errors into the picture - There be Dragons...

No. You just emulate floating-point in software and throw a switch
selecting between the two rounding rules.


Regards,
Nick Maclaren.

 

[Dennis Lee Bieber]

I recall an SF character known as "Slipstick Libby",
who was supposed to be a Genius - but I forget
the setting and the author.

Robert Heinlein. Appears a few of the Lazarus Long books.

It is something that has become quietly extinct, and
we did not even notice.

And get collector prices --
http://www.sphere.bc.ca/test/sruniverse.html
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[Tim Roberts]

I would suspect that this is one of those questions which are simple
to ask, but horribly difficult to answer - I mean - if the hardware has
thrown it away, how do you study it - you need somehow two
different parallel engines doing the same stuff, and comparing the
results, or you have to write a big simulation, and then you bring
your simulation errors into the picture - There be Dragons...

Actually, this is a very well studied part of computer science called
"interval arithmetic". As you say, you do every computation twice, once to
compute the minimum, once to compute the maximum. When you're done, you
can be confident that the true answer lies within the interval.

For people just getting into it, it can be shocking to realize just how
wide the interval can become after some computations.

 

[Hendrik van Rooyen]

Robert Heinlein. Appears a few of the Lazarus Long books.

And get collector prices --
http://www.sphere.bc.ca/test/sruniverse.html

Thanks Dennis - Fascinating site !

- Hendrik

 

[Nick Maclaren]

|>
|> >> What I don't know is how much precision this approximation loses when
|> >> used in real applications, and I have never found anyone else who has
|> >> much of a clue, either.
|> >>
|> >I would suspect that this is one of those questions which are simple
|> >to ask, but horribly difficult to answer - I mean - if the hardware has
|> >thrown it away, how do you study it - you need somehow two
|> >different parallel engines doing the same stuff, and comparing the
|> >results, or you have to write a big simulation, and then you bring
|> >your simulation errors into the picture - There be Dragons...
|>
|> Actually, this is a very well studied part of computer science called
|> "interval arithmetic". As you say, you do every computation twice, once to
|> compute the minimum, once to compute the maximum. When you're done, you
|> can be confident that the true answer lies within the interval.

The problem with it is that it is an unrealistically pessimal model,
and there are huge classes of algorithm that it can't handle at all;
anything involving iterative convergence for a start. It has been
around for yonks (I first dabbled with it 30+ years ago), and it has
never reached viability for most real applications. In 30 years, it
has got almost nowhere.

Don't confuse interval methods with interval arithmetic, because you
don't need the latter for the former, despite the claims that you do.

|> For people just getting into it, it can be shocking to realize just how
|> wide the interval can become after some computations.

Yes. Even when you can prove (mathematically) that the bounds are
actually quite tight


Regards,
Nick Maclaren.

 

[Rhamphoryncus]

The problem with it is that it is an unrealistically pessimal model,
and there are huge classes of algorithm that it can't handle at all;
anything involving iterative convergence for a start. It has been
around for yonks (I first dabbled with it 30+ years ago), and it has
never reached viability for most real applications. In 30 years, it
has got almost nowhere.

Don't confuse interval methods with interval arithmetic, because you
don't need the latter for the former, despite the claims that you do.

|> For people just getting into it, it can be shocking to realize just how
|> wide the interval can become after some computations.

Yes. Even when you can prove (mathematically) that the bounds are
actually quite tight

I've been experimenting with a fixed-point interval type in python. I
expect many algorithms would require you to explicitly
round/collapse/whatever-term the interval as they go along, essentially
making it behave like a float. Do you think it'd suitable for
general-use, assuming you didn't mind the explicit rounding?

Unfortunately I lack a math background, so it's unlikely to progress
past an experiment.

 

[Nick Maclaren]

|>
|> I've been experimenting with a fixed-point interval type in python. I
|> expect many algorithms would require you to explicitly
|> round/collapse/whatever-term the interval as they go along, essentially
|> making it behave like a float.

Yes, quite.

|> Do you think it'd suitable for
|> general-use, assuming you didn't mind the explicit rounding?

I doubt it. Sorry.

|> Unfortunately I lack a math background, so it's unlikely to progress
|> past an experiment.

As the same is true for what plenty of people have done, despite them
having good backgrounds in mathematics, don't feel inferior!


Regards,
Nick Maclaren.

 

[Scott David Daniels]

... Alas, most people wouldn't read that either <0.5 wink>.

Oh the loss, you missed the chance for a <0.499997684987 wink>.

--Scott David Daniels
(e-mail address removed)

 

[Hendrik van Rooyen]

[Tim Roberts]

|> Actually, this is a very well studied part of computer science called
|> "interval arithmetic". As you say, you do every computation twice, once to
|> compute the minimum, once to compute the maximum. When you're done, you
|> can be confident that the true answer lies within the interval.

The problem with it is that it is an unrealistically pessimal model,
and there are huge classes of algorithm that it can't handle at all;
anything involving iterative convergence for a start. It has been
around for yonks (I first dabbled with it 30+ years ago), and it has
never reached viability for most real applications. In 30 years, it
has got almost nowhere.

Don't confuse interval methods with interval arithmetic, because you
don't need the latter for the former, despite the claims that you do.

|> For people just getting into it, it can be shocking to realize just how
|> wide the interval can become after some computations.

Yes. Even when you can prove (mathematically) that the bounds are
actually quite tight

This sounds like one of those pesky:
"but you should be able to do better" - kinds of things...

- Hendrik

 

[Nick Maclaren]

|>
|> [ Interval arithmetic ]
|>
|> > |> For people just getting into it, it can be shocking to realize just how
|> > |> wide the interval can become after some computations.
|> >
|> > Yes. Even when you can prove (mathematically) that the bounds are
|> > actually quite tight
|>
|> This sounds like one of those pesky:
|> "but you should be able to do better" - kinds of things...

It's worse :-(

It is rather like global optimisation (including linear programming
etc.) The algorithms that are guaranteed to work are so catastrophically
slow that they are of theoretical interest only, but almost every
practical problem can be solved "well enough" with a hack, IF it is
coded by someone who understands both the problem and global
optimisation.

This is why the "statistical" methods (so disliked by Kahan) are used.
In a fair number of cases, they give reasonable estimates of the error.
In others, they give a false sense of security :-(


Regards,
Nick Maclaren.