5 ms·

This essay only covers underflow and overflow, and gives an example of "correct" summation for Rust. fn sum_up_numbers_correctly(numbers: &[i32]) -> Option<i

This essay only covers underflow and overflow, and gives an example of "correct" summation for Rust. 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) } I expected it to also mention the Kahan summation algorithm (https://en.wikipedia.org/wiki/Kahan_summation_algorithm https://en.wikipedia.org/wiki/Kahan_summation_algorithm), which gives more accurate results than this checked_add solution, but it did not. I wonder if that will be in one of the subsequent blog posts.

deleted 2y ago
[deleted]
lifthrasiir 2y ago
To be clear, the checked_add solution is for integers while the Kahan summation is for IEEE 754 numbers. (There is no `f32::checked_add` or similar.)
- eesmith 2y ago
  You're right! I am not a Rust programmer and mis-read the "i32" as "float32". 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."
  - jepler 2y ago
    You don't need machine code these days to find overflow in IEEE floating point arithmetic. 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.
  - tialaramex 2y ago
    Rust's 32-bit floating point type is, unsurprisingly, named f32 (stable Rust also has f64, and unstable builds offer f16 and possibly f128 which are both newer IEEE formats) 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.
    - lifthrasiir 2y ago
      Indeed, this approach is known as a superaccumulator [1] and faster overall than the Kahan summation for a large amount of numbers. I don't exactly know the currently accepted threshold but 10,000 numbers should be conservative enough for that. [1] https://arxiv.org/abs/1505.05571 https://arxiv.org/abs/1505.05571
- SideQuark 2y ago
  > There is no `f32::checked_add` 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.
msichert 2y ago
Hey, I'm the author of the blog post! 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.

deleted 2y ago

[deleted]

lifthrasiir 2y ago

To be clear, the checked_add solution is for integers while the Kahan summation is for IEEE 754 numbers. (There is no `f32::checked_add` or similar.)

eesmith 2y ago
You're right! I am not a Rust programmer and mis-read the "i32" as "float32". 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."
- jepler 2y ago
  You don't need machine code these days to find overflow in IEEE floating point arithmetic. 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.
- tialaramex 2y ago
  Rust's 32-bit floating point type is, unsurprisingly, named f32 (stable Rust also has f64, and unstable builds offer f16 and possibly f128 which are both newer IEEE formats) 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.
  - lifthrasiir 2y ago
    Indeed, this approach is known as a superaccumulator [1] and faster overall than the Kahan summation for a large amount of numbers. I don't exactly know the currently accepted threshold but 10,000 numbers should be conservative enough for that. [1] https://arxiv.org/abs/1505.05571 https://arxiv.org/abs/1505.05571
SideQuark 2y ago
> There is no `f32::checked_add` 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.

msichert 2y ago

Hey, I'm the author of the blog post! 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.