Estimating a billion distinct things, to about 2%, takes 1.5 kilobytes

One regular expression took Cloudflare offline for 27 minutes

On 2 July 2019 a firewall rule containing a single regular expression, released to Cloudflare’s whole network at once, pushed processors to nearly 100% and the service went down for 27 minutes. Cloudflare’s own account lists several causes; the expression was the trigger.

A regular expression is a short pattern for finding text, such as “digits, then a dash”. Most programming languages match them by backtracking: try one reading of the pattern, and if it fails, back up and try the next. When a pattern contains a repeat inside a repeat, the number of readings can double with every extra character.

Ken Thompson described a way round this in 1968: follow every possible reading at the same time, one character per step, so the work grows in step with the length of the text. Russ Cox showed in 2007 that for one nasty pattern a 29-character string kept Perl busy for over sixty seconds, while the Thompson method took about twenty microseconds. Cloudflare’s own account of the outage lists, among its causes, a regular-expression engine without guarantees on running time.

Try the textbook case below: the pattern (a+)+b against a string of a’s with no b at the end, so the match must fail. Both matchers run the same five instructions, and each counts every instruction it executes.

Cloudflare’s pattern was different, but the failure mode is the same. Some engines have shortcuts that hide this particular pattern: Perl 5.34 rejected it at once when tried for this page, which is why the demo runs its own matcher. A real search also retries from every start position, which costs more still.

Cloudflare, “Details of the Cloudflare outage on July 2, 2019”; Russ Cox, “Regular Expression Matching Can Be Simple And Fast” (2007); Ken Thompson, “Regular Expression Search Algorithm”, Communications of the ACM 11(6), 419–422 (1968).

A billion distinct things can be estimated to about 2% in 1.5 kilobytes

The HyperLogLog algorithm estimates the number of distinct items in a stream of more than a billion, to a typical accuracy of 2%, using about 1.5 kilobytes of memory.

Counting distinct visitors exactly means remembering every one you have seen, so you do not count anyone twice, and the memory grows with the number of visitors. A billion 4-byte IDs would take 4 gigabytes. HyperLogLog remembers almost nothing, and pays for it with accuracy: it returns an estimate, not the count.

It turns each item into a random-looking string of bits and notes how rare a pattern it contains. A hash that starts with ten zeros turns up about once in a thousand items, so meeting one suggests that about a thousand items have gone past. The algorithm splits items into 2,048 buckets by their first 11 bits, keeps for each bucket the longest run of leading zeros it has seen among the other bits, and combines the 2,048 numbers into one estimate. Duplicates change nothing, because the same item always produces the same bits.

The paper stores each of the 2,048 numbers in 5 bits, which is enough for a 32-bit hash, and quotes about 1.5 kilobytes in all (2,048 × 5 bits is 1,280 bytes, so the paper’s figure is rounded up). The demo stores each in 6 bits, packed into a real array of 1,536 bytes. In 2013 engineers at Google published an improved version that they had implemented for a system at Google. Pick how many distinct items to feed the demo.

Flajolet, Fusy, Gandouet and Meunier, “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm” (2007), the paper (abstract and introduction: 2% accuracy, 1.5 kilobytes, 5-bit registers); Heule, Nunkesser and Hall, “HyperLogLog in Practice” (Google, 2013).

In a stable matching, whoever makes the offers gets the better deal

There can be several stable ways to pair up two groups, and the Gale–Shapley procedure gives every member of the group that proposes their best stable partner and every member of the other group their worst.

Suppose three people each rank three others, and those three rank them back. A pairing is stable if nobody would rather leave with someone else who would also rather have them. In 1962 David Gale and Lloyd Shapley proved that a stable pairing always exists and gave a simple procedure to find one: each proposer asks their favourite, each receiver keeps their best offer so far and turns the rest down, and the rejected try their next choice.

Which side proposes decides who benefits. With the same rankings, the proposers get their best stable partner and the receivers their worst. Shapley and Alvin Roth shared the 2012 economics Nobel Prize for this line of work, which Roth turned into real markets for matching.

Proposing also protects you. A proposer cannot gain by lying about their ranking, while a receiver sometimes can, for example by listing only their top choices.

Gale and Shapley, “College admissions and the stability of marriage”, American Mathematical Monthly 69(1), 9–15 (1962), Theorem 2 (every proposer gets the best partner any stable pairing gives them); Gale–Shapley algorithm (the receivers’ worst outcome and misreporting); Nobel Prize in Economic Sciences 2012, Roth and Shapley.

A binary search proved correct hid a bug for two decades

A one-line mistake in the textbook way to find the middle of a range sat in a published binary search for about two decades, and in the Java library’s copy of it for about nine years. It shows only with arrays of around a billion entries.

Binary search looks for a value in a sorted list by checking the middle, discarding half, and repeating. Jon Bentley’s Programming Pearls (1986) presented a version that, in Joshua Bloch’s account, Bentley proved correct and tested. The key line took the average of the lowest and highest positions still in play: mid = (low + high) / 2.

In 2006 Joshua Bloch of Google pointed out that this line fails when low + high is larger than the biggest 32-bit integer, 2,147,483,647. The sum wraps round to a negative number and the program crashes. Bloch had written the Java library version himself; it carried the same line. In his words it had been lying in wait for nine years or so, until it broke someone’s program. A bug report about it had been filed in May 2004 (JDK-5045582) and was fixed in Java 6. A proof that treats whole numbers as unlimited cannot catch this, because computer integers have a limit.

Search for the last item of an array of any length up to the 32-bit limit and watch where the sum goes wrong.

Joshua Bloch, “Extra, Extra – Read All About It: Nearly All Binary Searches and Mergesorts are Broken” (2 June 2006); the Java bug report JDK-5045582 (11 May 2004); Jon Bentley, Programming Pearls (1986), which Bloch says contains the proved and tested version, in its “Chapter 5”.

Public-key cryptography was invented in secret first

Strangers can agree a secret over an open line, and British government cryptographers worked out how to do it before the academics who got the credit.

Before the 1970s, sending a secret message meant first getting a key to the other person by some safe route. In November 1976 Whitfield Diffie and Martin Hellman published a method that lets two people who have never met agree on a shared secret while everyone listens. Secure web connections still rely on that idea. Ralph Merkle had independently worked on distributing keys over an insecure channel, and the paper acknowledges him; RSA was devised in 1977 and published in 1978.

In December 1997 the British government made public that its communications-security group at GCHQ had been there first. James Ellis conceived the idea in 1970; Clifford Cocks described, in a note of November 1973, what is now called RSA; and a note by Malcolm Williamson in January 1974 describes what the group’s own history calls essentially Diffie–Hellman. It stayed classified for more than twenty years.

The demo uses numbers of 19 digits, small enough to read. Real systems use larger ones: key exchange over whole numbers uses primes of 600 digits or more (a 2,048-bit prime has 617 digits), and the elliptic-curve version widely used today works over a prime of 77 digits, 2²⁵⁵ − 19.

The History of Non-Secret Encryption (CESG page, mirrored February 1998; Ellis’s paper was released in December 1997); the original notes by Ellis (January 1970), Cocks (20 November 1973) and Williamson (21 January 1974); Diffie and Hellman, “New Directions in Cryptography”, IEEE Transactions on Information Theory 22(6), 644–654 (November 1976); RFC 7919 (2,048-bit and larger groups) and RFC 7748 (the prime 2²⁵⁵ − 19).

A rule that fits in one byte can compute anything

Rule 110, in which every cell looks only at itself and its two neighbours, is proved able to run any computation that a computer can.

Picture a row of black and white cells. At each tick, every cell turns black or white depending on its own colour and its two neighbours’ colours. That is eight cases, so a rule is eight yes-or-no answers, which is one byte. Stephen Wolfram numbered the 256 possible rules; rule 110 is the one whose answers read 01101110 in binary.

Wolfram suspected in 1985 that rule 110 can carry out any computation. Matthew Cook proved it, in work published in 2004. The proof needs the row to start from a carefully prepared, repeating background, so the single cell in the demo is not computing anything useful. What matters is that nothing more than this byte is required.

Matthew Cook, “Universality in Elementary Cellular Automata”, Complex Systems 15(1), 1–40 (2004); the paper (the proof of Wolfram’s 1985 conjecture); Rule 110 (rule table, the repeating background).

The longest-running five-state machine was found around 1990 and proved the champion in 2024

Among five-state, two-symbol Turing machines that halt when started on a blank tape, the champion runs for exactly 47,176,870 steps; that no halting machine of that size runs longer was proved in July 2024.

A Turing machine is the simplest model of a computer: a tape, a head, and a short table of rules. Take every machine with five states and two symbols, ten rules in all (one for each state and symbol), start each on a blank tape, and throw out the ones that run forever. How long can the longest survivor run? That number is called BB(5). Heiner Marxen and Jürgen Buntrock found a machine that halts after 47,176,870 steps around 1990, and for more than three decades nobody could prove that no other would beat it, because first you must decide whether each of 88,664,064 machines whose behaviour was still undecided ever halts. An online collective, the bbchallenge project, finished that job on 2 July 2024, with a proof checked by computer.

For six states, nobody knows. A six-state machine is known that writes more than 2↑↑↑5 ones, a number beyond any notation but stacked arrows. And a machine with 745 states, built in 2023, halts if and only if the standard foundations of mathematics, ZFC set theory, contradict themselves; smaller ones have been claimed since, down to 230 states in October 2026. If ZFC is consistent, it cannot settle how long such a machine runs.

Run the champions here. The five-state machine takes a second or two.

bbchallenge.org: search for BB(5) completed 2 July 2024 (the champion, 88,664,064 undecided machines, the 1990 reference to Marxen and Buntrock); Busy beaver (S(3) = 21, S(4) = 107, S(5) = 47,176,870; Σ(3) = 6, Σ(4) = 13, Σ(5) = 4,098; the six-state lower bound; the proof formalised in Rocq; the 745-state ZFC machine and its later improvements); bbchallenge wiki, logical independence (state counts since 2016).

You can check a huge calculation without redoing it

To test whether a matrix product is right, multiply by a random vector instead: it takes a fraction of the work and a wrong answer slips through with probability at most one half per try.

Someone hands you three big grids of numbers, A, B and C, and says A × B = C. Checking by multiplying A and B yourself costs about n³ operations for grids of side n; the best known method still needs about n^2.37. In 1977 Rūsiņš Freivalds noticed that you can do something cheaper. Pick a random list r of zeros and ones. Compute B·r, then A·(B·r), and compare with C·r. Each of those is a grid times a list, about n² operations.

If the product is right the test always agrees. If it is wrong, a single test fails to notice with probability at most one half. Run it twenty times and the chance of being fooled is below one in a million.

Freivalds, “Probabilistic Machines Can Use Less Running Time” (1977), whose text could not be opened; the algorithm and its error bound as described in Freivalds’ algorithm.

A long computation can be squeezed into surprisingly little memory

In 2025 Ryan Williams proved that any computation that takes t steps on a multitape Turing machine can be redone using only about √(t log t) memory cells.

Time and memory are the two currencies of computing. A program that runs for a trillion steps can touch at most a trillion cells, but does it need them? For fifty years the best answer, from Hopcroft, Paul and Valiant in the 1970s, was roughly t divided by log t cells. Williams, of MIT, showed in 2025 that about √(t log t) suffice, building on a 2024 result by James Cook and Ian Mertz about evaluating trees with little memory.

The result is for multitape Turing machines, the standard model. It bounds memory, not time: the theorem does not say how long the memory-saving version takes. The abstract also claims a little progress on the old P versus PSPACE question, whether everything that can be solved in a modest amount of memory can also be solved in a modest amount of time.

Ryan Williams, “Simulating Time With Square-Root Space”, STOC 2025 (arXiv:2502.17779); Hopcroft, Paul and Valiant, “On Time Versus Space”, JACM 24(2), 332–337 (1977), Theorem 1; Cook and Mertz, “Tree Evaluation is in Space O(log n · log log n)”, STOC 2024 (ECCC report, November 2023).

A 40-year-old hash-table conjecture was overturned in 2025

In January 2025 Andrew Krapivin, Martín Farach-Colton and William Kuszmaul showed that a hash table can fill up faster than a 1985 conjecture of Andrew Yao allowed. Krapivin began the work as an undergraduate at Rutgers.

A hash table stores items in slots chosen by a hash function. When the slot is taken, the table probes another, then another, until it finds a free one. Call δ the fraction of slots still empty: at 99% full, δ = 0.01. In 1985 Yao proved that, in tables where each item takes the first free slot on its probe sequence (“greedy” tables) and nothing is moved afterwards, probing at random is best for the average cost. He conjectured that it is also nearly best for the worst-case expected cost, about 1/δ probes. At 99% full that is around 100 probes to place an item.

Krapivin, an undergraduate at Rutgers when he began and now a graduate student at Cambridge, was exploring a technique called tiny pointers when he designed a table that does not follow that rule. The 2025 paper has two results. The first is funnel hashing, a greedy table whose worst-case expected cost grows only as the square of the logarithm of 1/δ, written O(log²(1/δ)), together with a proof that no greedy table that never reorders items can do better. “Worst-case expected” means the expected cost of the unluckiest insertion, not a guarantee for every insertion; a guarantee that holds with high probability for all insertions needs an extra log log n term. The second is elastic hashing, which is not greedy: it sometimes probes beyond the first free slot. Its average cost per insertion stays constant however full the table gets, and its worst-case expected cost is O(log(1/δ)), the least any table without reordering can achieve.

See the old wall for yourself: fill a table by probing at random.

Farach-Colton, Krapivin and Kuszmaul, “Optimal Bounds for Open Addressing Without Reordering” (arXiv:2501.02305, January 2025), Theorems 1 and 2 and Sections 4 and 5; Quanta Magazine, 10 February 2025; Rutgers Honors College (Krapivin, class of 2024).

Where each claim comes from

Every fact ends with its references. Where the original paper or document could be opened, the reference is that paper; where only a reference work could be read, the reference says so. The checking ledger lists what was opened on 23 October 2026 for each figure and what could not be opened. Every demo runs on your device, with the code and parameters described under it.

What is estimated or still open

• Regular expressions. Cloudflare’s pattern was not the one in the demo, and its account names several causes besides the expression. The 60-second Perl figure dates from 2007 and a different pattern, and current engines may differ. The demo’s counts are for its own two matchers on one pattern.
• HyperLogLog. The 2% and 1.5 kB figures are the authors’ statement of typical accuracy, for 2,048 registers and a 32-bit hash; the standard error is 1.04/√m, which is 2.3% for m = 2,048. The paper’s registers are 5 bits and the demo’s are 6. The demo’s error is its own measurement on random items.
• Binary search. The two-decade and nine-year figures are Bloch’s account. A 2004 bug report shows a failure on a large array, but neither source records which program Bloch means. The book itself was not opened, and the chapter number is Bloch’s.
• Public-key history. The dates come from the original notes and from the CESG page, known from a mirror of February 1998. How far each note matches the later academic methods is the group’s own judgement.
• Rule 110. The universality proof relies on a specially prepared background and is long. Cook’s own paper is the reference.
• Busy beaver. The 2↑↑↑5 figure is a lower bound for six states, and records for six states may have moved since this page was written. The 745-state result depends on ZFC being consistent. The smaller machines after 2023 are claims listed on the bbchallenge wiki, not results this page has checked.
• Square-root space. The result is asymptotic and bounds memory only, not running time. It was accepted at STOC 2025; its consequences for open problems are not settled.
• Hash tables. The bounds are asymptotic and hide constants, so the demo’s probe counts cannot be set against log²(1/δ) at the same fullness. The Quanta article is the source for the “around 100 probes” figure. The demo reproduces only the old baseline.