1
$\begingroup$

Where $x \in [1,2]$, find an upper bound on $|1-fl(x*fl(1/x))|$

Where $fl(x)$ rounds a number to the nearest IEEE 64-bit approximate encoded value.

My Work

64-bit IEEE has a 52-bit fraction with an implied leading 1.

With a hypothetical zero-bit fraction, the maximum approximation error would be $2^{-1}$. With a hypothetical $n$ bit fraction, the maximum approximation error would be $2^{-n-1}$. With a 52-bit fraction, the maximum approximation error would be $2^{-53}$.

The maximum error of $|1 - fl(x \cdot fl(1/x))|$ will be when $x$ is at maximum value of $x=2$ and approximation error is maximized so that $fl(x) = x + 2^{-53}$. This gives us a maximum approximation error of:

\begin{align*} &= 2 \cdot (1/2 + 2^{-53}) + 2^{-53} - 1 \\ &= 2 \cdot (1/2 + 2^{-53}) + 2^{-53} - 1 \\ &\approx 3.33 \cdot 10^{-16} \end{align*}

Is this right? Is it close?

$\endgroup$
0
$\begingroup$

Let $x = s\times 2^k$, where $1\leq s<2$. If $s = 1$, then $fl(1/x) = 2^{-k}$ and $|1 - fl(x \times fl(1/x))| = 0$.

Suppose, that $1 < s < 2$. Then $fl(1/x) = 1/x + \frac{d}{2}\times ulp(1/x)$ for some $-1 \leq d \leq 1$. Further, $ulp(1/x) = ulp(2/s\times 2^{-k-1}) = 2^{-k-1-p}$, where $p = 52$ is the precision of IEEE-754 64-bit floating point number (since $1 < 2/s < 2$).

Therefore $\phi \equiv x \times fl(1/x) = 1 + x\times 2^{-k-1-p}\times\frac{d}{2} = 1 + 2^{-p-1}\times\frac{sd}{2}$. Let $\operatorname{next}(x)$, $\operatorname{prev}(x)$ denote respectively next and previous to $x$ representable number. We have $\operatorname{next}(1) = 1+2^{-p}$ and $\operatorname{prev}(1) = 1-2^{-p-1}$.

Since $1-2^{-p-1} < \phi < 1 + 2^{-p-1}$, we have $\operatorname{prev}(1) \leq \phi < \frac{1}{2}(1 + \operatorname{next}(1))$ and $\operatorname{prev}(1) < fl(\phi) \leq 1$, from which we conclude $|1 - fl(\phi)| \leq 1-\operatorname{prev}(1) = 2^{-p-1} = 2^{-53}$.

$\endgroup$
  • $\begingroup$ Experimentally, with a random number like 1.814904755469005, using Julia, Scala, Python 2, Python 3, they all produce error of 1.11e-16 which is definitely greater than zero. So, the answer simply can't be zero. $\endgroup$ – clay Sep 19 '17 at 17:53
  • $\begingroup$ You are right. There was an error in last rounding. $\endgroup$ – Pawel Kowal Sep 19 '17 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.