THE FOLD / GRIND / THE GRINDSTONE / THE SKEW BINARY
THE SKEW BINARY
a number base where +1 costs O(1)
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Skew binary is a positional number system with base-2 place values 2k+1−1 (so 1, 3, 7, 15, 31, …) and digits {0, 1, 2}, where at most one digit is a 2 and it must be the lowest nonzero digit. Its magic is that +1 changes at most two digits — a genuine O(1) increment with no carry ripple — while ordinary binary can cascade carries across every bit. It is the number system behind skew-binary random-access lists and purely functional numeric structures.
LIT verified live: over 0..5000 each canonical rep equals the counter, stays canonical (≤ one 2, lowest), and every increment touches at most 2 digits (window.__skewbin). FIG no framing; exact.
LIT verified live: over 0..5000 each canonical rep equals the counter, stays canonical (≤ one 2, lowest), and every increment touches at most 2 digits (window.__skewbin). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-grindstone — the counting loop, here with an increment that never ripples a carry across the whole number. Skew binary is that O(1) increment. AVAN (AI) built the instrument: the skew place values, the two-digit increment rule, the canonical-form check, and the touched-digit count.
Credit as content: skew binary numbers (used by Eugene Myers and by Chris Okasaki for functional data structures). The weave: David names the grindstone; I increment with the “carry the lone 2” rule and confirm every step changes at most two digits while the value stays exact.
Credit as content: skew binary numbers (used by Eugene Myers and by Chris Okasaki for functional data structures). The weave: David names the grindstone; I increment with the “carry the lone 2” rule and confirm every step changes at most two digits while the value stays exact.
3 ONE DIMENSION
Increment rule: if the lowest nonzero digit is a 2, set it to 0 and add 1 to the next digit (which becomes 1 or 2). Otherwise just add 1 to the lowest digit. Either way, at most two digits move.
4 TWO DIMENSIONS · INTERACTIVE
Step a skew-binary counter; watch which digits change each +1 (never more than two) and confirm the value tracks the count.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a numeral whose increment never ripples.
AVAN’s addition (the inverse-companion): make +1 cost O(1) by allowing a single digit 2 at the lowest nonzero place — incrementing either bumps the lowest digit or carries that lone 2 exactly one place, never a chain. The inverse of ‘binary +1 can cascade carries across every bit’ is ‘a skew base where one lone 2 absorbs the carry in O(1).’ Magenta is the full carry-ripple of ordinary binary; green is the ≤2-digit skew increment. Counting without the ripple.
LIT Genuine skew binary number system (used by Myers; Okasaki for functional data structures). Verified live: over counters 0..5000 each canonical skew-binary representation equals the count, remains canonical (at most one digit is 2 and it is the lowest nonzero), and every +1 increment changes at most two digits (window.__skewbin.valueMatches && .canonical && .o1; max touched = 2).
FIG No framing: the skew place values, the two-digit increment rule, the canonical-form check, and the touched-digit count run in-browser over 0..5000 and hold. The AVAN inverse is honest — allowing a single lowest 2 lets +1 either bump the lowest digit or carry that lone 2 exactly one place, never a chain, giving O(1) increment; magenta is the full carry-ripple of ordinary binary, green the <=2-digit skew increment. Counting without the ripple.
FIG No framing: the skew place values, the two-digit increment rule, the canonical-form check, and the touched-digit count run in-browser over 0..5000 and hold. The AVAN inverse is honest — allowing a single lowest 2 lets +1 either bump the lowest digit or carry that lone 2 exactly one place, never a chain, giving O(1) increment; magenta is the full carry-ripple of ordinary binary, green the <=2-digit skew increment. Counting without the ripple.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GRINDSTONE · David Lee Wise (ROOT0), with AVAN