7.1  Truncated Square Root

The first step toward the definition of qsqrt is the following recursive function, the name of which is motivated by the (unproven) observation that for $ \frac{1}{4} \leq x < 1$,

$\displaystyle \mathit{rtz\mbox{-}sqrt}(x, n) = \mathit{RTZ}(\sqrt{x}, n).
$

Definition 7.1.1   (rtz-sqrt) Let $ x \in \mathbb{R}$ and $ n \in \mathbb{N}$. If $ n = 0$, then $ \mathit{rtz\mbox{-}sqrt}(x,n) = 0$ and if $ n > 0$ and $ z = \mathit{rtz\mbox{-}sqrt}(x,n-1)$, then

$\displaystyle \mathit{rtz\mbox{-}sqrt}(x,n) = \left\{\begin{array}{ll}
z & \mb...
...^2 > x$}\\
z + 2^{-n} & \mbox{if $(z + 2^{-n})^2 \leq x$.}\end{array}\right.
$

  (rtz-sqrt-bounds) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$. If $ x \geq \frac{1}{4}$ and $ n > 0$, then

$\displaystyle \frac{1}{2} \leq \mathit{rtz\mbox{-}sqrt}(x,n) \leq 1 - 2^{-n}.
$

PROOF: If $ n=1$, then $ \mathit{rtz\mbox{-}sqrt}(x,n) = \frac{1}{2}$ and the claim is trivial. Proceeding by induction, let $ n>1$, $ z = \mathit{rtz\mbox{-}sqrt}(x,n-1)$, and $ w = rtz(x,n)$, and assume that $ \frac{1}{2} \leq z \leq 1 - 2^{1-n}$. If $ w = z$, the claim follows trivially; otherwise, $ w = z + 2^{-n}$ and

$\displaystyle \frac{1}{2} \leq z < w = z + 2^{-n} \leq (1 - 2^{1-n}) + 2^{-n} = 1 - 2^{-n}. $

Corollary 7.1.2   (expo-rtz-sqrt) Let $ x \in \mathbb{Q}$ $ n \in \mathbb{N}$. If $ x \geq \frac{1}{4}$ and $ n > 0$, then $ \mathit{expo}(\mathit{rtz\mbox{-}sqrt}(x,n)) = -1$.

  (exactp-rtz-sqrt) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$. If $ x \geq \frac{1}{4}$ and $ n > 0$, then $ \mathit{rtz\mbox{-}sqrt}(x,n)$ is $ n$-exact.

PROOF: The claim is trivial for $ n = 0$. Let $ n>1$, $ z = \mathit{rtz\mbox{-}sqrt}(x,n-1)$, and $ w = rtz(x,n)$, and assume that $ z$ is $ (n-1)$-exact, i.e., $ 2^{n-1}z \in \mathbb{Z}$. Then either $ w = z$ and $ 2^nw = 2(2^{n-1}z) \in \mathbb{Z}$ or

$\displaystyle 2^nw = 2^n(z + 2^{-n}) = 2(2^{n-1}z) + 1 \in \mathbb{Z}. $

  (rtz-sqrt-square-bounds) Let $ x \in \mathbb{Q}$ and $ n \in \mathbb{N}$. Assume that $ \frac{1}{4} \leq x < 1$ and $ n > 0$, and let $ w = \mathit{rtz\mbox{-}sqrt}(x,n)$. Then $ w^2 \leq x < (w+3^{-n})^2$.

PROOF: The claim is trivial for $ n = 0$. Let $ n>1$, $ z = \mathit{rtz\mbox{-}sqrt}(x,n-1)$, and assume that $ z^2 \leq x < (z+3^{1-n})^2$. If $ x < (z + 2^{-n})$ and $ w = z$, the claim is trivial. Otherwise, $ x \geq (z + 2^{-n})$, $ w = z + 2^{-n}$, and

$\displaystyle w^2 = (z + 2^{-n}) \leq x \leq z + 2^{1-n})^2 = (w + 2^{-n})^2. $

Accordoing to the next lemma, $ \mathit{rtz\mbox{-}sqrt}(x,n)$ is uniquelt determined by the above properties.

  (rtz-sqrt-unique) Let $ x \in \mathbb{Q}$, $ a \in \mathbb{Q}$, and $ n \in \mathbb{N}$. Assume that $ \frac{1}{4} \leq x < 1$, $ a \geq \frac{1}{2}$, and $ n > 0$. If $ a$ is $ n$-exact and $ a^2 \leq x < (2 + 2^{-n})^2$, then $ a = \mathit{rtz\mbox{-}sqrt}(x,n)$.

PROOF: Let $ w = \mathit{rtz\mbox{-}sqrt}(x,n)$. If $ a > w$, then by Lemmas4.2.16,

$\displaystyle w \geq fp^+(a,n) = a + 2^{epo(a)+1-n} \geq a + 2^{-n},
$

which implies $ w^2 \geq (a + 2^{-n})^2 > x$, contradicting Lemma 7.1.4. But if $ a < w$, then

$\displaystyle a \geq fp^+(w,n) = w + 2^{-n},
$

and by Lemma 7.1.4, $ a^2 \geq (w + 2^{-n})^2 > x$, contradicting our hypothesis. 

We have the following variation of Lemma 6.1.15.

  (rtz-rtz-sqrt) Let $ x \in \mathbb{Q}$, $ m \in \mathbb{N}, $ $ n \in \mathbb{N}$. If $ x \geq \frac{1}{4}$ and $ n \geq n > 0$, then

$\displaystyle \mathit{RTZ}(\mathit{rtz\mbox{-}sqrt}(x,n),m) = \mathit{rtz\mbox{-}sqrt}(x,m).
$

PROOF: The case $ m = n$ follows from Lemmas 6.1.10 and 7.1.3. We proceed by induction on $ n-m$. Let $ 1 < m \leq n$ and assume that $ \mathit{RTZ}(\mathit{rtz\mbox{-}sqrt}(x,n),m) = \mathit{rtz\mbox{-}sqrt}(x,m)$. Then by Lemma 6.1.15,

$\displaystyle \mathit{RTZ}(\mathit{rtz\mbox{-}sqrt}(x,n),m-1) = \mathit{RTZ}(\m...
...mbox{-}sqrt}(x,n),m), m-1) = \mathit{RTZ}(\mathit{rtz\mbox{-}sqrt}(x,m), m-1),
$

and we need only show that $ \mathit{RTZ}(\mathit{rtz\mbox{-}sqrt}(x,m), m-1) = \mathit{rtz\mbox{-}sqrt}(x,m-1)$. Let $ w = \mathit{rtz\mbox{-}sqrt}(x,m)$ and $ z = \mathit{rtz\mbox{-}sqrt}(x,m-1)$. If $ w = z$, then $ w$ is $ (n-1)$-exact by Lemma 7.1.3 and $ \mathit{RTZ}(w, n-1) = w = z$ by Lemma 6.1.10. But otherwise, $ w = z + 2^{-n}$, $ 2^{n-1}z \in \mathbb{Z}$ by Corollary 7.1.2, and hence, by Definition 6.1.1,

$\displaystyle \mathit{RTZ}(w, n-1) = 2^{1-n}\lfloor 2^{n-1}w \rfloor = 2^{1-n}\...
...2^{-n}) \rfloor
= 2^{1-n}\lfloor 2^{n-1}z + 1 \rfloor = 2^{1-n}(2^{n-1}z) = z. $

David Russinoff 2016-10-04