How to Correctly Sum Up Numbers
cedardb.com
cedardb.com
For example, this is the proposed rust solution (imho the most readable):
fn sum_up_numbers_correctly(numbers: &[i32]) -> Option<i32> {
let mut sum: i32 = 0;
for i in numbers {
sum = sum.checked_add(*i)?;
}
Some(sum)
}
The upside of wrapping addition is that you can overflow as often as you want, as long as the result is within the range of the type, the result (of addition and subtraction) is correct. The downside is that you don't know if the result is within range. So you trade between correctly handling a larger range of inputs with wrapping or being more certain of the result with checked overflow.
My preferred solution would have been just upcasting. If we make sum an i64 we know it can't overflow the intermediate if you sum less than 2^32 i32 numbers, and on a 64 bit machine you lose basically nothing by doing that. Keep the checked_add if you are concerned about people summing extremely long lists of numbers
fn sum_up_numbers_correctly(numbers: &[i32]) -> Option<i32> {
let mut sum: i64 = 0;
for i in numbers {
sum = sum.checked_add(*i as i64)?;
}
Some(sum.try_into().ok()?)
}
When summing i64 you can do the same trick by summing into an i128
You can't memorize your way into software engineering. You can't say, "always wrap-around when an operation overflows" or "always tell the user (panic) when an operation overflows".
This article is a great example. C wraps unsigned integer addition on overflow, but Python upscales to arbitrary integer sizes. The trade-off, of course, is performance. If you're writing a real-time engine (for a rocket or a video game) and you can guarantee integer sizes, then you need to use the fastest algorithm possible. But if you're writing a general-purpose calculator, you might prefer upscaling or at least catching overflows and informing the user.
In almost any other disciple there would be a "correct" way to do it, or at least an accepted "best practice." But for software engineers, it's always, "it depends."
* binary is the best way to encode information and numbers * twos complement is the best general purpose way to encode negative integers * static typing and stronger typing lead to fewer bugs * length prefixes are better than using sentinel values and escaping
> In almost any other discipline there would be a "correct" way to do it
Tell me you know nothing about anything except computers without...
You think there's a "correct" way to build a bridge?
* two's complement is the best general purpose way (tradeoffs!)
* static typing leads to fewer bugs (but makes development slower - tradeoffs)
* length prefixes are better than sentinels - but the largest system language uses sentinels for strings (because prefixes are not actually always better, be and sentinels were deemed better by its creators)
Not really I was more hedging against HN pedantry...
> but makes development slower - tradeoffs
No it doesn't. It makes development faster!
> because prefixes are not actually always better, be and sentinels were deemed better by its creators
Because they got it wrong.
In contrast, when making concrete, there are valid and invalid ratios of water/cement/etc. You have to memorize (or lookup) the correct ratios. Building a bridge is filled with things you have to look up or just compute from basic parameters.
Of course there are engineering trade-offs in building a bridge. But there are also many "just follow the algorithm" procedures. In software engineering, it's all trade-offs! Almost by definition, if there is a choice, it's a trade-off that requires human judgement, otherwise, the choice would be made for you by the computer.
I’ve heard Zig has convenient facilities for it.
If you were designing the flight software for the Ariane 5, which choice would you make?
I would take note of the underlying hardware and what range of inputs are allowed and code appropriately. Stop pretending that your software doesn’t have a specific purpose and will run on an actual computer. If you’re doing finance you should be using fixed point integer arithmetic with two or three decimal places. If you’re doing physics simulations you need to be aware of how many significant digits exist. If you ignore your problem space and the kind of system your code is going to run on you’re living in spherical cow world and it doesn’t matter if you over- or under-flow because your software is garbage anyway.
But it just reinforces my point that there are no absolute rules. You have to think.
The Wiki quotes an interesting sentence from the official report - "An underlying theme in the development of Ariane 5 is the bias towards the mitigation of random failure." It's fortunate that that bias didn't extend to flight termination system. At the point flight control software intersects with real life, it's better to destroy an expensive rocket than have it rain fiery hell on some random people somewhere else. That principle holds to this day.
fn sum_up_numbers_correctly(numbers: &[i32]) -> Option<i32> {
let mut sum: i32 = 0;
for i in numbers {
sum = sum.checked_add(*i)?;
}
Some(sum)
}
The text does imply the correct float solution has a similar structure to the int32 case, with "So, you will have to resort to writing machine code manually if you want to efficiently check overflows of float numbers."
If you're sure your answer is a 32-bit IEEE floating point number, I think you could store the intermediate sums as a fully expanded fixed point number with enough bits to go from the smallest possible f32 to the largest possible, so you're just doing (big integer) integer summation. 36 bytes ought to be very possible. When you've finished summing, you find the top-most set bit, its position decides the exponent and the subsequent 23 bits are your mantissa.
If any intermediate sum overflows, you get an infinity. Further arithmetic can never return you to the realm of finite numbers (though you can also get into the world of "not a number" NaNs by calculating -inf + inf for instance), so you can use a standard function like (C99 <math.h>) isfinite() to check if any intermediate step of summing FP numbers overflowed the representation.
You don't need it. You get +- inf on overflow and can decide what to do then. It's also not hard to pre-check before ops if they will succeed if you want to pay the price (same as integers, or any language libs that do the same). In general these ops are expensive and rarely needed.
Making a checked math lib is not terribly hard.
I had planned to write about the Kahan summation, but I didn't want to overload the blog post with too many different concepts. I'm definitely considering writing about it in a follow-up post.
If you're overflowing the exponent, then you need more than hardware magics. But for precision I've used these multi-double tricks with the same guarantees as IEEE style formats, but with as much precision as I want.
Since performance is important, not using floats is not an option, and you rarely see Kahan summation type of tricks because the heavy lifting is usually done by BLAS libraries (i.e. vectorized linear algebra operations).
So, in numerical algorithms the type of tricks is typically using stable matrix decompositions like the QR decomposition A = QR where Q'Q = I (repeated multiplication with Q leaves the quantities roughly the same size, whereas with A things blow up).
And there are other tricks, for example if you need to orthogonalize a vector x to this Q, in full precision you compute y = x - Q * (Q' * x), so that Q' * y = 0. The Q' * x computation is a reduction, so it can accumulate O(n eps) errors in finite precision. Instead of doing a more stable reduction (e.g. Kahan summation etc), you can instead repeat the computation: z = y - Q * (Q' * y). The idea is that the second orthogonalization step kills the rounding error noise introduced by the first step.
So in short: you can still get accuracy and decent performance with floats, you just have to know the tricks.
[Another somewhat interesting point is that on GPUs reductions are by necessity implemented with O(ln n eps) error, and the naive but vectorized CPU implementation has an error O(n/k eps) where k is the vector width]
There's an interesting case of it today: LLMs. In theory, they should be fully deterministic with "temperature" parameter set to 0, but they aren't - all that matrix multiplication is massively parallelized, so with floating point math being order-dependent, partial results quickly accumulate non-deterministic errors.
This summing problem is solved by xsum: https://gitlab.com/radfordneal/xsum
There is room for more work here to make it faster or use less memory though.
Plus after sorting you can use SIMD to sum everything much faster.
But yes, xsum and the like are more accurate.
I'm not saying the status-quo is wrongheaded, and I see no obvious way to solve it -- just an observation.
Pretty much any production compiler can do this. They can also warn when you truncate without doing so explicitly. Where I work, for certain projects, all C++ compilation does both of these, forcing programmers to explicitly cast into size to show they made a careful consideration of sizes.
Other places guarantee integers operate mod n, others guarantee integers grow as needed (e.g., Python).
That people don't learn the numerics of their platform is not the problem of the language or compiler. Using languages that are closer to the hardware means less hand holding when developing code, whether it's memory, numerics, files, or any part where one needs to pay attention and complexity increases.
I'm curious how a compiler could know this at compile time? If you mean a runtime checking feature, I get it. I'm referring to an example statement like `ix = ia + ib` where all three are, say, u8 integers.
EDIT: I will agree in some situations, the compiler could deduce that a certain equation like above would or would not ever overflow, by context. But for the general case, I don't see how.
> But if they ARE the same size, the compiler doesn't similarly complain "your result may overflow the destination variable"
Adding two N bit unsigned integers together can require N+1 bits for the answer. So the compiler, if you add two intN and store into an intN, will warn you that "your result may overflow the destination variable". This is trivial since the compiler knows the types of all the variables in most all programming languages.
Plenty of compilers also use theorem proving to ensure some things do not overflow, so they can optimize accordingly. Thus, in the follow type of program
int arr[10];
for (int i = 0; i < 10; ++i)
arr[i] = i;
But if you have
int arr[10];
func setLen(int len)
for (int i = 0; i < len; ++i)
arr[i] = i;
Modern compilers do an every increasing amount of amazing things to make all this work transparently.
My remarks have been about integers -- the typical programming language floating point rules (`f32 = f32 * f32`, etc) make sense to me.
EDIT: Markdown editor didn't like the asterisk in my example equation.
It's pretty easy to make a checked integer (or float) math lib/type in C++. Make a class that holds an int, overload the ops, check them. I regularly do such stuff when proving boundedness of algorithms, or performance of an algorithm. Such a class can track numbers of adds, mults, etc., can catch errors, can track values of stats, anything.
I also made and regularly use an IntN type: the idea is take half the max int size your system has natively, say IntN, and make a Int2N built by hand as a class. Now templateize it on size. Now you can recursively make Int2N, 4N, 8N, etc., from that template, basically for free (no more code needed), and have any size int.
There's a lot of cool numerics stuff you can do along these lines.
alias tally='awk -F '\''[^-.0-9]'\'' '\''{ for (i = 1; i <= NF; i++) s += $i } END { print s }'\'''