Hacker News new | past | comments | ask | show | jobs | submit login

There's even more cleverness you can do -- there are exact summation algorithms[1], which guarantee that the sum you get is the floating point representation of the real number sum corresponding to the sum of the real numbers corresponding to the summands (that's a mouthful!). However, they have superlinear runtimes and non-constant space (well, assuming you don't incorporate the size of the float into the constant). In Python, you can use math.fsum to use one. However, even these cannot recover already-lost precision, so these need to be used with care as well. For example, if you solve a quadratic and average the two roots to get the quadratic's maximum or minimum (stupid approach, yes this is contrived), you already have some lost precision in solving the quadratic and rounding results that isn't possible to recover. Also, if there is cancellation involved, there is error you can't recover from -- this is called the condition number of the sum (it is (Sum abs(x_i)) / abs(Sum x_i)), and it represents a error bound (of a complex sort) that it's impossible to improve upon.

[1] www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: