Kahan p9 Example

Average Error: 20.4 → 5.3

Time: 7.9s

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 -3.009912847037178514101182261968247974013 \cdot 10^{153}:\\ \;\;\;\;-1\\ \mathbf{elif}\;y \le -3.748181836506679035654613993854921642505 \cdot 10^{-150} \lor \neg \left(y \le 6.410512806354982094014968147888518178732 \cdot 10^{-156}\right):\\ \;\;\;\;\sqrt[3]{{\left(\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\right)}^{3}}\\ \mathbf{else}:\\ \;\;\;\;-\sqrt[3]{-1}\\ \end{array}\]

C

double f(double x, double y) {
        double r102411 = x;
        double r102412 = y;
        double r102413 = r102411 - r102412;
        double r102414 = r102411 + r102412;
        double r102415 = r102413 * r102414;
        double r102416 = r102411 * r102411;
        double r102417 = r102412 * r102412;
        double r102418 = r102416 + r102417;
        double r102419 = r102415 / r102418;
        return r102419;
}

↓

double f(double x, double y) {
        double r102420 = y;
        double r102421 = -3.0099128470371785e+153;
        bool r102422 = r102420 <= r102421;
        double r102423 = -1.0;
        double r102424 = -3.748181836506679e-150;
        bool r102425 = r102420 <= r102424;
        double r102426 = 6.410512806354982e-156;
        bool r102427 = r102420 <= r102426;
        double r102428 = !r102427;
        bool r102429 = r102425 || r102428;
        double r102430 = x;
        double r102431 = r102430 - r102420;
        double r102432 = r102430 + r102420;
        double r102433 = r102431 * r102432;
        double r102434 = r102430 * r102430;
        double r102435 = r102420 * r102420;
        double r102436 = r102434 + r102435;
        double r102437 = r102433 / r102436;
        double r102438 = 3.0;
        double r102439 = pow(r102437, r102438);
        double r102440 = cbrt(r102439);
        double r102441 = cbrt(r102423);
        double r102442 = -r102441;
        double r102443 = r102429 ? r102440 : r102442;
        double r102444 = r102422 ? r102423 : r102443;
        return r102444;
}

Error

Bits error versus x

Bits error versus y

Target

Original	20.4
Target	0.0
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 < -3.0099128470371785e+153

   1. Initial program 63.7

      \[\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 -3.0099128470371785e+153 < y < -3.748181836506679e-150 or 6.410512806354982e-156 < y

   1. Initial program 0.0

      \[\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\]
   2. Using strategy rm

   3. Applied add-cbrt-cube 37.0

      \[\leadsto \frac{\left(x - y\right) \cdot \left(x + y\right)}{\color{blue}{\sqrt[3]{\left(\left(x \cdot x + y \cdot y\right) \cdot \left(x \cdot x + y \cdot y\right)\right) \cdot \left(x \cdot x + y \cdot y\right)}}}\]

   4. Applied add-cbrt-cube 37.3

      \[\leadsto \frac{\left(x - y\right) \cdot \color{blue}{\sqrt[3]{\left(\left(x + y\right) \cdot \left(x + y\right)\right) \cdot \left(x + y\right)}}}{\sqrt[3]{\left(\left(x \cdot x + y \cdot y\right) \cdot \left(x \cdot x + y \cdot y\right)\right) \cdot \left(x \cdot x + y \cdot y\right)}}\]

   5. Applied add-cbrt-cube 37.4

      \[\leadsto \frac{\color{blue}{\sqrt[3]{\left(\left(x - y\right) \cdot \left(x - y\right)\right) \cdot \left(x - y\right)}} \cdot \sqrt[3]{\left(\left(x + y\right) \cdot \left(x + y\right)\right) \cdot \left(x + y\right)}}{\sqrt[3]{\left(\left(x \cdot x + y \cdot y\right) \cdot \left(x \cdot x + y \cdot y\right)\right) \cdot \left(x \cdot x + y \cdot y\right)}}\]

   6. Applied cbrt-unprod 37.1

      \[\leadsto \frac{\color{blue}{\sqrt[3]{\left(\left(\left(x - y\right) \cdot \left(x - y\right)\right) \cdot \left(x - y\right)\right) \cdot \left(\left(\left(x + y\right) \cdot \left(x + y\right)\right) \cdot \left(x + y\right)\right)}}}{\sqrt[3]{\left(\left(x \cdot x + y \cdot y\right) \cdot \left(x \cdot x + y \cdot y\right)\right) \cdot \left(x \cdot x + y \cdot y\right)}}\]

   7. Applied cbrt-undiv 37.0

      \[\leadsto \color{blue}{\sqrt[3]{\frac{\left(\left(\left(x - y\right) \cdot \left(x - y\right)\right) \cdot \left(x - y\right)\right) \cdot \left(\left(\left(x + y\right) \cdot \left(x + y\right)\right) \cdot \left(x + y\right)\right)}{\left(\left(x \cdot x + y \cdot y\right) \cdot \left(x \cdot x + y \cdot y\right)\right) \cdot \left(x \cdot x + y \cdot y\right)}}}\]

   8. Simplified 0.0

      \[\leadsto \sqrt[3]{\color{blue}{{\left(\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\right)}^{3}}}\]

   if -3.748181836506679e-150 < y < 6.410512806354982e-156

   1. Initial program 29.1

      \[\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\]
   2. Using strategy rm

   3. Applied add-cbrt-cube 53.0

      \[\leadsto \frac{\left(x - y\right) \cdot \left(x + y\right)}{\color{blue}{\sqrt[3]{\left(\left(x \cdot x + y \cdot y\right) \cdot \left(x \cdot x + y \cdot y\right)\right) \cdot \left(x \cdot x + y \cdot y\right)}}}\]

   4. Applied add-cbrt-cube 53.0

      \[\leadsto \frac{\left(x - y\right) \cdot \color{blue}{\sqrt[3]{\left(\left(x + y\right) \cdot \left(x + y\right)\right) \cdot \left(x + y\right)}}}{\sqrt[3]{\left(\left(x \cdot x + y \cdot y\right) \cdot \left(x \cdot x + y \cdot y\right)\right) \cdot \left(x \cdot x + y \cdot y\right)}}\]

   5. Applied add-cbrt-cube 53.1

      \[\leadsto \frac{\color{blue}{\sqrt[3]{\left(\left(x - y\right) \cdot \left(x - y\right)\right) \cdot \left(x - y\right)}} \cdot \sqrt[3]{\left(\left(x + y\right) \cdot \left(x + y\right)\right) \cdot \left(x + y\right)}}{\sqrt[3]{\left(\left(x \cdot x + y \cdot y\right) \cdot \left(x \cdot x + y \cdot y\right)\right) \cdot \left(x \cdot x + y \cdot y\right)}}\]

   6. Applied cbrt-unprod 52.7

      \[\leadsto \frac{\color{blue}{\sqrt[3]{\left(\left(\left(x - y\right) \cdot \left(x - y\right)\right) \cdot \left(x - y\right)\right) \cdot \left(\left(\left(x + y\right) \cdot \left(x + y\right)\right) \cdot \left(x + y\right)\right)}}}{\sqrt[3]{\left(\left(x \cdot x + y \cdot y\right) \cdot \left(x \cdot x + y \cdot y\right)\right) \cdot \left(x \cdot x + y \cdot y\right)}}\]

   7. Applied cbrt-undiv 52.7

      \[\leadsto \color{blue}{\sqrt[3]{\frac{\left(\left(\left(x - y\right) \cdot \left(x - y\right)\right) \cdot \left(x - y\right)\right) \cdot \left(\left(\left(x + y\right) \cdot \left(x + y\right)\right) \cdot \left(x + y\right)\right)}{\left(\left(x \cdot x + y \cdot y\right) \cdot \left(x \cdot x + y \cdot y\right)\right) \cdot \left(x \cdot x + y \cdot y\right)}}}\]

   8. Simplified 29.1

      \[\leadsto \sqrt[3]{\color{blue}{{\left(\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\right)}^{3}}}\]

   9. Taylor expanded around -inf 16.1

      \[\leadsto \color{blue}{-1 \cdot \sqrt[3]{-1}}\]

   10. Simplified 16.1

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

4. Final simplification 5.3

   \[\leadsto \begin{array}{l} \mathbf{if}\;y \le -3.009912847037178514101182261968247974013 \cdot 10^{153}:\\ \;\;\;\;-1\\ \mathbf{elif}\;y \le -3.748181836506679035654613993854921642505 \cdot 10^{-150} \lor \neg \left(y \le 6.410512806354982094014968147888518178732 \cdot 10^{-156}\right):\\ \;\;\;\;\sqrt[3]{{\left(\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\right)}^{3}}\\ \mathbf{else}:\\ \;\;\;\;-\sqrt[3]{-1}\\ \end{array}\]

Reproduce

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