はてなブックマーク

Suppose you have an array of floating-point numbers, and wish to sum them. You might naively think you can simply add them, e.g. in Rust: fn naive_sum(arr: &[f32]) -> f32 { let mut out = 0.0; for x in arr { out += *x; } out } This however can easily result in an arbitrarily large accumulated error. Let’s try it out: naive_sum(&vec![1.0; 1_000_000]) = 1000000.0 naive_sum(&vec![1.0; 10_000_000]) = 1

I recently read the article Beautiful Branchless Binary Search by Malte Skarupke. In it they discuss the merits of the following snippet of C++ code implementing a binary search: template<typename It, typename T, typename Cmp> It lower_bound_skarupke(It begin, It end, const T& value, Cmp comp) { size_t length = end - begin; if (length == 0) return end; size_t step = bit_floor(length); if (step !=

This December I once again did the Advent of Code, in Rust. If you are interested, my solutions are on Github. I wanted to highlight one particular solution to the day 2 problem as it is both optimized completely beyond the point of reason yet contains a useful technique. For simplicity we’re only going to do part 1 of the day 2 problem here, but the exact same techniques apply to part 2. We’re go