import Mathlib /-! # Sqrtx Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator. For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python. ## Constraints - 0 <= x <= 2^31 - 1 ## Provided examples - `x = 4` → `2` - `x = 8` → `2` - `x = 1` → `1` ## Synthesized negative examples - invalid input: `x = 2147483648` ([structural] a predicate that admits 0 <= x <= 2^31 - 1. one past the stated maximum) - invalid input: `x = 2147483649` ([structural] a predicate that admits 0 <= x <= 2^31 - 1. two past the stated maximum) - invalid input: `x = 2147483650` ([structural] a predicate that admits 0 <= x <= 2^31 - 1. three past the stated maximum) - `x = 4` → `3` is wrong ([structural] soundness check y^2 <= x is missing. 3 exceeds the true floor and no valid y equals it) - `x = 8` → `4` is wrong ([structural] does not require y^2 <= x, so any non-negative integer passes. 4 > 2 and 4^2 > 8, so no sound spec accepts it.) - `x = 1` → `0` is wrong ([structural] maximality stated as achievability alone. 0 is feasible but not the floor sqrt) -/ namespace PSqrtx abbrev Input := Nat abbrev Output := Nat /-! ### Validity predicate (V) -/ /-- Valid input: a natural number at most `2^31 - 1`. -/ def isValidInput (input : Input) : Bool := input ≤ 2^31 - 1 /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest natural number whose square is at most `input`. -/ def sqrtFloor_spec (input : Input) (result : Output) : Prop := IsGreatest {y : ℕ | y * y ≤ input} result /-! ### Decidable specification (P_check) -/ /-- Decides `sqrtFloor_spec`: the greatest-element quantifier is bounded by `input`, since `y * y ≤ input` implies `y ≤ input` for natural numbers. -/ instance decidableSqrtFloorSpec (input result : Nat) : Decidable (IsGreatest {y : Nat | y * y ≤ input} result) := decidable_of_iff (result * result ≤ input ∧ ∀ y < input + 1, y * y ≤ input → y ≤ result) (by have sq_le_le : ∀ {y : Nat}, y * y ≤ input → y ≤ input := by intro y hy rcases Nat.eq_zero_or_pos y with h0 | hpos · subst h0 exact Nat.zero_le input · have hyy : y ≤ y * y := by calc y = y * 1 := (Nat.mul_one y).symm _ ≤ y * y := Nat.mul_le_mul_left y hpos exact le_trans hyy hy constructor · rintro ⟨hr, hb⟩ refine ⟨hr, fun y hy => ?_⟩ exact hb y (Nat.lt_succ_of_le (sq_le_le hy)) hy · rintro ⟨hr, hub⟩ exact ⟨hr, fun y _ hy => hub hy⟩) /-- Executable checker obtained mechanically from the specification. -/ def sqrtFloor_check (input : Input) (result : Output) : Bool := @decide (sqrtFloor_spec input result) (by unfold sqrtFloor_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem sqrtFloor_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : sqrtFloor_check input result ↔ sqrtFloor_spec input result := by simp [sqrtFloor_check] /-! ### Main algorithm (impl) -/ /-- Floor square root by Lean's built-in `Nat.sqrt`, an O(log x) integer square root. -/ def mySqrt (input : Input) : Output := Nat.sqrt input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem mySqrt_correct (input : Input) (h : isValidInput input) : sqrtFloor_spec input (mySqrt input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 4 #guard isValidInput 8 #guard isValidInput 1 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 2147483648) #guard !(isValidInput 2147483649) #guard !(isValidInput 2147483650) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard sqrtFloor_check 4 2 #guard sqrtFloor_check 8 2 #guard sqrtFloor_check 1 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(sqrtFloor_check 4 3) #guard !(sqrtFloor_check 8 4) #guard !(sqrtFloor_check 1 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard mySqrt 4 == 2 #guard mySqrt 8 == 2 #guard mySqrt 1 == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard sqrtFloor_check 4 (mySqrt 4) #guard sqrtFloor_check 8 (mySqrt 8) #guard sqrtFloor_check 1 (mySqrt 1) end PSqrtx