· 6 min read
Splitmix32: thirteen lines of beautiful randomness
I went looking for a seeded PRNG in TypeScript and found splitmix32, a 32-bit pseudorandom number generator so elegant it made me want to understand every single bit.
Writing · Tagged
Algorithms
6 articles
· 9 min read · Part 2 of 2
Why jump point search lost to a lookup table
The route optimizer benchmark track: JPS was a reasonable pathfinding choice, but precomputed Dijkstra tables, SlotId compression, and an exact ILP referee fit the warehouse better.
· 9 min read · Part 4 of 4
Stochastic greedy: scaling submodular maximization to massive datasets
Stochastic Greedy replaces greedy's full scan with random subsampling, reducing runtime from O(nk) to O(n ln(1/ε)) while losing only an additive ε in the approximation guarantee. This post covers the algorithm, its proof, and practical guidance.
· 6 min read · Part 3 of 4
Lazy greedy: speeding up submodular maximization for free
Lazy Greedy keeps the greedy algorithm's (1 - 1/e) guarantee while skipping most of its oracle calls. Submodularity makes stale marginal gains sound upper bounds, so a max-heap of them is enough to certify each pick.
· 11 min read · Part 2 of 4
The greedy algorithm for submodular maximization
The greedy algorithm achieves a (1 - 1/e) approximation for monotone submodular maximization, provably the best any efficient algorithm can do. This post covers the algorithm, its proof, and when greedy fails.
· 15 min read · Part 1 of 4
An introduction to submodularity
An introduction to submodular functions, the mathematical framework behind diminishing returns: set functions, marginal gains, and applications from sensor placement to influence maximization.
hidden · · 6 min read
Ten raffle winners, one shrinking bowl
Choosing ten distinct winners is not one random choice repeated ten times. Every name removed from the bowl changes the next draw.
hidden · · 5 min read
I found a probability bug in my old TSP solver
The code cited the right weighted-sampling paper and kept the wrong end of its priority queue. The mismatch is more useful than a clean success story.
hidden · · 8 min read
How wrong can a random sample be?
With 1,000 expected hits, a 20% miss has probability at most 0.00000324. Concentration turns 'probably close' into a number.
hidden · · 7 min read
A fair sample in 100 slots, forever
After 10,000 events, every event has a 1% chance of occupying a 100-slot buffer. After a billion, the buffer is still fair and still holds 100.
hidden · · 8 min read
The 1.25-byte question: have I seen this key?
A Bloom filter answers set membership in about 1.25 bytes per key. HyperLogLog, Count-Min, and MinHash make related trades for counting, frequency, and similarity.
hidden · · 7 min read
A one-line sampler can quietly double the odds
`Math.floor` and `Math.round` differ by one word. For four choices, one is uniform. The other makes the middle values twice as likely.
hidden · · 6 min read
When randomness should take sides
Weights of 1, 2, and 7 turn into odds of 10%, 20%, and 70%. Chance remains, but the code finally admits that the options differ.
hidden · · 5 min read
`ORDER BY random()` still has to see every row
Ask PostgreSQL for 100 random rows and it may still score every candidate. `LIMIT 100` shrinks the result, not the work needed to choose it.
hidden · · 8 min read
When luck is part of the proof
Karger's min-cut algorithm succeeds on one run with probability at least 2/(n(n-1)), and the same argument proves a graph has at most n(n-1)/2 minimum cuts. Freivalds' check and Miller-Rabin trade a proof for the same kind of bounded failure probability.