Kahan p9 Example

Average Error: 21.0 → 5.3

Time: 4.3s

Precision: 64

• Falling back on racket egraph because egg-herbie package not installed

\[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 -2.17401776624398403 \cdot 10^{153}:\\ \;\;\;\;-1\\ \mathbf{elif}\;y \le -2.03359079106827272 \cdot 10^{-162} \lor \neg \left(y \le 1.5900983176733966 \cdot 10^{-155}\right):\\ \;\;\;\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\\ \mathbf{else}:\\ \;\;\;\;1\\ \end{array}\]

C

double f(double x, double y) {
        double r91386 = x;
        double r91387 = y;
        double r91388 = r91386 - r91387;
        double r91389 = r91386 + r91387;
        double r91390 = r91388 * r91389;
        double r91391 = r91386 * r91386;
        double r91392 = r91387 * r91387;
        double r91393 = r91391 + r91392;
        double r91394 = r91390 / r91393;
        return r91394;
}

↓

double f(double x, double y) {
        double r91395 = y;
        double r91396 = -2.174017766243984e+153;
        bool r91397 = r91395 <= r91396;
        double r91398 = -1.0;
        double r91399 = -2.0335907910682727e-162;
        bool r91400 = r91395 <= r91399;
        double r91401 = 1.5900983176733966e-155;
        bool r91402 = r91395 <= r91401;
        double r91403 = !r91402;
        bool r91404 = r91400 || r91403;
        double r91405 = x;
        double r91406 = r91405 - r91395;
        double r91407 = r91405 + r91395;
        double r91408 = r91406 * r91407;
        double r91409 = r91405 * r91405;
        double r91410 = r91395 * r91395;
        double r91411 = r91409 + r91410;
        double r91412 = r91408 / r91411;
        double r91413 = 1.0;
        double r91414 = r91404 ? r91412 : r91413;
        double r91415 = r91397 ? r91398 : r91414;
        return r91415;
}

Error

Bits error versus x

Bits error versus y

Target

Original	21.0
Target	0.1
Herbie	5.3

\[\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 < -2.174017766243984e+153

   1. Initial program 63.6

      \[\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 -2.174017766243984e+153 < y < -2.0335907910682727e-162 or 1.5900983176733966e-155 < y

   1. Initial program 0.0

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

   if -2.0335907910682727e-162 < y < 1.5900983176733966e-155

   1. Initial program 30.7

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

   2. Taylor expanded around inf 16.6

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

4. Final simplification 5.3

   \[\leadsto \begin{array}{l} \mathbf{if}\;y \le -2.17401776624398403 \cdot 10^{153}:\\ \;\;\;\;-1\\ \mathbf{elif}\;y \le -2.03359079106827272 \cdot 10^{-162} \lor \neg \left(y \le 1.5900983176733966 \cdot 10^{-155}\right):\\ \;\;\;\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\\ \mathbf{else}:\\ \;\;\;\;1\\ \end{array}\]

Reproduce

herbie shell --seed 2020047 
(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))))