---

Step * 1 2 2 of Lemma integer-sqrt-bin-search


1. x : ℕ@i
2. ¬x < 2
3. binary-search(λr.x <z r * r;0;x)
= binary-search(λr.x <z r * r;0;x)
∈ {x1:ℕx| (¬↑((λr.x <z r * r) x1)) ∧ (↑((λr.x <z r * r) (x1 + 1)))} 
⊢ {x1:ℕx| (¬↑((λr.x <z r * r) x1)) ∧ (↑((λr.x <z r * r) (x1 + 1)))}  ⊆r (∃r:{ℕ
    (((r * r) ≤ x) ∧ x < (r + 1) * (r + 1))})
BY
{ (Reduce 0 THEN (D 0 THENA Auto) THEN D -1 THEN RW assert_pushdownC (-1) THEN Auto) }

---

Latex:

---

Latex:

1.  x  :  \mBbbN{}@i
2.  \mneg{}x  <  2
3.  binary-search(\mlambda{}r.x  <z  r  *  r;0;x)  =  binary-search(\mlambda{}r.x  <z  r  *  r;0;x)
\mvdash{}  \{x1:\mBbbN{}x|  (\mneg{}\muparrow{}((\mlambda{}r.x  <z  r  *  r)  x1))  \mwedge{}  (\muparrow{}((\mlambda{}r.x  <z  r  *  r)  (x1  +  1)))\}    \msubseteq{}r  (\mexists{}r:\{\mBbbN{}|  (((r  *  r)  \mleq{}  x)
                                                                                                                                                                  \mwedge{}  x  <  (r  +  1)
                                                                                                                                                                      *  (r  +  1))\})


By

---

Latex:
(Reduce  0  THEN  (D  0  THENA  Auto)  THEN  D  -1  THEN  RW  assert\_pushdownC  (-1)  THEN  Auto)

---

Home Index