[Tutor] very odd math problem

[Steven D'Aprano]

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