How can I add floats together in different orders, and always get the same total?

Posted by splicer on Stack Overflow See other posts from Stack Overflow or by splicer
Published on 2010-04-24T11:52:49Z Indexed on 2010/04/24 12:03 UTC
Read the original article Hit count: 161

Filed under:

numerical

|

order

|

floating-point

|

arithmetic

|

kahan-summation

Let's say I have three 32-bit floating point values, a, b, and c, such that (a + b) + c != a + (b + c). Is there summation algorithm, perhaps similar to Kahan summation, that guarantees that these values can be summed in any order and always arrive at the exact same (fairly accurate) total? I'm looking for the general case (i.e. not a solution that only deals with 3 numbers).

Is arbitrary precision arithmetic the only way to go? I'm dealing with very large data sets, so I'd like to avoid the overhead of using arbitrary precision arithmetic if possible.

Thanks!

© Stack Overflow or respective owner

Related posts about numerical

good books on numerical computation with C

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I've read the post "What is the best book on numerical methods?" and I wish to ask more or less the same question but in relation to C programming. Most of the time, C programming books on numerical methods are just another version of the author's previous Fortran book on the same subject. I've… >>> More
Integration error in high velocity

as seen on Game Development - Search for 'Game Development'
I've implemented a simple simulation of two planets (simple 2D disks really) in which the only force is gravity and there is also collision detection/response (collisions are completely elastic). I can launch one planet into orbit of the other just fine. The collision detection code though does not… >>> More
Typical Applications of Linear System Solver in Game Developemnt

as seen on Game Development - Search for 'Game Development'
I am going to write a custom solver for linear system. I would like to survey the typical problems involved the linear system solving in games. So that I can custom optimization on these problems based on the shape of the matrix. currently I am focus on these problems: B-Spline editing (I use… >>> More
HTML numerical to UTF

as seen on Stack Overflow - Search for 'Stack Overflow'
How can i convert this $langClarContent = &# 1059.,ч.,и.,&# 1090.,&# 1077.,&# 1083.,Dokeos &# 1077., &# 1089.,&# 1080.,&# 1089.,&# 1090.,&# 1077.,&# 1084., &# 1079.,&# 1072., &# 1091.,&# 1087.,&# 1088.,&# 1072.,&#… >>> More
Algorithm to generate numerical concept hierarchy

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a couple of numerical datasets that I need to create a concept hierarchy for. For now, I have been doing this manually by observing the data (and a corresponding linechart). Based on my intuition, I created some acceptable hierarchies. This seems like a task that can be automated. Does anyone… >>> More

Related posts about order

CakePHP: find neighbors, order on 'name' or 'order'

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have a list of ordered items, ordered according to the int field order. I'm creating a gallery in CakePHP 1.2 that has a prev and next button and those should link to the previous and next item according to their ordering, not according to their id. In order to get this result I've included… >>> More
how to get the int order sorting asc, the order field already in varchar type

as seen on Stack Overflow - Search for 'Stack Overflow'
I have the field receiptno as varchar and want to sort this, if normal order sorting getting wrong sorting value. Then have the idea to sort the field by convert int type. Is there anyway to converting int type in query itself >>> More
ASP.NET MVC 2: Mechanics behind an Order / Order Line in a edit form

as seen on Stack Overflow - Search for 'Stack Overflow'
In this question I am looking for links/code to handle an IList<OrderLine> in an MVC 2 edit form. Specifically I am interested in sending a complete order to the client, then posting the edited order back to an object (to persist) using: Html.EditorFor(m = m.orderlines[i]) (where orderlines… >>> More
Treeset to order elements in descending order

as seen on Stack Overflow - Search for 'Stack Overflow'
Here is the piece of code that I have used for Java 5.0 TreeSet<Integer> treeSetObj = new TreeSet<Integer>( Collections.reverseOrder() ) ; Collections.reverseOrder() is used to obtain a comparator in order to reverse the way the elements are stored and iterated. Is there a more optimized… >>> More
Search results in wordpress, order by custom category order and time DESC

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello I want to change default post search order to order: sample cat 1 sample post from cat 1 sample post from cat 1 sample cat 2 sample post from cat 2 sample post from cat 3 sample cat 3 etc.. So... I want to define category order and in search results will be sorted for this order and… >>> More