The following incredibly small sorting algorithm has an $O(n^{4/3})$ worst-case runtime: def fibonacci_sort(v): a, b = 1 , 1 while a * b < len(v): a, b = b, a + b while a > 0 : a, b = b - a, a g = a * b for i in range(g, len(v)): while i >= g and v[i - g] > v[i]: v[i], v[i - g] = v[i - g], v[i] i -= g As the name implies, it uses the Fibonacci sequence ($1, 1, 2, 3, 5, \dots$) to sort the…
It seems that in 2025 a lot of people fall into one of two camps when it comes to AI: skeptic or fanatic. The skeptic thinks AI sucks, that it’s overhyped, it only ever parrots nonsense and it will all blow over soon. The fanatic thinks general human-level intelligence is just around the corner, and that AI will solve almost all our problems. I hope my title is sufficiently ambiguous to attract…
Hash functions are incredibly neat mathematical objects. They can map arbitrary data to a small fixed-size output domain such that the mapping is deterministic, yet appears to be random. This “deterministic randomness” is incredibly useful for a variety of purposes, such as hash tables , checksums , monte carlo algorithms , communication-less distributed algorithms , etc, the list goes on. In this…
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 ;…
Suppose you have a 64-bit word and wish to extract a couple bits from it. For example you just performed a SWAR algorithm and wish to extract the least significant bit of each byte in the u64 . This is simple enough, you simply perform a binary AND with a mask of the bits you wish to keep: let out = word & 0x0101010101010101 ; However, this still leaves the bits of interest spread throughout the…
This post is an anecdote from over a decade ago, of which I lost the actual code. So please forgive me if I do not accurately remember all the details. Some details are also simplified so that anyone that likes computer security can enjoy this article, not just those who have played World of Warcraft (although the Venn diagram of those two groups likely has a solid overlap). When I was around 14…
A partition function accepts as input an array of elements, and a function returning a bool (a predicate ) which indicates if an element should be in the first, or second partition. Then it returns two arrays, the two partitions : def partition(v, pred): first = [x for x in v if pred(x)] second = [x for x in v if not pred(x)] return first, second This can actually be done without needing any extra…
To be precise, IEEE-754 floating point subtraction is functionally complete . That means you can construct any binary circuit using nothing but floating point subtraction. To see how, we must start at the bottom. I quote the IEEE 754-2019 standard, section 6.3: 6.3 The sign bit […] When neither the inputs nor result are NaN, […]; the sign of a sum, or of a difference $x−y$ regarded as a sum…
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…
The following Python function computes the Fibonacci sequence , without loops, recursion or floating point arithmetic: f= lambda n:(b:= 2 <<n)**n*b//(b*b-b- 1 )%b It really does: >>> [f(n) for n in range( 10 )] [ 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 ] How does it work? As a teaser, look at the decimal expansions of $100 / 9899$ and $1000 / 998999$ and see if you notice…
This article is not about deciding whether two floating point numbers are ‘close enough’. There are plenty of resources on this (often subjective) problem. We simply want to know if ${x \leq y.}$ Suppose that you are a programmer, and that you have two numbers. You want to know which number, if any, is larger. Now, if both numbers have the same type, the solution is trivial in almost any…