THE FOLD / SPAWN / NULL ISLAND / THE DOUBLE DABBLE
THE DOUBLE DABBLE
binary to decimal with no division at all
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Converting binary to decimal without a single division. Shift the number left into a register of decimal digits, and before each shift add 3 to any digit that has reached 5 or more. Shifts, comparisons and additions — nothing else. The magic constant is not magic: it is the pre-correction for doubling.
LIT verified live and exhaustively over all 4,096 twelve-bit values, every one converting exactly. And the add-3 is checked digit by digit: a digit of 5 doubles to 10, which is not a legal decimal digit, but (5+3)×2 = 16 — carry 1, digit 0, which is precisely right. The same holds for 6, 7, 8 and 9.
LIT verified live and exhaustively over all 4,096 twelve-bit values, every one converting exactly. And the add-3 is checked digit by digit: a digit of 5 doubles to 10, which is not a legal decimal digit, but (5+3)×2 = 16 — carry 1, digit 0, which is precisely right. The same holds for 6, 7, 8 and 9.
2 HOW IT WAS WEAVED · AI + HUMAN
The double dabble, also called shift-and-add-3, is the standard way to drive a seven-segment display from a binary counter in hardware with no divider. It appears wherever a divide instruction is unavailable or unaffordable, which historically was most places.
AVAN (AI) verified why the 3 works rather than only that it does, because the constant looks arbitrary and is not. A decimal digit d at or above 5 would double past 9. Adding 3 first gives 2(d+3) = 2d+6, and since a decimal carry is worth 16 in the packed representation but only 10 in value, the +6 is exactly the difference. The correction is not a fudge tuned to work — it is 16 minus 10, halved.
AVAN (AI) verified why the 3 works rather than only that it does, because the constant looks arbitrary and is not. A decimal digit d at or above 5 would double past 9. Adding 3 first gives 2(d+3) = 2d+6, and since a decimal carry is worth 16 in the packed representation but only 10 in value, the +6 is exactly the difference. The correction is not a fudge tuned to work — it is 16 minus 10, halved.
3 ONE DIMENSION
Why three, digit by digit.
4 TWO DIMENSIONS · INTERACTIVE
Step the conversion one shift at a time.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: bits marching out, digits filling up.
AVAN’s addition (the inverse-companion): the forward reading is “no divider needed.” The inverse is that the divider was replaced by n iterations of a wide parallel comparison. Every bit of input costs a pass over every decimal digit, each with its own compare-and-add-3 — so the work did not vanish, it turned from one slow sequential instruction into a great deal of cheap simultaneous hardware. Read backwards, this is the standard trade of the whole discipline: area for latency, and it is only a win where you have the silicon and cannot afford the wait.
LIT exhaustively correct over all 4,096 twelve-bit values, every one converting exactly; and the add-3 is checked digit by digit - a digit of 5 doubles to 10 which is not a legal decimal digit, but (5+3) times 2 is 16, carry 1 and digit 0, which is precisely right, and the same holds for 6, 7, 8 and 9
FIG The double dabble, also called shift-and-add-3, is the standard way to drive a seven-segment display from a binary counter in hardware with no divider. It appears wherever a divide instruction is unavailable or unaffordable, which historically was most places. AVAN verified WHY the 3 works rather than only that it does, because the constant looks arbitrary and is not: a decimal digit at or above 5 would double past 9, and adding 3 first gives 2(d+3) = 2d+6, where a decimal carry is worth 16 in the packed representation but only 10 in value - so the correction is 16 minus 10, halved.
FIG The double dabble, also called shift-and-add-3, is the standard way to drive a seven-segment display from a binary counter in hardware with no divider. It appears wherever a divide instruction is unavailable or unaffordable, which historically was most places. AVAN verified WHY the 3 works rather than only that it does, because the constant looks arbitrary and is not: a decimal digit at or above 5 would double past 9, and adding 3 first gives 2(d+3) = 2d+6, where a decimal carry is worth 16 in the packed representation but only 10 in value - so the correction is 16 minus 10, halved.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of NULL ISLAND · David Lee Wise (ROOT0), with AVAN