Kahan p9 Example

Average Error: 20.7 → 5.0

Time: 7.2s

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 -6.9149027213328366 \cdot 10^{144}:\\ \;\;\;\;-1\\ \mathbf{elif}\;y \le -3.5965424677863614 \cdot 10^{-162} \lor \neg \left(y \le 5.56317243527390382 \cdot 10^{-165}\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 r67075 = x;
        double r67076 = y;
        double r67077 = r67075 - r67076;
        double r67078 = r67075 + r67076;
        double r67079 = r67077 * r67078;
        double r67080 = r67075 * r67075;
        double r67081 = r67076 * r67076;
        double r67082 = r67080 + r67081;
        double r67083 = r67079 / r67082;
        return r67083;
}

↓

double f(double x, double y) {
        double r67084 = y;
        double r67085 = -6.914902721332837e+144;
        bool r67086 = r67084 <= r67085;
        double r67087 = -1.0;
        double r67088 = -3.5965424677863614e-162;
        bool r67089 = r67084 <= r67088;
        double r67090 = 5.563172435273904e-165;
        bool r67091 = r67084 <= r67090;
        double r67092 = !r67091;
        bool r67093 = r67089 || r67092;
        double r67094 = x;
        double r67095 = r67094 - r67084;
        double r67096 = r67094 + r67084;
        double r67097 = r67095 * r67096;
        double r67098 = r67094 * r67094;
        double r67099 = r67084 * r67084;
        double r67100 = r67098 + r67099;
        double r67101 = r67097 / r67100;
        double r67102 = 1.0;
        double r67103 = r67093 ? r67101 : r67102;
        double r67104 = r67086 ? r67087 : r67103;
        return r67104;
}

Error

Bits error versus x

Bits error versus y

Target

Original	20.7
Target	0.0
Herbie	5.0

\[\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 < -6.914902721332837e+144

   1. Initial program 60.9

      \[\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 -6.914902721332837e+144 < y < -3.5965424677863614e-162 or 5.563172435273904e-165 < y

   1. Initial program 0.2

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

   if -3.5965424677863614e-162 < y < 5.563172435273904e-165

   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 15.6

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

4. Final simplification 5.0

   \[\leadsto \begin{array}{l} \mathbf{if}\;y \le -6.9149027213328366 \cdot 10^{144}:\\ \;\;\;\;-1\\ \mathbf{elif}\;y \le -3.5965424677863614 \cdot 10^{-162} \lor \neg \left(y \le 5.56317243527390382 \cdot 10^{-165}\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 2020043 
(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))))