Full Width [alt+shift+f] Shortcuts [alt+shift+k]
Sign Up [alt+shift+s] Log In [alt+shift+l]

orlp.net - Blog Archive

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...
2 weeks ago
18
2 weeks ago
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...
3 months ago
46
3 months ago
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...
9 months ago
35
9 months ago
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...
Extracting and Depositing Bits Suppose you have a 64-bit word and wish to extract a couple bits from it. For example you just...
a year ago
17
a year ago
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...
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...
a year ago
17
a year ago
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...
a year ago
15
a year ago
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...
a year ago
15
a year ago
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...
a year ago
15
a year ago
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...
a year ago
12
a year ago
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...
over a year ago
14
over a year ago
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...
orlp.net - Blog...
Ordering Numbers, How Hard Can It Be? This article is not about deciding whether two floating point numbers are ‘close enough’. There are...
over a year ago
15
over a year ago
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...