bug500 (missed optimization)

Average Error: 19.4 → 0.6

Time: 15.2s

Precision: binary64

Cost: 33224

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

Math

\[\sin x - x \]

↓

\[\begin{array}{l} t_0 := \sin x - x\\ \mathbf{if}\;t_0 \leq -0.01:\\ \;\;\;\;t_0\\ \mathbf{elif}\;t_0 \leq 5 \cdot 10^{-24}:\\ \;\;\;\;\frac{\frac{\mathsf{fma}\left(-0.16666666666666666, {x}^{3}, 0.008333333333333333 \cdot {x}^{5}\right)}{0.3333333333333333}}{3}\\ \mathbf{else}:\\ \;\;\;\;t_0\\ \end{array} \]

FPCore

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

↓

(FPCore (x)
 :precision binary64
 (let* ((t_0 (- (sin x) x)))
   (if (<= t_0 -0.01)
     t_0
     (if (<= t_0 5e-24)
       (/
        (/
         (fma
          -0.16666666666666666
          (pow x 3.0)
          (* 0.008333333333333333 (pow x 5.0)))
         0.3333333333333333)
        3.0)
       t_0))))

C

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

↓

double code(double x) {
	double t_0 = sin(x) - x;
	double tmp;
	if (t_0 <= -0.01) {
		tmp = t_0;
	} else if (t_0 <= 5e-24) {
		tmp = (fma(-0.16666666666666666, pow(x, 3.0), (0.008333333333333333 * pow(x, 5.0))) / 0.3333333333333333) / 3.0;
	} else {
		tmp = t_0;
	}
	return tmp;
}

Julia

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

↓

function code(x)
	t_0 = Float64(sin(x) - x)
	tmp = 0.0
	if (t_0 <= -0.01)
		tmp = t_0;
	elseif (t_0 <= 5e-24)
		tmp = Float64(Float64(fma(-0.16666666666666666, (x ^ 3.0), Float64(0.008333333333333333 * (x ^ 5.0))) / 0.3333333333333333) / 3.0);
	else
		tmp = t_0;
	end
	return tmp
end

Wolfram

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

↓

code[x_] := Block[{t$95$0 = N[(N[Sin[x], $MachinePrecision] - x), $MachinePrecision]}, If[LessEqual[t$95$0, -0.01], t$95$0, If[LessEqual[t$95$0, 5e-24], N[(N[(N[(-0.16666666666666666 * N[Power[x, 3.0], $MachinePrecision] + N[(0.008333333333333333 * N[Power[x, 5.0], $MachinePrecision]), $MachinePrecision]), $MachinePrecision] / 0.3333333333333333), $MachinePrecision] / 3.0), $MachinePrecision], t$95$0]]]

Target

Original	19.4
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. Split input into 2 regimes

2. if (-.f64 (sin.f64 x) x) < -0.0100000000000000002 or 4.9999999999999998e-24 < (-.f64 (sin.f64 x) x)

   1. Initial program 14.5

      \[\sin x - x \]

   if -0.0100000000000000002 < (-.f64 (sin.f64 x) x) < 4.9999999999999998e-24

   1. Initial program 19.5

      \[\sin x - x \]

   2. Taylor expanded in x around 0 0.2

      \[\leadsto \color{blue}{-0.16666666666666666 \cdot {x}^{3} + 0.008333333333333333 \cdot {x}^{5}} \]

   3. Applied egg-rr 0.6

      \[\leadsto \color{blue}{{\left(\sqrt[3]{\mathsf{fma}\left(-0.16666666666666666, {x}^{3}, 0.008333333333333333 \cdot {x}^{5}\right)}\right)}^{3}} \]

   4. Applied egg-rr 0.2

      \[\leadsto \color{blue}{\frac{\frac{\mathsf{fma}\left(-0.16666666666666666, {x}^{3}, 0.008333333333333333 \cdot {x}^{5}\right)}{0.3333333333333333}}{3}} \]
3. Recombined 2 regimes into one program.

Alternatives

Alternative 1
Error	0.6
Cost	27208

\[\begin{array}{l} t_0 := \sin x - x\\ t_1 := 0.008333333333333333 \cdot {x}^{5}\\ \mathbf{if}\;t_0 \leq -0.01:\\ \;\;\;\;t_0\\ \mathbf{elif}\;t_0 \leq 0:\\ \;\;\;\;-0.16666666666666666 \cdot {x}^{3} + t_1\\ \mathbf{else}:\\ \;\;\;\;\left(x \cdot x\right) \cdot \left(-0.16666666666666666 \cdot x\right) + \left(t_1 + -0.0001984126984126984 \cdot {x}^{7}\right)\\ \end{array} \]

Alternative 2
Error	0.7
Cost	13828

\[\begin{array}{l} t_0 := \sin x - x\\ \mathbf{if}\;t_0 \leq -0.01:\\ \;\;\;\;t_0\\ \mathbf{else}:\\ \;\;\;\;\left(x \cdot x\right) \cdot \left(-0.16666666666666666 \cdot x\right) + 0.008333333333333333 \cdot {x}^{5}\\ \end{array} \]

Alternative 3
Error	0.6
Cost	13508

\[\begin{array}{l} \mathbf{if}\;x \leq 0.009:\\ \;\;\;\;-0.16666666666666666 \cdot {x}^{3} + 0.008333333333333333 \cdot {x}^{5}\\ \mathbf{else}:\\ \;\;\;\;\sin x - x\\ \end{array} \]

Alternative 4
Error	1.0
Cost	13444

\[\begin{array}{l} t_0 := \sin x - x\\ \mathbf{if}\;t_0 \leq -0.01:\\ \;\;\;\;t_0\\ \mathbf{else}:\\ \;\;\;\;\frac{-0.5 \cdot {x}^{3}}{3}\\ \end{array} \]

Alternative 5
Error	1.0
Cost	13316

\[\begin{array}{l} t_0 := \sin x - x\\ \mathbf{if}\;t_0 \leq -0.01:\\ \;\;\;\;t_0\\ \mathbf{else}:\\ \;\;\;\;-0.16666666666666666 \cdot {x}^{3}\\ \end{array} \]

Alternative 6
Error	1.0
Cost	13252

\[\begin{array}{l} t_0 := \sin x - x\\ \mathbf{if}\;t_0 \leq -0.01:\\ \;\;\;\;t_0\\ \mathbf{else}:\\ \;\;\;\;\left(x \cdot x\right) \cdot \left(-0.16666666666666666 \cdot x\right)\\ \end{array} \]

Alternative 7
Error	1.3
Cost	448

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

Alternative 8
Error	1.3
Cost	448

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

Alternative 9
Error	59.8
Cost	128

\[-x \]

Reproduce

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