Cubic bit-operation bound for binary rational reduction
ProvedAFT.BinaryArithmetic.reduce_workinfo-loss-lar-native-5c3becbnative-binary-arithmeticstoc-2027
For every sign bit and binary numerator and denominator strings with a positive denominator value, the work charged by the binary rational reduction algorithm is at most 2000 times the cube of the sum of the two input lengths plus one. The bound includes the algorithm’s normalization and gcd-based reduction operations and is uniform over the represented integers.
Preamble
import Definitions.Def_InfoLossLAR_Native_AFT_BinaryRationalData import Mathlib section /-! Canonical rational data stored as Boolean lists. Proof fields are erased; semantic reduced height controls the actual operand representation length. -/ namespace AFT.BinaryArithmetic namespace RationalBits end RationalBits set_option maxRecDepth 8192
Formal statement
theorem _root_.AFT.BinaryArithmetic.reduce_work (negative : Bool) (num den : List Bool) (hden : 0 < _root_.AFT.BinaryArithmetic.value den) :
(_root_.AFT.BinaryArithmetic.reduce negative num den hden).work ≤ 2000*(num.length+den.length+1)^3 := by sorrySource
Local manuscript repository commit 5c3becb254daaa8738368b474349766c1769c2a0; lean/AFT/BinaryRationalData.lean, lines 94–107; exact native theorem type and complete proof.