Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Addition of signed binary integers

Definition
InfoLossLAR_Native_AFT_BinarySignedAddition

by BoomShaKaLaaaKa · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

info-loss-lar-native-5c3becbnative-binary-arithmeticstoc-2027

A signed digit pair (s,a)(s,a)(s,a) represents the integer (−1)sv(a)(-1)^s v(a)(−1)sv(a). The signed-addition routine returns a sign, magnitude digits, and a native charge, with the exact specification

decode⁡(signedAdd⁡(s,a,t,b))=(−1)sv(a)+(−1)tv(b).\operatorname{decode}(\operatorname{signedAdd}(s,a,t,b))=(-1)^s v(a)+(-1)^t v(b).decode(signedAdd(s,a,t,b))=(−1)sv(a)+(−1)tv(b).

It combines magnitude addition and borrow subtraction to handle both signs of each operand.

Definition code
import Definitions.Def_InfoLossLAR_Native_AFT_BinaryRationalData
import Mathlib


/-! Signed-magnitude addition, implemented by the Boolean ripple algorithms. -/
namespace AFT.BinaryArithmetic

structure SignedResult where
  negative : Bool
  digits : List Bool
  work : ℕ

def signedAdd (firstSign secondSign : Bool) (first second : List Bool) : SignedResult :=
  if firstSign==secondSign then
    let sum := add false first second
    ⟨firstSign,sum.digits,sum.work+3⟩
  else
    let diff := subtract false first second
    if diff.borrow then
      let reverse := subtract false second first
      ⟨secondSign,reverse.digits,diff.work+reverse.work+4⟩
    else ⟨firstSign,diff.digits,diff.work+4⟩

theorem signedAdd_value (firstSign secondSign : Bool) (first second : List Bool) :
    signedValue (signedAdd firstSign secondSign first second).negative
      (signedAdd firstSign secondSign first second).digits =
      signedValue firstSign first+signedValue secondSign second := by
  have hadd := add_value first second false
  simp only [Bool.toNat_false,Nat.add_zero] at hadd
  by_cases he : firstSign=secondSign
  · subst secondSign
    simp only [signedAdd,beq_self_eq_true,ite_true,signedValue,hadd]
    cases firstSign <;> simp
    omega
  · have hbeq : (firstSign==secondSign)=false := by simpa using he
    simp only [signedAdd,hbeq,Bool.false_eq_true,ite_false]
    cases hb : (subtract false first second).borrow with
    | true =>
      have hlt := (subtract_borrow first second).mp hb
      have hv := subtract_value second first hlt.le
      simp only [ite_true,signedValue,hv]
      cases firstSign <;> cases secondSign <;> simp_all <;> omega
    | false =>
      have hle : value second ≤ value first := by
        have hh := (subtract_borrow first second)
        simp only [hb,Bool.false_eq_true,false_iff] at hh
        omega
      have hv := subtract_value first second hle
      simp only [Bool.false_eq_true,ite_false,signedValue,hv]
      cases firstSign <;> cases secondSign <;> simp_all <;> omega





end AFT.BinaryArithmetic
Source
Local manuscript repository commit 5c3becb254daaa8738368b474349766c1769c2a0; lean/AFT/BinarySignedAddition.lean; migrated native SHA256 382d7ef5725daa96617c1d348f867a1a0df72ea117ea5384eb555385388b5898; retained source units selected by Lean oracle.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me