why 'lambda' and 'reduce'?

Manuel M Garcia mail at manuelmgarcia.com
Sat Jun 14 20:48:14 CEST 2003


On Sat, 14 Jun 2003 08:38:31 -0600, Steven Taschuk
<staschuk at telusplanet.net> wrote:

>Assuming the arithmetic of each iteration introduces error which
>is less than quadratic in the number of iterations so far... which
>is very plausible, without even looking at the code again.
>
>And that the initial state is "correct enough" to get it all
>started.  (The quadratic convergence might just be asymptotic
>behaviour; initially it might have much worse behaviour, and thus
>susceptible to the arithmetic error.)

As long as you play by the computer's rules, error is not much of a
problem.  To get 5000 digits, I only had to give the computer 10 extra
digits to work with, and that was probably overkill.  If you get your
algorithms from books, you can trust they will be stable.

The last digit is never to be trusted, but unless you are using a
silly rounding rule, the last digit is actually innocent until proven
guilty.  Error would start at the last digit, and grow from there,
hopefully slowly.  If there is just as much 'jitter' in the positive
direction as the negative direction, the growth will be slow, because
a lot of the errors will cancel each other out.

For the most part, 3 things can cause error to grow unmanageably with
floating point:

1) Bias.  One of the operations you use a lot always adds some error,
and always in the same direction (truncation is good for adding this
error, I break this rule using integer math in the program, but
happily I don't need enough iterations to get burned)
2) Subtraction with two numbers that are _very_ close together
(hopefully you can use algebra to prevent this).
3) adding together a lengthy series of very small numbers, hoping they
will grow into a large number (this is why many pretty looking
infinite forms of Pi are no darn good to compute digits)

(There are other problems you can have with financial data, dealing
with different stupid rounding rules)

And if you are working with integers, you can have 1 more error,
forgetting to scale up before division.

(if I forgot any others, I guess I will learn them the hard way ;-)

If you play by these rules, things work out pretty good.  The worst
case scenario with error never shows up.

Manuel




More information about the Python-list mailing list