Kahan p9 Example

Average Error: 19.9 → 4.9

Time: 7.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 -1.4984271813117974 \cdot 10^{147}:\\ \;\;\;\;\sqrt[3]{-1}\\ \mathbf{elif}\;y \le -1.1106249786105219 \cdot 10^{-160} \lor \neg \left(y \le 1.0639458246816258 \cdot 10^{-162}\right):\\ \;\;\;\;\sqrt[3]{{\left(\frac{1}{\frac{x \cdot x + y \cdot y}{\left(x - y\right) \cdot \left(x + y\right)}}\right)}^{3}}\\ \mathbf{else}:\\ \;\;\;\;\sqrt[3]{1}\\ \end{array}\]

C

double f(double x, double y) {
        double r86186 = x;
        double r86187 = y;
        double r86188 = r86186 - r86187;
        double r86189 = r86186 + r86187;
        double r86190 = r86188 * r86189;
        double r86191 = r86186 * r86186;
        double r86192 = r86187 * r86187;
        double r86193 = r86191 + r86192;
        double r86194 = r86190 / r86193;
        return r86194;
}

↓

double f(double x, double y) {
        double r86195 = y;
        double r86196 = -1.4984271813117974e+147;
        bool r86197 = r86195 <= r86196;
        double r86198 = -1.0;
        double r86199 = cbrt(r86198);
        double r86200 = -1.1106249786105219e-160;
        bool r86201 = r86195 <= r86200;
        double r86202 = 1.0639458246816258e-162;
        bool r86203 = r86195 <= r86202;
        double r86204 = !r86203;
        bool r86205 = r86201 || r86204;
        double r86206 = 1.0;
        double r86207 = x;
        double r86208 = r86207 * r86207;
        double r86209 = r86195 * r86195;
        double r86210 = r86208 + r86209;
        double r86211 = r86207 - r86195;
        double r86212 = r86207 + r86195;
        double r86213 = r86211 * r86212;
        double r86214 = r86210 / r86213;
        double r86215 = r86206 / r86214;
        double r86216 = 3.0;
        double r86217 = pow(r86215, r86216);
        double r86218 = cbrt(r86217);
        double r86219 = cbrt(r86206);
        double r86220 = r86205 ? r86218 : r86219;
        double r86221 = r86197 ? r86199 : r86220;
        return r86221;
}

Error

Bits error versus x

Bits error versus y

Target

Original	19.9
Target	0.0
Herbie	4.9

\[\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.4984271813117974e+147

   1. Initial program 61.4

      \[\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 63.9

      \[\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 64.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 64.0

      \[\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 64.0

      \[\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 64.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 61.4

      \[\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 0 0

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

   if -1.4984271813117974e+147 < y < -1.1106249786105219e-160 or 1.0639458246816258e-162 < y

   1. Initial program 0.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 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.0

      \[\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 36.9

      \[\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.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. Using strategy rm

   10. Applied clear-num 0.1

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

   if -1.1106249786105219e-160 < y < 1.0639458246816258e-162

   1. Initial program 29.5

      \[\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 52.3

      \[\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 52.4

      \[\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 52.5

      \[\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.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 52.1

      \[\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.5

      \[\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 15.3

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

4. Final simplification 4.9

   \[\leadsto \begin{array}{l} \mathbf{if}\;y \le -1.4984271813117974 \cdot 10^{147}:\\ \;\;\;\;\sqrt[3]{-1}\\ \mathbf{elif}\;y \le -1.1106249786105219 \cdot 10^{-160} \lor \neg \left(y \le 1.0639458246816258 \cdot 10^{-162}\right):\\ \;\;\;\;\sqrt[3]{{\left(\frac{1}{\frac{x \cdot x + y \cdot y}{\left(x - y\right) \cdot \left(x + y\right)}}\right)}^{3}}\\ \mathbf{else}:\\ \;\;\;\;\sqrt[3]{1}\\ \end{array}\]

Reproduce

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