THE FOLD / GRIND / THE CRON JOB / THE NON-RESTORING DIVISION
THE NON-RESTORING DIVISION
do not undo the bad step, correct it later
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Long division in hardware subtracts, and when the result goes negative it has to put it back. Non-restoring division does not put it back — it leaves the remainder negative and adds on the next step instead of subtracting. Same answer, one fewer operation every time the subtraction was too big.
LIT verified live. Across five divisions it gives the correct quotient and remainder every time and agrees with the restoring version exactly, while using 12 operations against 18 to 23 — 41 steps saved across the five. Exhaustively correct on 4,096 cases, and the remainder needs at most one final correction.
LIT verified live. Across five divisions it gives the correct quotient and remainder every time and agrees with the restoring version exactly, while using 12 operations against 18 to 23 — 41 steps saved across the five. Exhaustively correct on 4,096 cases, and the remainder needs at most one final correction.
2 HOW IT WAS WEAVED · AI + HUMAN
Non-restoring division is the classical hardware algorithm, and the insight is that restoring wastes work: adding the divisor back and then subtracting it again on the next cycle is the same as simply adding it once, shifted. The wasted add-then-subtract cancels.
AVAN (AI) counted the operations rather than describing the saving, because “fewer operations” is exactly the sort of claim that turns out to be a wash. Restoring costs one op per bit plus one more per negative step; non-restoring costs exactly one per bit, always — 12 for a 12-bit dividend regardless of the numbers. The saving is not an average, it is the elimination of a data-dependent branch, which on hardware matters more than the count.
AVAN (AI) counted the operations rather than describing the saving, because “fewer operations” is exactly the sort of claim that turns out to be a wash. Restoring costs one op per bit plus one more per negative step; non-restoring costs exactly one per bit, always — 12 for a 12-bit dividend regardless of the numbers. The saving is not an average, it is the elimination of a data-dependent branch, which on hardware matters more than the count.
3 ONE DIMENSION
Five divisions, two algorithms, one answer.
4 TWO DIMENSIONS · INTERACTIVE
Step through, and watch the remainder go negative and stay there.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a path that crosses below zero and keeps going.
AVAN’s addition (the inverse-companion): the forward reading is “do not undo the bad step.” The inverse is that the intermediate state is now meaningless. A restoring divider always holds a genuine partial remainder that could be inspected, interrupted or resumed; a non-restoring one spends most of its cycles holding a negative number that is not the remainder of anything. Read backwards, the speed comes from allowing the machine to be temporarily wrong in a controlled way, and everything that wanted to look at the register mid-flight has lost the ability to.
LIT across five divisions it gives the correct quotient and remainder every time and agrees with the restoring version exactly, while using 12 operations against 18 to 23 - 41 steps saved across the five; exhaustively correct on 4,096 cases, and the remainder needs at most one final correction
FIG Non-restoring division is the classical hardware algorithm, and the insight is that restoring wastes work: adding the divisor back and then subtracting it again on the next cycle is the same as simply adding it once, shifted, so the wasted add-then-subtract cancels. AVAN counted the operations rather than describing the saving, because 'fewer operations' is exactly the sort of claim that turns out to be a wash. Restoring costs one op per bit plus one more per negative step; non-restoring costs exactly one per bit, always - 12 for a 12-bit dividend regardless of the numbers. The saving is the elimination of a data-dependent branch, which on hardware matters more than the count.
FIG Non-restoring division is the classical hardware algorithm, and the insight is that restoring wastes work: adding the divisor back and then subtracting it again on the next cycle is the same as simply adding it once, shifted, so the wasted add-then-subtract cancels. AVAN counted the operations rather than describing the saving, because 'fewer operations' is exactly the sort of claim that turns out to be a wash. Restoring costs one op per bit plus one more per negative step; non-restoring costs exactly one per bit, always - 12 for a 12-bit dividend regardless of the numbers. The saving is the elimination of a data-dependent branch, which on hardware matters more than the count.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CRON JOB · David Lee Wise (ROOT0), with AVAN