------------------------------------------------------------------------
-- Explicit division for interval reals
--
-- 区间实数的显式除法
------------------------------------------------------------------------

{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}

module Real.Interval.Division where

open import Data.Empty using (⊥-elim)
open import Data.Sum using (_⊎_; inj₁; inj₂)

open import Real.Interval using (RealI)
open import Real.Interval.Arith using (0ℝ; 1ℝ; _+ℝ_; negℝ)
open import Real.Interval.Mul using (_*ℝ_)
open import Real.Interval.Equiv using (_≈ℝ_; ≈ℝ-refl; ≈ℝ-sym; ≈ℝ-trans)
open import Real.Interval.Order using (_<ℝ_; <-irrefl; <-trans)
open import Real.Interval.Mul.Laws using
  (*ℝ-comm; *ℝ-assoc; *ℝ-identityˡ; *ℝ-identityʳ; *ℝ-zeroˡ; *ℝ-distribʳ-+)
open import Real.Interval.Mul.Cong using (*ℝ-cong)
open import Real.Interval.Mul.Order using
  (negℝ-*ℝ; ≈-neg; ≈-<-respʳ; pos*pos; <-*mono)
open import Real.Interval.ArithLaws using (negℝ-0ℝ; negℝ-negℝ)
open import Real.Interval.OrderLaws using (≈-<-resp; <-neg)
open import Real.Interval.Recip using (recipℝ'; recipℝ)
open import Real.Interval.Inverse using (*ℝ-inverse; *ℝ-neg)
open import Real.Interval.RecipLaws using (recipℝ-1; recipℝ-cong)
open import Real.Interval.Embed using (0ℝ<ℝ1ℝ)
open import Real.Interval.Reasoning.Equiv

------------------------------------------------------------------------
-- Definition
--
-- 定义

-- Divide by a non-zero real: multiply by its reciprocal.
--
-- 除以非零实数:乘以其倒数。
infixl 7 _/ℝ_

_/ℝ_ : (x y : RealI) → (nz : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ)) → RealI
_/ℝ_ x y nz = x *ℝ recipℝ' y nz

------------------------------------------------------------------------
-- Non-zero witnesses
--
-- 非零见证

-- The product of two non-zero reals is non-zero.
--
-- 两个非零实数之积非零。
nonzero-mul : (y z : RealI)
  (nz_y : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
  (nz_z : (0ℝ <ℝ z) ⊎ (z <ℝ 0ℝ))
  → (0ℝ <ℝ y *ℝ z) ⊎ (y *ℝ z <ℝ 0ℝ)
nonzero-mul y z (inj₁ 0<y) (inj₁ 0<z) = inj₁ (pos*pos y z 0<y 0<z)
nonzero-mul y z (inj₁ 0<y) (inj₂ z<0) =
  inj₂ (≈-<-resp (≈ℝ-sym (*ℝ-comm y z)) (z*y<0))
  where
    z*y<0 : z *ℝ y <ℝ 0ℝ
    z*y<0 = ≈-<-respʳ (*ℝ-zeroˡ y) (<-*mono z 0ℝ y z<0 0<y)
nonzero-mul y z (inj₂ y<0) (inj₁ 0<z) =
  inj₂ (≈-<-respʳ (*ℝ-zeroˡ z) (<-*mono y 0ℝ z y<0 0<z))
nonzero-mul y z (inj₂ y<0) (inj₂ z<0) =
  inj₁ (≈-<-respʳ (negℝ-neg-mul y z)
        (pos*pos (negℝ y) (negℝ z) 0<-ny 0<-nz))
  where
    0<-ny : 0ℝ <ℝ negℝ y
    0<-ny = ≈-<-resp negℝ-0ℝ (<-neg y 0ℝ y<0)
    0<-nz : 0ℝ <ℝ negℝ z
    0<-nz = ≈-<-resp negℝ-0ℝ (<-neg z 0ℝ z<0)
    negℝ-neg-mul : (a b : RealI) → negℝ a *ℝ negℝ b ≈ℝ a *ℝ b
    negℝ-neg-mul a b =
      beginℝ
        negℝ a *ℝ negℝ b
          ≈ℝ⟨ ≈ℝ-sym (negℝ-*ℝ a (negℝ b)) ⟩
        negℝ (a *ℝ negℝ b)
          ≈ℝ⟨ ≈-neg (*ℝ-neg a b) ⟩
        negℝ (negℝ (a *ℝ b))
          ≈ℝ⟨ negℝ-negℝ (a *ℝ b) ⟩
        a *ℝ b
      ∎ℝ

------------------------------------------------------------------------
-- Uniqueness of the reciprocal
--
-- 倒数的唯一性

-- Any right inverse of y is the reciprocal of y.
--
-- y 的任意右逆等于 y 的倒数。
recip-unique : (y : RealI)
  (nz : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
  (r : RealI)
  → y *ℝ r ≈ℝ 1ℝ
  → r ≈ℝ recipℝ' y nz
recip-unique y nz r yr≈1 =
  beginℝ
    r
      ≈ℝ⟨ ≈ℝ-sym (*ℝ-identityʳ r) ⟩
    r *ℝ 1ℝ
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl (≈ℝ-sym (*ℝ-inverse y nz)) ⟩
    r *ℝ (y *ℝ recipℝ' y nz)
      ≈ℝ⟨ ≈ℝ-sym (*ℝ-assoc r y (recipℝ' y nz)) ⟩
    (r *ℝ y) *ℝ recipℝ' y nz
      ≈ℝ⟨ *ℝ-cong (*ℝ-comm r y) ≈ℝ-refl ⟩
    (y *ℝ r) *ℝ recipℝ' y nz
      ≈ℝ⟨ *ℝ-cong yr≈1 ≈ℝ-refl ⟩
    1ℝ *ℝ recipℝ' y nz
      ≈ℝ⟨ *ℝ-identityˡ (recipℝ' y nz) ⟩
    recipℝ' y nz
  ∎ℝ

------------------------------------------------------------------------
-- Reciprocal of negation and product
--
-- 取负与乘积的倒数

-- The reciprocal of a negation is the negation of the reciprocal.
--
-- 取负的倒数等于倒数的取负。
recipℝ'-neg-eq : (y : RealI)
  (nz : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
  (nz_neg : (0ℝ <ℝ negℝ y) ⊎ (negℝ y <ℝ 0ℝ))
  → recipℝ' (negℝ y) nz_neg ≈ℝ negℝ (recipℝ' y nz)
recipℝ'-neg-eq y nz nz_neg =
  ≈ℝ-sym (recip-unique (negℝ y) nz_neg (negℝ (recipℝ' y nz)) target)
  where
    r = recipℝ' y nz
    y-neg-r-eq : y *ℝ negℝ r ≈ℝ negℝ (y *ℝ r)
    y-neg-r-eq =
      beginℝ
        y *ℝ negℝ r
          ≈ℝ⟨ *ℝ-comm y (negℝ r) ⟩
        negℝ r *ℝ y
          ≈ℝ⟨ ≈ℝ-sym (negℝ-*ℝ r y) ⟩
        negℝ (r *ℝ y)
          ≈ℝ⟨ ≈-neg (*ℝ-comm r y) ⟩
        negℝ (y *ℝ r)
      ∎ℝ
    target : negℝ y *ℝ negℝ r ≈ℝ 1ℝ
    target =
      beginℝ
        negℝ y *ℝ negℝ r
          ≈ℝ⟨ ≈ℝ-sym (negℝ-*ℝ y (negℝ r)) ⟩
        negℝ (y *ℝ negℝ r)
          ≈ℝ⟨ ≈-neg y-neg-r-eq ⟩
        negℝ (negℝ (y *ℝ r))
          ≈ℝ⟨ negℝ-negℝ (y *ℝ r) ⟩
        y *ℝ r
          ≈ℝ⟨ *ℝ-inverse y nz ⟩
        1ℝ
      ∎ℝ

-- The reciprocal of a product is the product of reciprocals.
--
-- 乘积的倒数等于倒数之积。
recipℝ'-mul-eq : (y z : RealI)
  (nz_y : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
  (nz_z : (0ℝ <ℝ z) ⊎ (z <ℝ 0ℝ))
  (nz_yz : (0ℝ <ℝ y *ℝ z) ⊎ (y *ℝ z <ℝ 0ℝ))
  → recipℝ' (y *ℝ z) nz_yz ≈ℝ recipℝ' y nz_y *ℝ recipℝ' z nz_z
recipℝ'-mul-eq y z nz_y nz_z nz_yz =
  ≈ℝ-sym
    (recip-unique (y *ℝ z) nz_yz (recipℝ' y nz_y *ℝ recipℝ' z nz_z) target)
  where
    r_y = recipℝ' y nz_y
    r_z = recipℝ' z nz_z
    target : (y *ℝ z) *ℝ (r_y *ℝ r_z) ≈ℝ 1ℝ
    target =
      beginℝ
        (y *ℝ z) *ℝ (r_y *ℝ r_z)
          ≈ℝ⟨ *ℝ-assoc y z (r_y *ℝ r_z) ⟩
        y *ℝ (z *ℝ (r_y *ℝ r_z))
          ≈ℝ⟨ *ℝ-cong ≈ℝ-refl (≈ℝ-sym (*ℝ-assoc z r_y r_z)) ⟩
        y *ℝ ((z *ℝ r_y) *ℝ r_z)
          ≈ℝ⟨ *ℝ-cong ≈ℝ-refl
                (*ℝ-cong (*ℝ-comm z r_y) ≈ℝ-refl) ⟩
        y *ℝ ((r_y *ℝ z) *ℝ r_z)
          ≈ℝ⟨ *ℝ-cong ≈ℝ-refl (*ℝ-assoc r_y z r_z) ⟩
        y *ℝ (r_y *ℝ (z *ℝ r_z))
          ≈ℝ⟨ *ℝ-cong ≈ℝ-refl
                (*ℝ-cong ≈ℝ-refl (*ℝ-inverse z nz_z)) ⟩
        y *ℝ (r_y *ℝ 1ℝ)
          ≈ℝ⟨ *ℝ-cong ≈ℝ-refl (*ℝ-identityʳ r_y) ⟩
        y *ℝ r_y
          ≈ℝ⟨ *ℝ-inverse y nz_y ⟩
        1ℝ
      ∎ℝ

------------------------------------------------------------------------
-- Congruence
--
-- 合同性

-- Equal numerators give equal quotients with the same denominator.
--
-- 分母相同时,分子相等则商相等。
/ℝ-congˡ : {x x' y : RealI}
           {nz : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ)}
         → x ≈ℝ x' → _/ℝ_ x y nz ≈ℝ _/ℝ_ x' y nz
/ℝ-congˡ x≈x' = *ℝ-cong x≈x' ≈ℝ-refl

-- Denominator congruence, positive branch.
--
-- 分母合同性,正分支。
/ℝ-congʳ-pos :
  {x y y' : RealI}
  (0<y : 0ℝ <ℝ y) (0<y' : 0ℝ <ℝ y')
  → y ≈ℝ y'
  → _/ℝ_ x y (inj₁ 0<y) ≈ℝ _/ℝ_ x y' (inj₁ 0<y')
/ℝ-congʳ-pos {x} {y} {y'} 0<y 0<y' y≈y' =
  *ℝ-cong ≈ℝ-refl (recipℝ-cong y y' 0<y 0<y' y≈y')

-- Denominator congruence, negative branch.
--
-- 分母合同性,负分支。
/ℝ-congʳ-neg :
  {x y y' : RealI}
  (y<0 : y <ℝ 0ℝ) (y'<0 : y' <ℝ 0ℝ)
  → y ≈ℝ y'
  → _/ℝ_ x y (inj₂ y<0) ≈ℝ _/ℝ_ x y' (inj₂ y'<0)
/ℝ-congʳ-neg {x} {y} {y'} y<0 y'<0 y≈y' =
  *ℝ-cong ≈ℝ-refl (recipℝ'-neg-cong y≈y')
  where
    0<-ny : 0ℝ <ℝ negℝ y
    0<-ny = ≈-<-resp negℝ-0ℝ (<-neg y 0ℝ y<0)
    0<-ny' : 0ℝ <ℝ negℝ y'
    0<-ny' = ≈-<-resp negℝ-0ℝ (<-neg y' 0ℝ y'<0)
    ny≈ny' : negℝ y ≈ℝ negℝ y'
    ny≈ny' = ≈-neg y≈y'
    recipℝ'-neg-cong :
      y ≈ℝ y'
      → recipℝ' y (inj₂ y<0) ≈ℝ recipℝ' y' (inj₂ y'<0)
    recipℝ'-neg-cong y≈y' =
      ≈-neg (recipℝ-cong (negℝ y) (negℝ y') 0<-ny 0<-ny' ny≈ny')

-- Denominator congruence, combined. Branches must match; the
-- mismatched cases are impossible because _≈ℝ_ preserves strict order.
--
-- 组合的分母合同性。分支必须一致;不一致分支因 _≈ℝ_ 保持严格序而矛盾。
/ℝ-congʳ :
  {x y y' : RealI}
  (nz  : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
  (nz' : (0ℝ <ℝ y') ⊎ (y' <ℝ 0ℝ))
  → y ≈ℝ y'
  → _/ℝ_ x y nz ≈ℝ _/ℝ_ x y' nz'
/ℝ-congʳ (inj₁ 0<y) (inj₁ 0<y') y≈y' = /ℝ-congʳ-pos 0<y 0<y' y≈y'
/ℝ-congʳ (inj₁ 0<y) (inj₂ y'<0) y≈y' =
  ⊥-elim (<-irrefl 0ℝ (<-trans (≈-<-respʳ y≈y' 0<y) y'<0))
/ℝ-congʳ {y = y} (inj₂ y<0) (inj₁ 0<y') y≈y' =
  ⊥-elim (<-irrefl y (<-trans y<0 (≈-<-respʳ (≈ℝ-sym y≈y') 0<y')))
/ℝ-congʳ (inj₂ y<0) (inj₂ y'<0) y≈y' = /ℝ-congʳ-neg y<0 y'<0 y≈y'

-- Full congruence of division.
--
-- 除法的完整合同性。
/ℝ-cong :
  {x x' y y' : RealI}
  (nz  : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
  (nz' : (0ℝ <ℝ y') ⊎ (y' <ℝ 0ℝ))
  → x ≈ℝ x' → y ≈ℝ y'
  → _/ℝ_ x y nz ≈ℝ _/ℝ_ x' y' nz'
/ℝ-cong nz nz' x≈x' y≈y' =
  ≈ℝ-trans (/ℝ-congˡ {nz = nz} x≈x')
           (/ℝ-congʳ nz nz' y≈y')

------------------------------------------------------------------------
-- Multiplication and division cancel
--
-- 乘法与除法互消

-- Multiplying then dividing by the same non-zero real cancels.
--
-- 先乘后除以同一非零实数,相互抵消。
*ℝ-/ℝ : (x y : RealI) (nz : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
      → _/ℝ_ (x *ℝ y) y nz ≈ℝ x
*ℝ-/ℝ x y nz =
  beginℝ
    (x *ℝ y) *ℝ recipℝ' y nz
      ≈ℝ⟨ *ℝ-assoc x y (recipℝ' y nz) ⟩
    x *ℝ (y *ℝ recipℝ' y nz)
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl (*ℝ-inverse y nz) ⟩
    x *ℝ 1ℝ
      ≈ℝ⟨ *ℝ-identityʳ x ⟩
    x
  ∎ℝ

-- Dividing then multiplying by the same non-zero real cancels.
--
-- 先除后乘以同一非零实数,相互抵消。
/ℝ-*ℝ : (x y : RealI) (nz : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
      → _/ℝ_ x y nz *ℝ y ≈ℝ x
/ℝ-*ℝ x y nz =
  beginℝ
    (x *ℝ recipℝ' y nz) *ℝ y
      ≈ℝ⟨ *ℝ-assoc x (recipℝ' y nz) y ⟩
    x *ℝ (recipℝ' y nz *ℝ y)
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl
            (≈ℝ-trans (*ℝ-comm (recipℝ' y nz) y) (*ℝ-inverse y nz)) ⟩
    x *ℝ 1ℝ
      ≈ℝ⟨ *ℝ-identityʳ x ⟩
    x
  ∎ℝ

------------------------------------------------------------------------
-- Division by one
--
-- 除以一

-- Dividing by one leaves the numerator unchanged.
--
-- 除以一不改变分子。
/ℝ-1 : (x : RealI) → _/ℝ_ x 1ℝ (inj₁ 0ℝ<ℝ1ℝ) ≈ℝ x
/ℝ-1 x =
  beginℝ
    x *ℝ recipℝ 1ℝ 0ℝ<ℝ1ℝ
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl recipℝ-1 ⟩
    x *ℝ 1ℝ
      ≈ℝ⟨ *ℝ-identityʳ x ⟩
    x
  ∎ℝ

------------------------------------------------------------------------
-- Zero numerator
--
-- 零分子

-- Zero divided by any non-zero real is zero.
--
-- 零除以任意非零实数等于零。
0/ℝ : (y : RealI) (nz : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
    → _/ℝ_ 0ℝ y nz ≈ℝ 0ℝ
0/ℝ y nz = *ℝ-zeroˡ (recipℝ' y nz)

------------------------------------------------------------------------
-- Interaction with negation
--
-- 与取负的交互

-- Negating the numerator negates the quotient.
--
-- 对分子取负等价于对商取负。
negℝ-/ℝ : (x y : RealI) (nz : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
        → _/ℝ_ (negℝ x) y nz ≈ℝ negℝ (_/ℝ_ x y nz)
negℝ-/ℝ x y nz =
  beginℝ
    negℝ x *ℝ recipℝ' y nz
      ≈ℝ⟨ ≈ℝ-sym (negℝ-*ℝ x (recipℝ' y nz)) ⟩
    negℝ (x *ℝ recipℝ' y nz)
  ∎ℝ

-- Negating the denominator negates the quotient.
--
-- 对分母取负等价于对商取负。
/ℝ-neg-denom : (x y : RealI) (nz : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
  (nz_neg : (0ℝ <ℝ negℝ y) ⊎ (negℝ y <ℝ 0ℝ))
  → _/ℝ_ x (negℝ y) nz_neg ≈ℝ negℝ (_/ℝ_ x y nz)
/ℝ-neg-denom x y nz nz_neg =
  beginℝ
    x *ℝ recipℝ' (negℝ y) nz_neg
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl (recipℝ'-neg-eq y nz nz_neg) ⟩
    x *ℝ negℝ (recipℝ' y nz)
      ≈ℝ⟨ *ℝ-neg x (recipℝ' y nz) ⟩
    negℝ (x *ℝ recipℝ' y nz)
  ∎ℝ

------------------------------------------------------------------------
-- Addition over a common denominator
--
-- 同分母加法

-- Sums with the same denominator add in the numerator.
--
-- 同分母的商之和等于分子之和的商。
/ℝ-+-same-denom :
  (x y z : RealI) (nz : (0ℝ <ℝ z) ⊎ (z <ℝ 0ℝ))
  → _/ℝ_ x z nz +ℝ _/ℝ_ y z nz ≈ℝ _/ℝ_ (x +ℝ y) z nz
/ℝ-+-same-denom x y z nz =
  ≈ℝ-sym
    (beginℝ
      (x +ℝ y) *ℝ recipℝ' z nz
        ≈ℝ⟨ *ℝ-distribʳ-+ (recipℝ' z nz) x y ⟩
      x *ℝ recipℝ' z nz +ℝ y *ℝ recipℝ' z nz
    ∎ℝ)

------------------------------------------------------------------------
-- Associativity
--
-- 除法结合

-- Dividing by y and then by z equals dividing by the product.
--
-- 先除以 y 再除以 z 等于除以 y * z。
/ℝ-assoc : (x y z : RealI)
  (nz_y : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
  (nz_z : (0ℝ <ℝ z) ⊎ (z <ℝ 0ℝ))
  → _/ℝ_ (_/ℝ_ x y nz_y) z nz_z ≈ℝ
    _/ℝ_ x (y *ℝ z) (nonzero-mul y z nz_y nz_z)
/ℝ-assoc x y z nz_y nz_z =
  beginℝ
    (x *ℝ recipℝ' y nz_y) *ℝ recipℝ' z nz_z
      ≈ℝ⟨ *ℝ-assoc x (recipℝ' y nz_y) (recipℝ' z nz_z) ⟩
    x *ℝ (recipℝ' y nz_y *ℝ recipℝ' z nz_z)
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl
            (≈ℝ-sym (recipℝ'-mul-eq y z nz_y nz_z
                       (nonzero-mul y z nz_y nz_z))) ⟩
    x *ℝ recipℝ' (y *ℝ z) (nonzero-mul y z nz_y nz_z)
  ∎ℝ

------------------------------------------------------------------------
-- Cancellation
--
-- 约分

-- Common factors cancel in numerator and denominator.
--
-- 分子与分母中的公共因子相消。
/ℝ-cancel : (x y z : RealI)
  (nz_y : (0ℝ <ℝ y) ⊎ (y <ℝ 0ℝ))
  (nz_z : (0ℝ <ℝ z) ⊎ (z <ℝ 0ℝ))
  → _/ℝ_ (x *ℝ z) (y *ℝ z) (nonzero-mul y z nz_y nz_z) ≈ℝ _/ℝ_ x y nz_y
/ℝ-cancel x y z nz_y nz_z =
  beginℝ
    (x *ℝ z) *ℝ recipℝ' (y *ℝ z) (nonzero-mul y z nz_y nz_z)
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl
            (recipℝ'-mul-eq y z nz_y nz_z (nonzero-mul y z nz_y nz_z)) ⟩
    (x *ℝ z) *ℝ (recipℝ' y nz_y *ℝ recipℝ' z nz_z)
      ≈ℝ⟨ *ℝ-assoc x z (recipℝ' y nz_y *ℝ recipℝ' z nz_z) ⟩
    x *ℝ (z *ℝ (recipℝ' y nz_y *ℝ recipℝ' z nz_z))
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl
            (≈ℝ-sym (*ℝ-assoc z (recipℝ' y nz_y) (recipℝ' z nz_z))) ⟩
    x *ℝ ((z *ℝ recipℝ' y nz_y) *ℝ recipℝ' z nz_z)
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl
            (*ℝ-cong (*ℝ-comm z (recipℝ' y nz_y)) ≈ℝ-refl) ⟩
    x *ℝ ((recipℝ' y nz_y *ℝ z) *ℝ recipℝ' z nz_z)
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl
            (*ℝ-assoc (recipℝ' y nz_y) z (recipℝ' z nz_z)) ⟩
    x *ℝ (recipℝ' y nz_y *ℝ (z *ℝ recipℝ' z nz_z))
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl
            (*ℝ-cong ≈ℝ-refl (*ℝ-inverse z nz_z)) ⟩
    x *ℝ (recipℝ' y nz_y *ℝ 1ℝ)
      ≈ℝ⟨ *ℝ-cong ≈ℝ-refl (*ℝ-identityʳ (recipℝ' y nz_y)) ⟩
    x *ℝ recipℝ' y nz_y
  ∎ℝ