· 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 3
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 · · 4 min read
The Raffle Changes After Every Winner
Choosing ten distinct winners is not ten independent random choices. Every draw changes the distribution faced by the next one.
hidden · · 4 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 · · 5 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 · · 4 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 · · 4 min read
Small Data Structures That Lie Just Enough
A Bloom filter can rule out missing keys without storing the keys. Its false positives are not a defect; they are the price of the memory saved.
hidden · · 4 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 · · 4 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
The Hidden Full-Table Scan in `ORDER BY random()`
Ask PostgreSQL for 100 random rows and it may still evaluate a random key for every candidate. `LIMIT 100` does not make the other rows disappear.
hidden · · 5 min read
When Luck Is Part of the Proof
Karger's min-cut algorithm can fail on one run and still be exact when it succeeds. Repetition turns that luck into a bound.