Hamming's Geometrische Intuïtie
Hamming zag geometrie overal
Het hoofdstuk 9 van Hamming begint met een waarschuwing: geometrische intuïtie stort in hoge dimensies in. In 3D vult een bol het meeste van zijn omsluitende kubus. In 10D neemt de bol minder dan 0,2% van het volume van de kubus in. In 100D loopt de breuk naar nul. Volume concentreert zich nabij het oppervlak. Punten clusteren bij hoeken, niet in het centrum.
Zijn foutcorrigerende codes exploiteerden dit direct. Hamming-codes pakken codewoorden in n-dimensionale binaire ruimte zodat elk codewoord wordt omgeven door een bol van corrigeerbare fouten. De geometrie bepaalt hoeveel fouten je kunt corrigeren. Bolpakking in n-dimensionale ruimte is een wiskundig probleem met echte inzetten: pak de bollen dichter in elkaar, corrigeer meer fouten.
Deze geometrische faalwijze is ook van toepassing op algoritmische complexiteit. Bij kleine N lijken O(N²) en O(N) op een grafiek bijna identiek. Het verschil tussen hen lijkt beheersbaar. Bij grote N explodeert het verschil — precies zoals het volume van de bol in hoge dimensies ineenstort. Wat op kleine schaal tractabel voelt, wordt onmogelijk op grote schaal.
De vorm van elke complexiteitsklasse
Complexiteit tekenen
Elke complexiteitsklasse heeft een geometrische vorm:
- O(1): een horizontale lijn. Dezelfde kosten ongeacht N. Geen helling.
- O(log N): een zachte opwaartse curve die afvlakt. Verdubbelt elke keer dat N wordt gekwadrateerd. Groeit proportioneel aan het aantal cijfers in N.
- O(N): een diagonale lijn door de oorsprong. Kosten groeien proportioneel aan N.
- O(N log N): iets steiler diagonaal. Een lijn die zeer zacht omhoog buigt.
- O(N²): een parabool. Bij N=100: 10.000 bewerkingen. Bij N=1.000: 1.000.000 bewerkingen.
Het kritieke inzicht: de verhouding tussen twee complexiteitsklassen is zelf een functie van N. Bij N=10 kost O(N²) 10× meer dan O(N). Bij N=1.000 kost O(N²) 1.000× meer. Bij N=1.000.000 kost het 1.000.000× meer. Het verschil groeit niet alleen — het groeit in het tempo van N zelf.
Dit is het geometrische argument voor waarom MOAD-0001-patches belangrijk zijn. Een afhankelijkheidoplosser verplaatsen van O(N²) naar O(N) is geen constante versnelling. Bij N=50.000 pakketten is het een 50.000× versnelling. Bij N=100.000 is het een 100.000× versnelling. De waarde van de patch groeit met de probleemgrootte.
De groeiende kloof
O(N²) en O(N) produceren beide juiste resultaten.
Bij N=10: O(N²) kost 100 bewerkingen, O(N) kost 10 bewerkingen. Verhouding: 10×.
Bij N=1.000: O(N²) kost 1.000.000 bewerkingen, O(N) kost 1.000 bewerkingen.
Grafen als Geometrie
De Gerichte Acyclische Graaf
Een DAG (directed acyclic graph) is een geometrische structuur: knooppunten verbonden door gerichte randen zonder cycli. Softwareafhankelijkheidsgrafen, bouwpijplijnen en gegevensstroomarchitecturen vormen allemaal DAGs.
Elk knooppunt draagt geometrische eigenschappen mee gemeten door het tellen van zijn randen:
- In-graad: aantal randen dat aankomt bij het knooppunt. Hoge in-graad betekent dat veel upstream-afhankelijkheden dit knooppunt voeden.
- Out-graad: aantal randen dat het knooppunt verlaat. Hoge out-graad betekent dat veel downstream-consumenten afhankelijk zijn van dit knooppunt.
- Betweenness: in-graad + out-graad. Meet hoeveel paden door dit knooppunt lopen. Een knooppunt met hoge betweenness zit op een kruispunt in de graaf.
- Surge-score: versnelling × in-graad. Meet hoeveel werk downstream stroomt wanneer dit knelpunt wordt opgeheven.
Het fabrieksmodel geeft deze geometrische eigenschappen fysieke betekenis:
- Hoge betweenness + hoge surge-score = workaholic-knooppunt. Verwijder dit knelpunt zonder downstream in te richten = instorting.
- Hoge out-graad + lage surge-score = gulzige knooppunt. Verbruikt zonder voort te brengen. De machine die vergeet te stoppen.
Surge & Betweenness in Praktijk
Een DAG Lezen
Beschouw een keten van 5 knooppunten: A → B → C → D → E, plus een extra rand B → D.
- A: in-graad 0, out-graad 1, betweenness 1. Bronknooppunt. Niets voelt het. Één consument.
- B: in-graad 1 (van A), out-graad 2 (naar C en naar D), betweenness 3. Voelt twee downstream-knooppunten — een uitvoeringspunt.
- C: in-graad 1 (van B), out-graad 1 (naar D), betweenness 2. Een doorvoerknooppunt.
- D: in-graad 2 (van B en van C), out-graad 1 (naar E), betweenness 3. Ontvangt van twee paden.
- E: in-graad 1 (van D), out-graad 0, betweenness 1. Sinkknooppunt.
B en D delen de hoogste betweenness (3). B is de uitsplitsing: het voelt twee knooppunten. D is het convergentiepunt: het ontvangt van twee paden. Na een MOAD-0001-patch bij C, ontvangt D surge van zowel het B→D-pad als het C→D-pad tegelijkertijd.
Knooppuntmaten Berekenen
Een afhankelijkheidgraaf: A → B → C → D → E (een keten), plus een extra rand B → D.
Knooppunt C heeft een gemeten versnelling van 50× na een MOAD-0001-patch.
Het Flatland-Defect
MOAD-0007: Ruimtelijke Data Bevraagd als Platte Lijst
MOAD-0007 (het Flatland-Defect): ruimtelijke data bevraagd als platte lijst negeert de geometrische structuur van de data. Elke query controleert alle N objecten. O(N) per query. Bij M queries: O(M × N). Op schaal: catastrofaal.
Een realtime raycaster controleert elk object in een scène tegen elke ray. Bij 60 frames per seconde, met 100 rays per frame en 10.000 scèneobjecten: 60.000.000 kruisingsvergelijkingen per seconde. Allemaal vermijdbaar.
Het geometrische inzicht: ruimte heeft structuur. Objecten clusteren. Een ray die de linkerhelft van de scène mist, mist elk object in de linkerhelft. Een platte lijst kan dit niet benutten — hij controleert elk object ongeacht ruimtelijke locatie. Een ruimtelijke datastructuur kan.
De BVH: Binair Zoeken in 3D
Hoe een BVH Werkt
Een BVH (Bounding Volume Hierarchy) decomponeert 3D-ruimte in een boom van geneste begrenzingsvakken. Elk intern knooppunt houdt een begrenzingsvak vast dat alle geometrie van zijn kinderen bevat.
Een raycast-query:
1. Test het wortelbegrenzingsvak. Als de ray mist, sluit af — de hele scène is weggesnoeid.
2. Als de ray raakt, herhaal in kinderen. Test elk kind's begrenzingsvak.
3. Voor elk kind dat mist: verwijder die substructuur. Voor elk kind dat raakt: herhaal dieper.
4. Bij bladknooppunten: test de werkelijke geometrie.
Geometrie van wegsnoeien: op elk niveau worden niet-snijdende vertakkingen geëlimineerd. Met een gebalanceerde BVH van diepte d: 2^d bladknooppunten bestaan, maar een enkele ray heeft hooguit O(log N) vergelijkingen nodig voor het weggesnoeid pad.
Dit is hetzelfde geometrische argument als binair zoeken: elke vergelijking halveert de resterende zoekruimte. Binair zoeken halveert een gesorteerde array. Een BVH halveert de zichtbare 3D-ruimte. De structuur is identiek — een gebalanceerde binaire boom met wegsnoeien op elk knooppunt.
Een MOAD-0007-fix: vervang de platte lijst door een BVH. Verplaats van O(N) per query naar O(log N) per query. Bij N=1.024 objecten, O(log₂ 1.024) = 10 vergelijkingen in plaats van 1.024.
BVH-Versnelling Berekenen
Een gamescène heeft 1.024 objecten.
Zonder BVH: een raycast controleert alle 1.024 objecten.
Met een gebalanceerde BVH van diepte 10 (2^10 = 1.024 bladeren): een raycast doorloopt hooguit 10 niveaus, met 2 kindvergelijkingen per niveau.