Kahan p9 Example

Average Error: 20.2 → 5.1

Time: 7.9s

Precision: 64

\[0.0 \lt x \lt 1 \land y \lt 1\]

Math

\[\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\]

↓

\[\begin{array}{l} \mathbf{if}\;y \le -1.946405021817491610626074253405329924501 \cdot 10^{152}:\\ \;\;\;\;-1\\ \mathbf{elif}\;y \le -1.048004930642509241748111685822132171198 \cdot 10^{-161}:\\ \;\;\;\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\\ \mathbf{elif}\;y \le 2.184840803589228861176620759693605020188 \cdot 10^{-164}:\\ \;\;\;\;1\\ \mathbf{else}:\\ \;\;\;\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\\ \end{array}\]

C

double f(double x, double y) {
        double r58256 = x;
        double r58257 = y;
        double r58258 = r58256 - r58257;
        double r58259 = r58256 + r58257;
        double r58260 = r58258 * r58259;
        double r58261 = r58256 * r58256;
        double r58262 = r58257 * r58257;
        double r58263 = r58261 + r58262;
        double r58264 = r58260 / r58263;
        return r58264;
}

↓

double f(double x, double y) {
        double r58265 = y;
        double r58266 = -1.9464050218174916e+152;
        bool r58267 = r58265 <= r58266;
        double r58268 = -1.0;
        double r58269 = -1.0480049306425092e-161;
        bool r58270 = r58265 <= r58269;
        double r58271 = x;
        double r58272 = r58271 - r58265;
        double r58273 = r58271 + r58265;
        double r58274 = r58272 * r58273;
        double r58275 = r58271 * r58271;
        double r58276 = r58265 * r58265;
        double r58277 = r58275 + r58276;
        double r58278 = r58274 / r58277;
        double r58279 = 2.184840803589229e-164;
        bool r58280 = r58265 <= r58279;
        double r58281 = 1.0;
        double r58282 = r58280 ? r58281 : r58278;
        double r58283 = r58270 ? r58278 : r58282;
        double r58284 = r58267 ? r58268 : r58283;
        return r58284;
}

Error

Bits error versus x

Bits error versus y

Target

Original	20.2
Target	0.1
Herbie	5.1

\[\begin{array}{l} \mathbf{if}\;0.5 \lt \left|\frac{x}{y}\right| \lt 2:\\ \;\;\;\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\\ \mathbf{else}:\\ \;\;\;\;1 - \frac{2}{1 + \frac{x}{y} \cdot \frac{x}{y}}\\ \end{array}\]

Derivation

1. Split input into 3 regimes

2. if y < -1.9464050218174916e+152

   1. Initial program 63.5

      \[\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\]

   2. Taylor expanded around 0 0

      \[\leadsto \color{blue}{-1}\]

   if -1.9464050218174916e+152 < y < -1.0480049306425092e-161 or 2.184840803589229e-164 < y

   1. Initial program 0.1

      \[\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\]

   if -1.0480049306425092e-161 < y < 2.184840803589229e-164

   1. Initial program 30.6

      \[\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\]

   2. Taylor expanded around inf 16.3

      \[\leadsto \color{blue}{1}\]
3. Recombined 3 regimes into one program.

4. Final simplification 5.1

   \[\leadsto \begin{array}{l} \mathbf{if}\;y \le -1.946405021817491610626074253405329924501 \cdot 10^{152}:\\ \;\;\;\;-1\\ \mathbf{elif}\;y \le -1.048004930642509241748111685822132171198 \cdot 10^{-161}:\\ \;\;\;\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\\ \mathbf{elif}\;y \le 2.184840803589228861176620759693605020188 \cdot 10^{-164}:\\ \;\;\;\;1\\ \mathbf{else}:\\ \;\;\;\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\\ \end{array}\]

Reproduce

herbie shell --seed 2019294 
(FPCore (x y)
  :name "Kahan p9 Example"
  :precision binary64
  :pre (and (< 0.0 x 1) (< y 1))

  :herbie-target
  (if (< 0.5 (fabs (/ x y)) 2) (/ (* (- x y) (+ x y)) (+ (* x x) (* y y))) (- 1 (/ 2 (+ 1 (* (/ x y) (/ x y))))))

  (/ (* (- x y) (+ x y)) (+ (* x x) (* y y))))