orlp.net - Blog...
Sorting with Fibonacci Numbers and a Knuth Reward Check
The following incredibly small sorting algorithm has an $O(n^{4/3})$ worst-case runtime:
def...
31st Dec 2025
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)):
...
orlp.net - Blog...
Why Bad AI Is Here to Stay
It seems that in 2025 a lot of people fall into one of two camps when it comes
to AI: skeptic or...
2nd Feb 2025
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...
orlp.net - Blog...
Breaking CityHash64, MurmurHash2/3, wyhash, and more...
Hash functions are incredibly
neat mathematical objects. They can map arbitrary data to a small...
2nd Nov 2024
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...
orlp.net - Blog...
Taming Floating-Point Sums
Suppose you have an array of floating-point numbers, and wish to sum them.
You might naively think...
25th May 2024
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...
orlp.net - Blog...
When Random Isn't
This post is an anecdote from over a decade ago, of which I lost the actual
code. So please forgive...
10th Jan 2024
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...
orlp.net - Blog...
Branchless Lomuto Partitioning
A partition function accepts as input an array of elements, and a function
returning a bool (a...
4th Dec 2023
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...
orlp.net - Blog...
Subtraction Is Functionally Complete
To be precise, IEEE-754 floating point
subtraction is functionally
complete. That means you
can...
28th Sep 2023
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...
orlp.net - Blog...
Bitwise Binary Search: Elegant and Fast
I recently read the article Beautiful Branchless Binary Search
by Malte Skarupke. In it they discuss...
16th May 2023
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&...
orlp.net - Blog...
The World's Smallest Hash Table
This December I once again did the Advent of Code,
in Rust. If you are interested, my solutions
are...
4th Mar 2023
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...
orlp.net - Blog...
Magical Fibonacci Formulae
The following Python function computes the Fibonacci
sequence, without loops,
recursion or floating...
6th Feb 2023
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...
Full Width 
Shortcuts 
Sign Up 
Log In 
Articles 
Reading List 