[Tutor] very odd math problem

Steven D'Aprano steve at pearwood.info
Fri Mar 11 12:30:50 CET 2011

```Alan Gauld wrote:

> Why would you use a loop when the final value is just
> the final multiplication. Since you know the final value
> in advance (you need it to create the loop!) why not
> just do the final multiplication directly:
>
> x = 10*0.1
>
> I think I'm missing something?

The context was generating a list of values, not just the final value.
But the result can be generalized to other situations. Consider some
function that calculates a result x by an iterative process. You don't
care about the intermediate results, but you do have to step through
them on the way to the final result:

x = initial_value
while condition:
x += increment(x)

When possible, it is better to re-write the formula to avoid repeatedly
adding an increment to x. The problem is, if each addition has potential
error of dx, then N additions have potential error N*dx -- you can't
assume that errors will always cancel. If N is large, so is the expected
error.

If it isn't possible to re-write it, then you have to take care to
control for the error, which is hard. This is why good maths software
tends to be horrible code, and why pretty code tends to make terrible
maths software :(

Another source of errors is catastrophic cancellation, when intermediate
terms in a calculation cancel so badly that the end result is
*completely* wrong. To see an especially extreme example, here's a
torture test for summation by Tim Peters:

>>> sum([1, 1e100, 1, -1e100] * 10000)
0.0

This sum *should* add up to 20000:

1 + 1e100 + 1 - 1e100 + 1 ... + 1e100 + 1 - 1e100
= 1 + 1 + 1 + ... + 1
= 20000

but due to round-off error at each step, it cancels to zero:

>>> sum([1, 1e100, 1, -1e100] * 10000)
0.0

The math module starting in Python 2.6 has a specialised high-precision
sum function that can cope:

>>> import math
>>> math.fsum([1, 1e100, 1, -1e100] * 10000)
20000.0

--
Steven

```