orlp.net - Blog Archive

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…

It seems that in 2025 a lot of people fall into one of two camps when it comes to AI: skeptic or fanatic.

Hash functions are incredibly neat mathematical objects.

Suppose you have an array of floating-point numbers, and wish to sum them.

Suppose you have a 64-bit word and wish to extract a couple bits from it.

This post is an anecdote from over a decade ago, of which I lost the actual code.

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.

To be precise, IEEE-754 floating point subtraction is functionally complete.

I recently read the article Beautiful Branchless Binary Search by Malte Skarupke.

This December I once again did the Advent of Code, in Rust.

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?

This article is not about deciding whether two floating point numbers are ‘close enough’.