Topic
Everything filed under Algorithms, newest first.
RSS · JSON · All topics
Golden Board: teaching chess without a shared language
Golden Board is a 512 KiB binary message designed to teach chess to an unknown recipient with no shared language, starting by teaching the format needed to read its own contents, then pictures, interactions and the rules of chess.
61 min · 14,039 words
A short explainer of the 'I can't believe it can sort' algorithm from Stanley P. Y. Fung's paper: a deceptively simple O(n^2) nested-loop swap sort, with pseudocode and a Java implementation.
1 min · 256 words
Writing from a part-time job on a Lisp compiler, the author explains Kildall's dataflow analysis algorithm and how it is used for analyses such as escape analysis in a Lisp compiler's intermediate representation.
13 min · 2,879 words
Steinar H. Gunderson strongly solves the Norse Fox Game (halatafl): with perfect play the sheep win, even with 19 sheep (18 moving first), and 9 sheep can force a draw. He explains the bitboard representation and retrograde search behind his ~1000-line solver.
9 min · 2,096 words
Probabilistic data structures in Go
An explainer on Bloom filters, count-min sketches, HyperLogLog, t-digest and top-k sketches: how they trade exactness for memory, what guarantees they give, and an introduction to unsure, a dependency-free Go package implementing them.
22 min · 5,130 words
blqsort - A C++ Quicksort Faster Than std::sort
Christof Kaser presents blqsort, an MIT-licensed branchless quicksort for C and C++ that beats std::sort and ipnsort on random and partially sorted data, with benchmarks and an explanation of how it works.
41 min · 9,518 words
e-means: 10x faster k-means at equal loss
Researchers at Meta FAIR open-source e-means, a replacement for Lloyd's k-means algorithm that reaches lower test loss in 1.2 to 3 epochs instead of 25, a 10–45x wall-clock speedup on GPU versus Flash-KMeans and 8–15x on CPU versus Faiss.
12 min · 2,753 words
Constructing a Quine from Kleene's Second Recursion Theorem
A walkthrough of formalizing Kleene's second recursion theorem from both classical and functional programming perspectives, then using the construction to build a working quine in untyped lambda calculus.
10 min · 2,293 words
Could a modern chess engine on a Pentium have defeated Kasparov in 1996?
Nicholas Carlini ports Stockfish to a 1995 200 MHz Pentium Pro with 64MB RAM, estimates it plays around 3300 Elo at classical time controls, and argues that algorithmic progress alone would have let commodity 1996 hardware beat Kasparov without Deep Blue, with lessons for software versus hardware gains in AI.
14 min · 3,118 words
Galactus the Devourer: Efficient algorithms, the Exponential Time Hypothesis, and losing the plot
Ben Recht traces how computer science never rigorously defined 'efficient' algorithms, from Jack Edmonds' 1965 digression through polynomial time and P vs NP to the Exponential Time Hypothesis, arguing complexity theory's scaffolding drifted away from the practical problems, such as industrial SAT solving, it was meant to describe.
6 min · 1,428 words
How hard is it to check for whitespace?
Sergey Tselovalnikov follows Guava's surprisingly complex isWhitespace matcher down a rabbit hole into Unicode's many whitespace characters, how different languages define whitespace, and the perfect-hashing trick that makes the check fast.
6 min · 1,375 words
How curl was accidentally Turing-complete for nine months
Nicolas Seriot shows that from curl 8.12 through 8.16, config-file variable slicing plus uncapped config includes let curl simulate any two-counter Minsky machine, making it Turing-complete in principle until curl 8.17.0 added a five-level include cap.
2 min · 457 words
Can GROUP BY still be optimized after all these years?
Pivot walks through how analytical databases execute GROUP BY and shares a novel optimization for GROUP BY queries with a Top-K operator above them, pruning partitions during execution for a 1.6x speedup on a ClickBench-style query.
6 min · 1,372 words
11 nanoseconds per word: Ridiculously Over-Optimizing Anagrams
David G. Andersen builds a solver for an anagram-enabled word ladder game and then over-optimizes its anagram indexing in Rust, using collision-free prime-product (Gödel numbering) identifiers, packed inputs and branchless loops to reach about 11 ns per word.
9 min · 2,171 words
Bitter Lessons and Premature Optimizations
Veit Heller revisits Knuth’s ‘premature optimization’ line and Rich’s Bitter Lesson, arguing that the shape of efficiency arguments—not just the slogans—matters when building AI systems and robots.
7 min · 1,668 words
Andrea Piseri looks at how array languages like APL implement scans over packed boolean arrays, where a naive loop manages about 0.6 elements per cycle. Using truth-table symmetries, the essay shows that fast versions of just and, less-than and xor are enough to derive good implementations of every other boolean scan, with bit-twiddling implementations in an appendix.
14 min · 3,251 words
Jim Calabro walks through how bloom filters work, how Bluesky moved from multiple hash functions to double hashing to cut contention, and then explores the one-hash bloom filter from Lu et al., which splits the bit array into partitions with pairwise coprime sizes so a single hash can stand in for k independent ones.
6 min · 1,387 words
Khalid Hamadeh shows that the 256-byte PITABLE in Ron Rivest’s RC2 cipher (RFC 2268), and a second unexplained table, are reproduced exactly by a Fisher–Yates shuffle driven by the decimal digits of π, three digits per draw, with code to verify it.
13 min · 2,954 words
EvoGrain: Algorithmic Sound Design with L-Systems and Granular Synthesis
Nathan Ho walks through building EvoGrain, an open-source system that randomly generates L-systems, expands them into command sequences, interprets those as sets of grains, and renders them with granular synthesis, covering inspirations like Iamus, the design of each pipeline stage, and generated sound examples.
30 min · 6,813 words
Designing more efficient quantum circuits with Claude
Anthropic describes giving Claude plain-language specifications for eight quantum circuits from chemistry, optimization, physics simulation and number theory, plus an automated evaluator. Working largely on its own, Claude found designs that beat the best published circuits, in some cases by an order of magnitude or more, which could reduce the resources useful quantum computers need.
17 min · 3,860 words