Uniform three-block-bit precision for every convolution coefficient and carry
ProvedIntMul.CarryProduct.logarithmic_coefficient_precisionalgorithmsfixed-tape-routinginteger-multiplicationturing-machines
Let be binary operand words, and , where . Split the words into base- digits and let be their full padded convolution coefficient array. Its minimal sufficient coefficient precision is
where are the respective block counts. Then
and every coefficient-plus-carry sum in the low-to-high normalization pass satisfies
for every coefficient of the array and every carry position . This gives a uniform sufficient -bit precision using only a logarithmic block-size parameter, removing the need to compute an exact block-count-dependent coefficient precision. Empty and leading-zero operand words are included.
Preamble
import Definitions.Def_IntMul_CarryProduct import Mathlib.Tactic open IntMul IntMul.CarryProduct
Formal statement
theorem IntMul.CarryProduct.logarithmic_coefficient_precision (B : ℕ) (x y : List Bool)
(hb : lg (x.length+y.length)≤B) :
coefficientWidth B x y≤3*B ∧
∀ a ∈ CarryNormalization.coefficients B x y, ∀ j : ℕ,
a+CarryNormalization.carryAt (2^B) (CarryNormalization.coefficients B x y) 0 j<2^(3*B) := by sorrySource
Original logarithmic coefficient/carry precision bound. Uses exact accepted convolution and carry bounds, with owned block-count and power inequalities. Written by Codex.