{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.ContinuityRecipBudget where
open import Data.Nat using (ℕ; suc) renaming (_+_ to _+ℕ_)
open import Data.Nat.Properties using (+-suc; +-identityʳ)
open import Data.Rational using (ℚ; 0ℚ; 1ℚ; _+_; _<_; _≤_; _*_)
open import Data.Rational.Base using (NonZero; positive; 1/_; nonNegative)
open import Data.Rational.Properties using
(*-assoc; *-comm; *-inverseʳ; *-identityˡ; *-distribʳ-+; pos⇒nonZero; <⇒≤
; ≤-trans; *-monoˡ-≤-nonNeg; positive⁻¹; 1/pos⇒pos; pos*pos⇒pos)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; sym; cong; trans; module ≡-Reasoning)
open ≡-Reasoning
open import Real using (ε; embed; embed-+-hom; embed-suc-pos)
open import Real.Interval using (RealI)
open import Real.IntervalEquiv using (width; recip2^t)
open import Real.Interval.ContinuityProdBudget using (width-deep)
open import Real.Interval.DensityArch using (embed1≡1)
10ε9≡1 : embed 10 * ε 9 ≡ 1ℚ
10ε9≡1 = *-inverseʳ (embed 10) {{pos⇒nonZero (embed 10) {{embed-suc-pos {9}}}}}
1+1≡2 : 1ℚ + 1ℚ ≡ embed 2
1+1≡2 = refl
e+e≡2e : ε 9 + ε 9 ≡ embed 2 * ε 9
e+e≡2e = begin
ε 9 + ε 9
≡⟨ cong (λ z → z + ε 9) (sym (*-identityˡ (ε 9))) ⟩
1ℚ * ε 9 + ε 9
≡⟨ cong (λ z → 1ℚ * ε 9 + z) (sym (*-identityˡ (ε 9))) ⟩
1ℚ * ε 9 + 1ℚ * ε 9
≡⟨ sym (*-distribʳ-+ (ε 9) 1ℚ 1ℚ) ⟩
(1ℚ + 1ℚ) * ε 9
≡⟨ cong (λ z → z * ε 9) 1+1≡2 ⟩
embed 2 * ε 9
∎
8+2≡10 : embed 8 + embed 2 ≡ embed 10
8+2≡10 = sym (embed-+-hom 8 2)
budget-eq : embed 8 * ε 9 + (ε 9 + ε 9) ≡ 1ℚ
budget-eq = begin
embed 8 * ε 9 + (ε 9 + ε 9)
≡⟨ cong (λ z → embed 8 * ε 9 + z) e+e≡2e ⟩
embed 8 * ε 9 + embed 2 * ε 9
≡⟨ sym (*-distribʳ-+ (ε 9) (embed 8) (embed 2)) ⟩
(embed 8 + embed 2) * ε 9
≡⟨ cong (λ z → z * ε 9) 8+2≡10 ⟩
embed 10 * ε 9
≡⟨ 10ε9≡1 ⟩
1ℚ
∎
suc≡+1 : (n : ℕ) → suc n ≡ n +ℕ 1
suc≡+1 n = sym (trans (+-suc n 0) (cong suc (+-identityʳ n)))
embed-suc-mul : (n : ℕ) (q : ℚ) → embed (suc n) * q ≡ embed n * q + q
embed-suc-mul n q = begin
embed (suc n) * q
≡⟨ cong (λ z → z * q) (cong embed (suc≡+1 n)) ⟩
embed (n +ℕ 1) * q
≡⟨ cong (λ z → z * q) (embed-+-hom n 1) ⟩
(embed n + embed 1) * q
≡⟨ *-distribʳ-+ q (embed n) (embed 1) ⟩
embed n * q + embed 1 * q
≡⟨ cong (λ z → embed n * q + z) (cong (λ z → z * q) embed1≡1) ⟩
embed n * q + 1ℚ * q
≡⟨ cong (λ z → embed n * q + z) (*-identityˡ q) ⟩
embed n * q + q
∎
coef2 : (q : ℚ) → embed 2 * q ≡ q + q
coef2 q = begin
embed 2 * q
≡⟨ embed-suc-mul 1 q ⟩
embed 1 * q + q
≡⟨ cong (λ z → z * q + q) embed1≡1 ⟩
1ℚ * q + q
≡⟨ cong (λ z → z + q) (*-identityˡ q) ⟩
q + q
∎
coef3 : (q : ℚ) → embed 3 * q ≡ (q + q) + q
coef3 q = begin
embed 3 * q
≡⟨ embed-suc-mul 2 q ⟩
embed 2 * q + q
≡⟨ cong (λ z → z + q) (coef2 q) ⟩
(q + q) + q
∎
coef4 : (q : ℚ) → embed 4 * q ≡ ((q + q) + q) + q
coef4 q = begin
embed 4 * q
≡⟨ embed-suc-mul 3 q ⟩
embed 3 * q + q
≡⟨ cong (λ z → z + q) (coef3 q) ⟩
((q + q) + q) + q
∎
coef5 : (q : ℚ) → embed 5 * q ≡ (((q + q) + q) + q) + q
coef5 q = begin
embed 5 * q
≡⟨ embed-suc-mul 4 q ⟩
embed 4 * q + q
≡⟨ cong (λ z → z + q) (coef4 q) ⟩
(((q + q) + q) + q) + q
∎
coef6 : (q : ℚ) → embed 6 * q ≡ ((((q + q) + q) + q) + q) + q
coef6 q = begin
embed 6 * q
≡⟨ embed-suc-mul 5 q ⟩
embed 5 * q + q
≡⟨ cong (λ z → z + q) (coef5 q) ⟩
((((q + q) + q) + q) + q) + q
∎
coef7 : (q : ℚ) → embed 7 * q ≡ (((((q + q) + q) + q) + q) + q) + q
coef7 q = begin
embed 7 * q
≡⟨ embed-suc-mul 6 q ⟩
embed 6 * q + q
≡⟨ cong (λ z → z + q) (coef6 q) ⟩
(((((q + q) + q) + q) + q) + q) + q
∎
coef8 : (q : ℚ) → embed 8 * q ≡ ((((((q + q) + q) + q) + q) + q) + q) + q
coef8 q = begin
embed 8 * q
≡⟨ embed-suc-mul 7 q ⟩
embed 7 * q + q
≡⟨ cong (λ z → z + q) (coef7 q) ⟩
((((((q + q) + q) + q) + q) + q) + q) + q
∎
0<embed-suc : (n : ℕ) → 0ℚ < embed (suc n)
0<embed-suc n = positive⁻¹ (embed (suc n)) {{embed-suc-pos {n}}}
0<3 : 0ℚ < embed 3
0<3 = 0<embed-suc 2
0<6 : 0ℚ < embed 6
0<6 = 0<embed-suc 5
0<inv :
(q : ℚ) (q>0 : 0ℚ < q) →
0ℚ < 1/_ q {{pos⇒nonZero q {{positive q>0}}}}
0<inv q q>0 =
positive⁻¹ (1/_ q {{pos⇒nonZero q {{positive q>0}}}})
{{1/pos⇒pos q {{positive q>0}}}}
0<mul :
(a b : ℚ) (a>0 : 0ℚ < a) (b>0 : 0ℚ < b) →
0ℚ < a * b
0<mul a b a>0 b>0 =
positive⁻¹ (a * b) {{pos*pos⇒pos a {{positive a>0}} b {{positive b>0}}}}
d-cancel :
(c e : ℚ) {{nz : NonZero (c * c)}} →
((c * c) * e) * (1/_ (c * c)) ≡ e
d-cancel c e = begin
((c * c) * e) * (1/_ (c * c))
≡⟨ *-assoc (c * c) e (1/_ (c * c)) ⟩
(c * c) * (e * (1/_ (c * c)))
≡⟨ cong (λ z → (c * c) * z) (*-comm e (1/_ (c * c))) ⟩
(c * c) * ((1/_ (c * c)) * e)
≡⟨ sym (*-assoc (c * c) (1/_ (c * c)) e) ⟩
((c * c) * (1/_ (c * c))) * e
≡⟨ cong (λ z → z * e) (*-inverseʳ (c * c)) ⟩
1ℚ * e
≡⟨ *-identityˡ e ⟩
e
∎
d-eight :
(c e : ℚ) {{nz : NonZero (c * c)}} →
(embed 8 * ((c * c) * e)) * (1/_ (c * c)) ≡ embed 8 * e
d-eight c e = begin
(embed 8 * ((c * c) * e)) * (1/_ (c * c))
≡⟨ *-assoc (embed 8) ((c * c) * e) (1/_ (c * c)) ⟩
embed 8 * (((c * c) * e) * (1/_ (c * c)))
≡⟨ cong (λ z → embed 8 * z) (d-cancel c e) ⟩
embed 8 * e
∎
budget-split :
(A B q : ℚ) → (A + B) * q ≡ A * q + B * q
budget-split A B q = *-distribʳ-+ q A B
width-small-quant :
(r : RealI) (N n : ℕ) (q : ℚ) →
width r 0 ≤ embed N →
0ℚ ≤ embed N →
recip2^t n < q →
width r n ≤ embed N * q
width-small-quant r N n q w0≤ 0≤N small =
≤-trans (width-deep r N n w0≤)
(*-monoˡ-≤-nonNeg (embed N) {{nonNegative 0≤N}}
(<⇒≤ small))