import Mathlib /-! # Divide Two Integers Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator. The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2. Return the quotient after dividing dividend by divisor. Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, if the quotient is strictly greater than 2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than -2^31, then return -2^31. ## Constraints - -2^31 <= dividend, divisor <= 2^31 - 1 - divisor != 0 ## Provided examples - `dividend = 10, divisor = 3` → `3` - `dividend = 7, divisor = -3` → `-2` - `dividend = 1, divisor = 1` → `1` ## Synthesized negative examples - invalid input: `dividend = -2147483649, divisor = 1` ([structural] a predicate that admits -2^31 <= dividend, divisor <= 2^31 - 1. catches a predicate that forgot the lower bound on dividend) - invalid input: `dividend = 1, divisor = 0` ([structural] a predicate that admits divisor != 0. catches a predicate that checks only the range) - invalid input: `dividend = 2147483648, divisor = 1` ([structural] a predicate that admits -2^31 <= dividend, divisor <= 2^31 - 1. catches a predicate that forgot the upper bound on dividend) - `dividend = 10, divisor = 3` → `2` is wrong ([structural] loop stops one subtraction too early. q=2 satisfies q*3<=10 but is one below true) - `dividend = 7, divisor = -3` → `-1` is wrong ([structural] off-by-one in the quotient computation. true quotient is -2; -1 is one step off) - `dividend = 1, divisor = 1` → `0` is wrong ([structural] specification requires only that q*divisor <= dividend, not that q is the greatest such integer. 0 is feasible under that bound but is not the quotient) -/ namespace PDivideTwoIntegers abbrev Input := (Int) × (Int) abbrev Output := Int /-! ### Specification helpers -/ /-- `x` lies in the closed signed 32-bit interval. -/ def InInt32Range (x : Int) : Prop := (-(2 ^ 31 : Int)) ≤ x ∧ x ≤ (2 ^ 31 - 1 : Int) /-- `q` is the toward-zero quotient of `D` by `d`, with remainder `D - d*q`. -/ def IsTruncQuotient (D d q : Int) : Prop := |D - d * q| < |d| ∧ 0 ≤ D * (D - d * q) /-! ### Validity predicate (V) -/ /-- Valid input: both operands are signed 32-bit integers and the divisor is nonzero. -/ def isValidInput (input : Input) : Bool := (-(2 ^ 31 : Int)) ≤ input.1 && input.1 ≤ (2 ^ 31 - 1 : Int) && (-(2 ^ 31 : Int)) ≤ input.2 && input.2 ≤ (2 ^ 31 - 1 : Int) && input.2 != 0 /-! ### Ideal specification (P_spec) -/ /-- `result` is the unique in-range integer selected by the clamping cases or the toward-zero quotient relation. -/ def divide_spec (input : Input) (result : Output) : Prop := let D := input.1 let d := input.2 InInt32Range result ∧ ∀ q : Int, InInt32Range q → ((if 0 < D * d ∧ |d| * (2 ^ 31 : Int) ≤ |D| then q = (2 ^ 31 - 1 : Int) else if D * d < 0 ∧ |d| * (2 ^ 31 + 1 : Int) ≤ |D| then q = (-(2 ^ 31 : Int)) else IsTruncQuotient D d q) ↔ q = result) /-! ### Decidable specification (P_check) -/ /-- Executable form of `divide_spec`: the spec predicate `holds` must be true at `result` and false at every other in-range candidate. Because two distinct quotients satisfying the truncation remainder condition differ by less than 2, the only candidates that could falsify the uniqueness universal are `result - 1` and `result + 1`, so that universal is checked by `.all` over that window. -/ def divide_check (input : Input) (result : Output) : Bool := let D := input.1 let d := input.2 let inRange : Int → Bool := fun x => (-(2 ^ 31 : Int)) ≤ x && x ≤ (2 ^ 31 - 1 : Int) let truncQuot : Int → Bool := fun q => |D - d * q| < |d| && 0 ≤ D * (D - d * q) let holds : Int → Bool := fun q => if 0 < D * d && |d| * (2 ^ 31 : Int) ≤ |D| then q == (2 ^ 31 - 1 : Int) else if D * d < 0 && |d| * (2 ^ 31 + 1 : Int) ≤ |D| then q == (-(2 ^ 31 : Int)) else truncQuot q inRange result && holds result && [result - 1, result + 1].all (fun q => !(inRange q) || !(holds q)) /-- `k = 0` whenever `|d * k|` is strictly below `|d|`. -/ theorem divTI_eq_zero_of_abs_mul_lt {d k : Int} (h : |d * k| < |d|) : k = 0 := by by_contra hk have h1 : (1 : Int) ≤ |k| := Int.one_le_abs hk rw [abs_mul] at h nlinarith [abs_nonneg d, abs_nonneg k] /-- The toward-zero quotient relation pins `q` uniquely. -/ theorem divTI_truncQuot_unique {D d q₁ q₂ : Int} (h₁ : IsTruncQuotient D d q₁) (h₂ : IsTruncQuotient D d q₂) : q₁ = q₂ := by obtain ⟨ha₁, hb₁⟩ := h₁ obtain ⟨ha₂, hb₂⟩ := h₂ rcases lt_trichotomy D 0 with hD | hD | hD · have hr₁ : D - d * q₁ ≤ 0 := by nlinarith have hr₂ : D - d * q₂ ≤ 0 := by nlinarith have hkey : |d * (q₂ - q₁)| < |d| := by have he : d * (q₂ - q₁) = (D - d * q₁) - (D - d * q₂) := by ring rw [abs_lt] at ha₁ ha₂ rw [he, abs_lt] constructor <;> linarith [ha₁.1, ha₁.2, ha₂.1, ha₂.2] have hz := divTI_eq_zero_of_abs_mul_lt hkey omega · subst hD have e₁ : q₁ = 0 := divTI_eq_zero_of_abs_mul_lt (d := d) (by simpa using ha₁) have e₂ : q₂ = 0 := divTI_eq_zero_of_abs_mul_lt (d := d) (by simpa using ha₂) rw [e₁, e₂] · have hr₁ : 0 ≤ D - d * q₁ := by nlinarith have hr₂ : 0 ≤ D - d * q₂ := by nlinarith have hkey : |d * (q₂ - q₁)| < |d| := by have he : d * (q₂ - q₁) = (D - d * q₁) - (D - d * q₂) := by ring rw [abs_lt] at ha₁ ha₂ rw [he, abs_lt] constructor <;> linarith [ha₁.1, ha₁.2, ha₂.1, ha₂.2] have hz := divTI_eq_zero_of_abs_mul_lt hkey omega /-- Boolean range test, lifted out of the checker's `let`. -/ def divTI_inRangeB (x : Int) : Bool := (-(2 ^ 31 : Int)) ≤ x && x ≤ (2 ^ 31 - 1 : Int) /-- Boolean truncation test, lifted out of the checker's `let`. -/ def divTI_truncQuotB (D d q : Int) : Bool := |D - d * q| < |d| && 0 ≤ D * (D - d * q) /-- The checker's candidate predicate, lifted out of its `let`. -/ def divTI_holdsB (D d q : Int) : Bool := if 0 < D * d && |d| * (2 ^ 31 : Int) ≤ |D| then q == (2 ^ 31 - 1 : Int) else if D * d < 0 && |d| * (2 ^ 31 + 1 : Int) ≤ |D| then q == (-(2 ^ 31 : Int)) else divTI_truncQuotB D d q /-- The specification's candidate predicate. -/ def divTI_holdsP (D d q : Int) : Prop := if 0 < D * d ∧ |d| * (2 ^ 31 : Int) ≤ |D| then q = (2 ^ 31 - 1 : Int) else if D * d < 0 ∧ |d| * (2 ^ 31 + 1 : Int) ≤ |D| then q = (-(2 ^ 31 : Int)) else IsTruncQuotient D d q /-- The checker with its `let`s substituted. -/ theorem divTI_check_eq (input : Input) (result : Output) : divide_check input result = (divTI_inRangeB result && divTI_holdsB input.1 input.2 result && [result - 1, result + 1].all (fun q => !(divTI_inRangeB q) || !(divTI_holdsB input.1 input.2 q))) := rfl /-- The specification with its `let`s substituted. -/ theorem divTI_spec_eq (input : Input) (result : Output) : divide_spec input result ↔ (InInt32Range result ∧ ∀ q : Int, InInt32Range q → (divTI_holdsP input.1 input.2 q ↔ q = result)) := Iff.rfl theorem divTI_inRangeB_iff (x : Int) : divTI_inRangeB x = true ↔ InInt32Range x := by simp [divTI_inRangeB, InInt32Range] theorem divTI_holdsB_iff (D d q : Int) : divTI_holdsB D d q = true ↔ divTI_holdsP D d q := by simp [divTI_holdsB, divTI_holdsP, divTI_truncQuotB, IsTruncQuotient] theorem divTI_holdsP_unique {D d q₁ q₂ : Int} (h₁ : divTI_holdsP D d q₁) (h₂ : divTI_holdsP D d q₂) : q₁ = q₂ := by unfold divTI_holdsP at h₁ h₂ by_cases hc₁ : 0 < D * d ∧ |d| * (2 ^ 31 : Int) ≤ |D| · rw [if_pos hc₁] at h₁ h₂ rw [h₁, h₂] · rw [if_neg hc₁] at h₁ h₂ by_cases hc₂ : D * d < 0 ∧ |d| * (2 ^ 31 + 1 : Int) ≤ |D| · rw [if_pos hc₂] at h₁ h₂ rw [h₁, h₂] · rw [if_neg hc₂] at h₁ h₂ exact divTI_truncQuot_unique h₁ h₂ theorem divTI_sub_one_ne (r : Int) : r - 1 ≠ r := by omega theorem divTI_add_one_ne (r : Int) : r + 1 ≠ r := by omega theorem divTI_window (D d r : Int) (hh : divTI_holdsP D d r) (q : Int) (hq : q ≠ r) : (!(divTI_inRangeB q) || !(divTI_holdsB D d q)) = true := by cases hb : divTI_holdsB D d q with | false => simp | true => exact absurd (divTI_holdsP_unique ((divTI_holdsB_iff D d q).mp hb) hh) hq theorem divTI_check_iff_core (input : Input) (result : Output) : divide_check input result = true ↔ (InInt32Range result ∧ divTI_holdsP input.1 input.2 result) := by rw [divTI_check_eq] constructor · intro hc rw [Bool.and_eq_true, Bool.and_eq_true] at hc exact ⟨(divTI_inRangeB_iff result).mp hc.1.1, (divTI_holdsB_iff _ _ _).mp hc.1.2⟩ · rintro ⟨hr, hh⟩ rw [Bool.and_eq_true, Bool.and_eq_true] refine ⟨⟨(divTI_inRangeB_iff result).mpr hr, (divTI_holdsB_iff _ _ _).mpr hh⟩, ?_⟩ rw [List.all_eq_true] intro q hq simp at hq rcases hq with rfl | rfl · exact divTI_window _ _ _ hh _ (divTI_sub_one_ne result) · exact divTI_window _ _ _ hh _ (divTI_add_one_ne result) theorem divTI_spec_iff_core (input : Input) (result : Output) : divide_spec input result ↔ (InInt32Range result ∧ divTI_holdsP input.1 input.2 result) := by rw [divTI_spec_eq] constructor · rintro ⟨hr, hall⟩ exact ⟨hr, (hall result hr).mpr rfl⟩ · rintro ⟨hr, hh⟩ refine ⟨hr, ?_⟩ intro q _ constructor · intro hpq exact divTI_holdsP_unique hpq hh · rintro rfl exact hh /-- On valid input the checker accepts exactly the specified outputs. -/ theorem divide_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : divide_check input result ↔ divide_spec input result := by exact (divTI_check_iff_core input result).trans (divTI_spec_iff_core input result).symm /-! ### Implementation helpers -/ /-- Largest `k` with `b <<< k ≤ a`; `0` when `b = 0` or one shift already exceeds `a`. -/ def highestShift (a b : Nat) : Nat := if h : 0 < b ∧ b <<< 1 ≤ a then 1 + highestShift a (b <<< 1) else 0 termination_by a - b decreasing_by have hs : b <<< 1 = b * 2 := by simp [Nat.shiftLeft_eq] omega /-- Quotient of `a` by `b` by long division: set the bit of the largest shifted divisor and recur on the remainder. -/ def natQuotient (a b : Nat) : Nat := if h : 0 < b ∧ b ≤ a then (1 <<< highestShift a b) + natQuotient (a - (b <<< highestShift a b)) b else 0 termination_by a decreasing_by have hb : 0 < b := h.1 have hpos : 0 < b <<< highestShift a b := by rw [Nat.shiftLeft_eq] positivity omega /-- Apply the toward-zero sign to the natural quotient and clamp the result into the signed 32-bit range. -/ def applySignAndClamp (q : Nat) (neg : Bool) : Int := let z : Int := if neg then -(Int.ofNat q) else Int.ofNat q if z < -(2 ^ 31 : Int) then -(2 ^ 31 : Int) else if (2 ^ 31 - 1 : Int) < z then (2 ^ 31 - 1 : Int) else z /-! ### Main algorithm (impl) -/ /-- Truncating division by bitwise long division on the absolute values, with the sign applied and the quotient clamped to the signed 32-bit range. -/ def truncatingDivide (input : Input) : Output := let neg := decide (input.1 < 0) != decide (input.2 < 0) applySignAndClamp (natQuotient input.1.natAbs input.2.natAbs) neg /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem truncatingDivide_correct (input : Input) (h : isValidInput input) : divide_spec input (truncatingDivide input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (10, 3) #guard isValidInput (7, (-3)) #guard isValidInput (1, 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ((-2147483649), 1)) #guard !(isValidInput (1, 0)) #guard !(isValidInput (2147483648, 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard divide_check (10, 3) 3 #guard divide_check (7, (-3)) (-2) #guard divide_check (1, 1) 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(divide_check (10, 3) 2) #guard !(divide_check (7, (-3)) (-1)) #guard !(divide_check (1, 1) 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard truncatingDivide (10, 3) == 3 #guard truncatingDivide (7, -3) == -2 #guard truncatingDivide (1, 1) == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard divide_check (10, 3) (truncatingDivide (10, 3)) #guard divide_check (7, -3) (truncatingDivide (7, -3)) #guard divide_check (1, 1) (truncatingDivide (1, 1)) end PDivideTwoIntegers