Length and cubic charge bounds for the binary gcd
ProvedAFT.BinaryArithmetic.gcd_resourcesinfo-loss-lar-native-5c3becbnative-binary-arithmeticstoc-2027
For two supplied natural-number bit strings of lengths and , the native Euclidean gcd computation returns a bit string of length at most and satisfies
The bounds include normalization of redundant high zero bits in the inputs.
Here denotes the operation charge recorded by the native counted program. The bound is an accounting lemma for the constructive sampler, not a separate certificate in a Turing-machine model.
Preamble
import Definitions.Def_InfoLossLAR_Native_AFT_BinaryEuclid import Mathlib /-! A binary implementation of Euclid with an explicit linear-in-bitlength iteration bound. Each iteration performs two long divisions, which halves the second nonzero operand. -/ namespace AFT.BinaryArithmetic end AFT.BinaryArithmetic section AFT section BinaryArithmetic open AFT open AFT.BinaryArithmetic
Formal statement
theorem AFT.BinaryArithmetic.gcd_resources (as bs : List Bool) :
(_root_.AFT.BinaryArithmetic.gcd as bs).digits.length ≤ max as.length bs.length ∧
(_root_.AFT.BinaryArithmetic.gcd as bs).work ≤ 1000*(as.length+bs.length+1)^3 := by sorrySource
Local manuscript repository commit 5c3becb254daaa8738368b474349766c1769c2a0; lean/AFT/BinaryEuclid.lean, lines 162–177; exact native theorem type and complete proof.