Computing

13 breaks

The ideas inside the machines we use all day.

AllBiologyComputingEarth & SpaceEconomicsEngineeringFood ScienceHistoryLanguageMathsMindMusic & SoundPhysics
Why sorting gets slow so fast: bubble sort versus merge sort and n log n Two sorting methods can both be perfectly correct and still differ by a factor of 25,000 on a big list. Race bubble sort against merge sort on the same… Computing3 min read How your phone finds the quickest route: Dijkstra's shortest-path algorithm Your phone finds the fastest route across millions of roads without trying them all. The trick is a rule Edsger Dijkstra devised in 1956: always finish the… Computing3 min read Why eight yes/no answers can draw a fractal, make noise or compute: elementary cellular automata Take a row of lit and dark squares and repeat one tiny rule to make the next row: look at a square and its two neighbours, then decide if it is lit. There are… Computing3 min read Why one flipped bit can be found and fixed: Hamming's error-correcting code A single flipped bit can turn a good file into garbage, yet a machine can find and repair it without ever seeing the original. In 1950 Richard Hamming, tired… Computing4 min read Why swapping cards at random is not a fair shuffle: Fisher–Yates and the 27 paths Shuffling three cards by swapping each one with a random card from the whole row looks fair, but it is not. It makes 3 × 3 × 3 = 27 equally likely paths for… Computing4 min read How to find one name among a billion in 30 looks: binary search Pick a number from 1 to 1,000,000 and you can find it in at most 20 yes-or-no questions. The trick is binary search: look in the middle of a sorted list, throw… Computing4 min read Why common letters get short codes in a ZIP file: Huffman coding ASCII spends 8 bits on every letter, whether it is a common e or a rare z. In 1951 a graduate student, David Huffman, found a way to give frequent symbols… Computing4 min read How a computer finds one flipped bit and fixes it: Hamming's code A bit can flip in memory, on a disk or in a radio signal, and nothing tells you which one went wrong. In 1950 Richard Hamming published a code that finds the… Computing4 min read Why 0.1 + 0.2 isn't 0.3: flip the 64 bits a computer uses for decimals Type 0.1 + 0.2 into almost any programming language and you get 0.30000000000000004. Nothing is broken. Computers count in powers of two, and a tenth is an… Computing3 min read How a Bloom filter says "definitely not" using just a few bits How can a computer check whether a word is on a huge list using only a few bits per entry? A Bloom filter flips a handful of switches for every word you add… Computing3 min read How one extra digit on your bank card catches your typos The last digit of your bank card number isn't part of your account. It's a check digit, computed from the other fifteen by a recipe an IBM engineer patented in… Computing5 min read How computers fake grey using only black and white dots Old Mac screens, cheap printers and some modern games can only show two colours: black and white. Yet they still draw soft shadows and smooth skies. The trick… Computing5 min read