bug500 (missed optimization)

Average Error: 19.5 → 0.6

Time: 7.8s

Precision: binary64

Cost: 20480

\[-1000 < x \land x < 1000\]

Math

\[\sin x - x \]

↓

\[\frac{x + \sin x}{\left(0.4 + \mathsf{fma}\left(-0.0002698412698412698, {x}^{4}, -0.015714285714285715 \cdot \left(x \cdot x\right)\right)\right) + \frac{-12}{x \cdot x}} \]

FPCore

(FPCore (x) :precision binary64 (- (sin x) x))

↓

(FPCore (x)
 :precision binary64
 (/
  (+ x (sin x))
  (+
   (+
    0.4
    (fma -0.0002698412698412698 (pow x 4.0) (* -0.015714285714285715 (* x x))))
   (/ -12.0 (* x x)))))

C

double code(double x) {
	return sin(x) - x;
}

↓

double code(double x) {
	return (x + sin(x)) / ((0.4 + fma(-0.0002698412698412698, pow(x, 4.0), (-0.015714285714285715 * (x * x)))) + (-12.0 / (x * x)));
}

Julia

function code(x)
	return Float64(sin(x) - x)
end

↓

function code(x)
	return Float64(Float64(x + sin(x)) / Float64(Float64(0.4 + fma(-0.0002698412698412698, (x ^ 4.0), Float64(-0.015714285714285715 * Float64(x * x)))) + Float64(-12.0 / Float64(x * x))))
end

Wolfram

code[x_] := N[(N[Sin[x], $MachinePrecision] - x), $MachinePrecision]

↓

code[x_] := N[(N[(x + N[Sin[x], $MachinePrecision]), $MachinePrecision] / N[(N[(0.4 + N[(-0.0002698412698412698 * N[Power[x, 4.0], $MachinePrecision] + N[(-0.015714285714285715 * N[(x * x), $MachinePrecision]), $MachinePrecision]), $MachinePrecision]), $MachinePrecision] + N[(-12.0 / N[(x * x), $MachinePrecision]), $MachinePrecision]), $MachinePrecision]), $MachinePrecision]

Target

Original	19.5
Target	0.1
Herbie	0.6

\[\begin{array}{l} \mathbf{if}\;\left|x\right| < 0.07:\\ \;\;\;\;-\left(\left(\frac{{x}^{3}}{6} - \frac{{x}^{5}}{120}\right) + \frac{{x}^{7}}{5040}\right)\\ \mathbf{else}:\\ \;\;\;\;\sin x - x\\ \end{array} \]

Derivation

1. Initial program 19.5

   \[\sin x - x \]

2. Applied egg-rr 19.5

   \[\leadsto \color{blue}{{\left(\sqrt[3]{\sin x - x}\right)}^{3}} \]

3. Applied egg-rr 20.2

   \[\leadsto {\color{blue}{\left({\left(\sqrt{\sin x - x}\right)}^{0.3333333333333333} \cdot {\left(\sqrt{\sin x - x}\right)}^{0.3333333333333333}\right)}}^{3} \]

4. Simplified 20.2

   \[\leadsto {\color{blue}{\left(\sqrt[3]{\sqrt{\sin x - x}} \cdot \sqrt[3]{\sqrt{\sin x - x}}\right)}}^{3} \]
   Proof

   [Start] 20.2	\[ {\left({\left(\sqrt{\sin x - x}\right)}^{0.3333333333333333} \cdot {\left(\sqrt{\sin x - x}\right)}^{0.3333333333333333}\right)}^{3} \]
   unpow1/3 [=>] 20.2	\[ {\left(\color{blue}{\sqrt[3]{\sqrt{\sin x - x}}} \cdot {\left(\sqrt{\sin x - x}\right)}^{0.3333333333333333}\right)}^{3} \]
   unpow1/3 [=>] 20.2	\[ {\left(\sqrt[3]{\sqrt{\sin x - x}} \cdot \color{blue}{\sqrt[3]{\sqrt{\sin x - x}}}\right)}^{3} \]

5. Applied egg-rr 19.5

   \[\leadsto \color{blue}{\frac{x + \sin x}{\frac{x + \sin x}{\sin x - x}}} \]

6. Taylor expanded in x around 0 0.7

   \[\leadsto \frac{x + \sin x}{\color{blue}{\left(0.4 + \left(-0.0002698412698412698 \cdot {x}^{4} + -0.015714285714285715 \cdot {x}^{2}\right)\right) - 12 \cdot \frac{1}{{x}^{2}}}} \]

7. Simplified 0.6

   \[\leadsto \frac{x + \sin x}{\color{blue}{\left(0.4 + \mathsf{fma}\left(-0.0002698412698412698, {x}^{4}, -0.015714285714285715 \cdot \left(x \cdot x\right)\right)\right) - \frac{12}{x \cdot x}}} \]
   Proof

   [Start] 0.7	\[ \frac{x + \sin x}{\left(0.4 + \left(-0.0002698412698412698 \cdot {x}^{4} + -0.015714285714285715 \cdot {x}^{2}\right)\right) - 12 \cdot \frac{1}{{x}^{2}}} \]
   fma-def [=>] 0.7	\[ \frac{x + \sin x}{\left(0.4 + \color{blue}{\mathsf{fma}\left(-0.0002698412698412698, {x}^{4}, -0.015714285714285715 \cdot {x}^{2}\right)}\right) - 12 \cdot \frac{1}{{x}^{2}}} \]
   unpow2 [=>] 0.7	\[ \frac{x + \sin x}{\left(0.4 + \mathsf{fma}\left(-0.0002698412698412698, {x}^{4}, -0.015714285714285715 \cdot \color{blue}{\left(x \cdot x\right)}\right)\right) - 12 \cdot \frac{1}{{x}^{2}}} \]
   associate-*r/ [=>] 0.6	\[ \frac{x + \sin x}{\left(0.4 + \mathsf{fma}\left(-0.0002698412698412698, {x}^{4}, -0.015714285714285715 \cdot \left(x \cdot x\right)\right)\right) - \color{blue}{\frac{12 \cdot 1}{{x}^{2}}}} \]
   metadata-eval [=>] 0.6	\[ \frac{x + \sin x}{\left(0.4 + \mathsf{fma}\left(-0.0002698412698412698, {x}^{4}, -0.015714285714285715 \cdot \left(x \cdot x\right)\right)\right) - \frac{\color{blue}{12}}{{x}^{2}}} \]
   unpow2 [=>] 0.6	\[ \frac{x + \sin x}{\left(0.4 + \mathsf{fma}\left(-0.0002698412698412698, {x}^{4}, -0.015714285714285715 \cdot \left(x \cdot x\right)\right)\right) - \frac{12}{\color{blue}{x \cdot x}}} \]

8. Final simplification 0.6

   \[\leadsto \frac{x + \sin x}{\left(0.4 + \mathsf{fma}\left(-0.0002698412698412698, {x}^{4}, -0.015714285714285715 \cdot \left(x \cdot x\right)\right)\right) + \frac{-12}{x \cdot x}} \]

Alternatives

Alternative 1
Error	0.9
Cost	7104

\[\frac{x + \sin x}{0.4 + \frac{\frac{-12}{x}}{x}} \]

Alternative 2
Error	1.1
Cost	6976

\[\frac{x + \sin x}{\frac{-12}{x \cdot x}} \]

Alternative 3
Error	1.1
Cost	6976

\[\frac{x + \sin x}{\frac{\frac{-12}{x}}{x}} \]

Alternative 4
Error	1.2
Cost	6656

\[-0.16666666666666666 \cdot {x}^{3} \]

Alternative 5
Error	1.2
Cost	448

\[x \cdot \left(\left(x \cdot x\right) \cdot -0.16666666666666666\right) \]

Alternative 6
Error	59.8
Cost	128

\[-x \]

Reproduce

herbie shell --seed 2023057 
(FPCore (x)
  :name "bug500 (missed optimization)"
  :precision binary64
  :pre (and (< -1000.0 x) (< x 1000.0))

  :herbie-target
  (if (< (fabs x) 0.07) (- (+ (- (/ (pow x 3.0) 6.0) (/ (pow x 5.0) 120.0)) (/ (pow x 7.0) 5040.0))) (- (sin x) x))

  (- (sin x) x))