Framed checked multiword arithmetic #
The arithmetic programs reserve registers zero through three for workspace. Their frame preserves memory and every other register outside the destination list, including registers that are not source operands. Register lists are fixed when constructing the code.
Main definitions #
Arithmetic.Frame: preservation of all digit registers outside a destination list.Difference.truncatingProgram: subtraction with a branch that clears an underflowed result.
Main results #
Schoolbook.preserves_program: the syntactic register frame for schoolbook multiplication.Schoolbook.exec_framed: full multiplication with the digit-register frame.Schoolbook.exec_eighteen_framed: arbitrary layouts of eighteen-digit operands and a thirty-six-digit product, in exactly 2465 instructions.Difference.exec_framed: nonnegative subtraction with the digit-register frame.Difference.exec_eighteen_framed: eighteen-digit nonnegative subtraction in exactly 112 instructions.Difference.exec_eighteen_truncating: general eighteen-digit natural-number subtraction in at most 132 instructions, with the full digit-register frame.
References #
A multiplication cell writes only its output digit and arithmetic workspace.
Every digit register outside a row's destinations is syntactically preserved.
Every digit register outside all row destinations is syntactically preserved.
Clearing an accumulator preserves every digit register outside it.
Radix initialization writes only the four reserved workspace registers.
Multiplication writes only destination digits and the four reserved workspace registers.
Clear a digit list, with its full frame and exact cost.
Full multiplication preserves every non-destination digit register. The destination lists and operands have arbitrary fixed lengths and arbitrary disjoint register layouts.
An arbitrary eighteen-digit layout computes all thirty-six product digits in 2465 instructions while preserving every other digit register and memory.
Subtraction without a sign hypothesis, retaining the exact final borrow equation. This is the arithmetic core used before clearing a negative result.
Subtraction followed by clearing its output exactly when the final borrow is one. The second alternative is a self-copy, so both branches are executable for empty lists.
Instances For
Truncating subtraction writes only its destinations and reserved workspace.
General natural-number subtraction, including underflow. The result is Nat.sub,
with bounded digits and preservation of every non-destination digit register and memory.
The clear branch costs ds.length + 2; the other branch costs three instructions.
General eighteen-digit natural-number subtraction takes at most 132 instructions.
Nonnegative subtraction preserves every digit register outside its in-place output.
Eighteen-digit nonnegative subtraction has an exact 112-instruction execution and preserves memory and every digit register outside the in-place destination list.