---

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


1. x : ℕ@i
⊢ if (x) < (2)  then x  else binary-search(λr.x <z r * r;0;x) ∈ ∃r:{ℕ| (((r * r) ≤ x) ∧ x < (r + 1) * (r + 1))}
BY
{ ((Decide ⌜x < 2⌝⋅ THENA Auto) THEN (Reduce 0 THENA Auto)) }

1
1. x : ℕ@i
2. x < 2
⊢ x ∈ ∃r:{ℕ| (((r * r) ≤ x) ∧ x < (r + 1) * (r + 1))}

2
1. x : ℕ@i
2. ¬x < 2
⊢ binary-search(λr.x <z r * r;0;x) ∈ ∃r:{ℕ| (((r * r) ≤ x) ∧ x < (r + 1) * (r + 1))}

---

Latex:

---

Latex:

1.  x  :  \mBbbN{}@i
\mvdash{}  if  (x)  <  (2)    then  x    else  binary-search(\mlambda{}r.x  <z  r  *  r;0;x)  \mmember{}  \mexists{}r:\{\mBbbN{}|  (((r  *  r)  \mleq{}  x)
                                                                                                                                              \mwedge{}  x  <  (r  +  1)  *  (r  +  1))\}


By

---

Latex:
((Decide  \mkleeneopen{}x  <  2\mkleeneclose{}\mcdot{}  THENA  Auto)  THEN  (Reduce  0  THENA  Auto))

---

Home Index