import Mathlib /-! # Powx N Implement pow(x, n), which calculates x raised to the power n (i.e., xn). ## Constraints - -100.0 < x < 100.0 - -2^31 <= n <= 2^31-1 - n is an integer. - Either x is not zero or n > 0. - -10^4 <= xn <= 10^4 ## Provided examples - `x = 2.0, n = 10` → `1024.0` - `x = 2.1, n = 3` → `9.261` - `x = 2.0, n = -2` → `0.25` ## Synthesized negative examples - invalid input: `x = 100.0, n = 1` ([structural] a predicate that admits -100.0 < x < 100.0. x equals the forbidden upper endpoint; a predicate checking <= accepts it) - invalid input: `x = 0.0, n = 0` ([structural] a predicate that admits Either x is not zero or n > 0.. zero base with exponent zero; the forbidden combination) - invalid input: `x = -100.0, n = 1` ([structural] a predicate that admits -100.0 < x < 100.0. x equals the forbidden lower endpoint) - `x = 2.0, n = 10` → `1024.5` is wrong ([structural] exact equality relaxed to a tolerance. Within 1.0 of x^n but not exact.) - `x = 2.1, n = 3` → `4.41` is wrong ([structural] exponent decremented by one. computes 2.1^2 instead of 2.1^3) - `x = 2.0, n = -2` → `0.5` is wrong ([structural] exponent is n+1 instead of n. 0.5 = 2^{-1}) -/ namespace PPowxN abbrev Input := (Float) × (Int) abbrev Output := Float /-! ### Specification helpers -/ /-- Power-by-squaring over `Float` that reports once the running value passes `cap`; sound for bases of at least 1, where every intermediate value stays below the final result. -/ def floatPowOverCap (acc b cap : Float) (e : Nat) : Nat → Bool | 0 => decide (cap < acc) || decide (cap < b) | fuel + 1 => if cap < acc then true else if e == 0 then false else if cap < b then true else floatPowOverCap (if e % 2 == 1 then acc * b else acc) (b * b) cap (e / 2) fuel /-- Decides `|x ^ n| ≤ cap` by splitting on the magnitude of `x` and the sign of `n`, computing only in the cases that can exceed 1. -/ def powWithinBounds (x : Float) (n : Int) (cap : Float) : Bool := if n == 0 then true else if (decide (1 ≤ x.abs) && decide (0 < n)) || (decide (x.abs ≤ 1) && decide (n < 0)) then !(floatPowOverCap 1 (if 0 < n then x.abs else 1 / x.abs) cap n.natAbs 33) else true /-! ### Validity predicate (V) -/ /-- Valid input: `-100 < x < 100`, `n` in the signed 32-bit range, `x ≠ 0` unless `n > 0`, and `|x ^ n| ≤ 10^4`. -/ def isValidInput (input : Input) : Bool := decide ((-100.0 : Float) < input.1) && decide (input.1 < (100.0 : Float)) && decide ((-2147483648 : Int) ≤ input.2 ∧ input.2 ≤ (2147483647 : Int)) && (!(input.1 == 0.0) || decide (0 < input.2)) && powWithinBounds input.1 input.2 10000.0 /-! ### Ideal specification (P_spec) -/ /-- `result` is correct when its real value is within `4e-9` of the real value of `x ^ n`, negative exponents read as reciprocals. -/ def power_spec (input : Input) (result : Output) : Prop := |(Float.toRat0 result : ℝ) - (Float.toRat0 input.1 : ℝ) ^ (input.2 : ℤ)| ≤ 4 / 10 ^ 9 /-! ### Decidable specification (P_check) -/ /-- Decides the specification's real-valued tolerance inequality by pulling it back along the rational casts: every term is a rational embedded in `ℝ`, so `Rat.cast_zpow`, `Rat.cast_sub`, `Rat.cast_abs` and `Rat.cast_le` turn the goal into the corresponding inequality over `ℚ`, which Lean decides natively. -/ instance (input : Input) (result : Output) : Decidable (|(Float.toRat0 result : ℝ) - (Float.toRat0 input.1 : ℝ) ^ (input.2 : ℤ)| ≤ 4 / 10 ^ 9) := decidable_of_iff (|(Float.toRat0 result) - (Float.toRat0 input.1) ^ (input.2 : ℤ)| ≤ (4 : ℚ) / 10 ^ 9) (by rw [show (4 / 10 ^ 9 : ℝ) = ((4 / 10 ^ 9 : ℚ) : ℝ) by push_cast; norm_num, ← Rat.cast_zpow, ← Rat.cast_sub, ← Rat.cast_abs, Rat.cast_le]) /-- Executable checker obtained mechanically from the specification. -/ def power_check (input : Input) (result : Output) : Bool := @decide (power_spec input result) (by unfold power_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem power_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : power_check input result ↔ power_spec input result := by simp [power_check] /-! ### Implementation helpers -/ /-- Recursive binary exponentiation: `fastPow b e` computes `b ^ e` by squaring `b` and halving `e`. -/ def fastPow (b : Float) (e : Nat) : Float := if h : e = 0 then 1.0 else if e % 2 = 1 then b * fastPow (b * b) (e / 2) else fastPow (b * b) (e / 2) termination_by e decreasing_by all_goals exact Nat.div_lt_self (Nat.pos_of_ne_zero h) (by decide) /-! ### Main algorithm (impl) -/ /-- Rounds `y` to the nearest integer-valued `Float`, halves away from zero. -/ def roundFloat (y : Float) : Float := if y < 0 then -((-y) + 0.5).floor else (y + 0.5).floor /-- Exact rational value of the shortest decimal that round-trips to `x`, trying denominators `1, 10, 100, …` in turn and falling back to the exact binary value of `x`. -/ def decimalRatAux (x scale : Float) : Nat → Rat | 0 => x.toRat0 | d + 1 => let m := roundFloat (x * scale) if m / scale == x then m.toRat0 / scale.toRat0 else decimalRatAux x (scale * 10.0) d /-- Reads `x` as the exact decimal it was written as (e.g. `2.1` becomes `21/10`). -/ def decimalRat (x : Float) : Rat := decimalRatAux x 1.0 18 /-- Exact rational power by repeated multiplication. -/ def ratPow (r : Rat) : Nat → Rat | 0 => 1 | e + 1 => r * ratPow r e /-- `Float` nearest to the rational `r`, computed as a single correctly rounded division. -/ def ratToFloat (r : Rat) : Float := let num := if r.num < 0 then - Float.ofNat r.num.natAbs else Float.ofNat r.num.toNat num / Float.ofNat r.den /-- Binary exponentiation over `n.natAbs`, taking the reciprocal when `n` is negative. Small exponents are computed in exact decimal-rational arithmetic so the final `Float` is rounded only once. -/ def powerImpl (input : Input) : Output := let x := input.1 let n := input.2 if n < 0 then if n.natAbs ≤ 64 then ratToFloat (1 / ratPow (decimalRat x) n.natAbs) else 1.0 / fastPow x n.natAbs else if n.natAbs ≤ 64 then ratToFloat (ratPow (decimalRat x) n.natAbs) else fastPow x n.natAbs /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem powerImpl_correct (input : Input) (h : isValidInput input) : power_spec input (powerImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (2.0, 10) #guard isValidInput (2.1, 3) #guard isValidInput (2.0, (-2)) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (100.0, 1)) #guard !(isValidInput (0.0, 0)) #guard !(isValidInput ((-100.0), 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard power_check (2.0, 10) 1024.0 #guard power_check (2.1, 3) 9.261 #guard power_check (2.0, (-2)) 0.25 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(power_check (2.0, 10) 1024.5) #guard !(power_check (2.1, 3) 4.41) #guard !(power_check (2.0, (-2)) 0.5) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard powerImpl (2.0, 10) == 1024.0 #guard powerImpl (2.1, 3) == 9.261 #guard powerImpl (2.0, (-2)) == 0.25 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard power_check (2.0, 10) (powerImpl (2.0, 10)) #guard power_check (2.1, 3) (powerImpl (2.1, 3)) #guard power_check (2.0, (-2)) (powerImpl (2.0, (-2))) end PPowxN