bug323 (missed optimization)

Average Error: 59.5 → 57.2

Time: 8.2s

Precision: binary64

Cost: 45440

\[0 \leq x \land x \leq 0.5\]

Math

\[\cos^{-1} \left(1 - x\right) \]

↓

\[\mathsf{fma}\left({\left({\left(\pi \cdot 0.5\right)}^{0.3333333333333333}\right)}^{2}, \sqrt[3]{\pi \cdot 0.5}, -\sin^{-1} \left(1 - x\right)\right) \]

FPCore

(FPCore (x) :precision binary64 (acos (- 1.0 x)))

↓

(FPCore (x)
 :precision binary64
 (fma
  (pow (pow (* PI 0.5) 0.3333333333333333) 2.0)
  (cbrt (* PI 0.5))
  (- (asin (- 1.0 x)))))

C

double code(double x) {
	return acos((1.0 - x));
}

↓

double code(double x) {
	return fma(pow(pow((((double) M_PI) * 0.5), 0.3333333333333333), 2.0), cbrt((((double) M_PI) * 0.5)), -asin((1.0 - x)));
}

Julia

function code(x)
	return acos(Float64(1.0 - x))
end

↓

function code(x)
	return fma(((Float64(pi * 0.5) ^ 0.3333333333333333) ^ 2.0), cbrt(Float64(pi * 0.5)), Float64(-asin(Float64(1.0 - x))))
end

Wolfram

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

↓

code[x_] := N[(N[Power[N[Power[N[(Pi * 0.5), $MachinePrecision], 0.3333333333333333], $MachinePrecision], 2.0], $MachinePrecision] * N[Power[N[(Pi * 0.5), $MachinePrecision], 1/3], $MachinePrecision] + (-N[ArcSin[N[(1.0 - x), $MachinePrecision]], $MachinePrecision])), $MachinePrecision]

Target

Original	59.5
Target	0.0
Herbie	57.2

\[2 \cdot \sin^{-1} \left(\sqrt{\frac{x}{2}}\right) \]

Derivation

1. Initial program 59.5

   \[\cos^{-1} \left(1 - x\right) \]

2. Applied egg-rr 59.5

   \[\leadsto \color{blue}{\pi \cdot 0.5 + \left(-\sin^{-1} \left(1 - x\right)\right)} \]

3. Simplified 59.5

   \[\leadsto \color{blue}{\pi \cdot 0.5 - \sin^{-1} \left(1 - x\right)} \]
   Proof
   (-.f64 (*.f64 (PI.f64) 1/2) (asin.f64 (-.f64 1 x))): 0 points increase in error, 0 points decrease in error
   (Rewrite=> sub-neg_binary64 (+.f64 (*.f64 (PI.f64) 1/2) (neg.f64 (asin.f64 (-.f64 1 x))))): 2 points increase in error, 0 points decrease in error

4. Applied egg-rr 60.7

   \[\leadsto \color{blue}{\mathsf{fma}\left({\left(\sqrt[3]{\pi \cdot 0.5}\right)}^{2}, \sqrt[3]{\pi \cdot 0.5}, -\sin^{-1} \left(1 - x\right)\right)} \]

5. Applied egg-rr 57.2

   \[\leadsto \mathsf{fma}\left({\color{blue}{\left({\left(\pi \cdot 0.5\right)}^{0.3333333333333333}\right)}}^{2}, \sqrt[3]{\pi \cdot 0.5}, -\sin^{-1} \left(1 - x\right)\right) \]

6. Final simplification 57.2

   \[\leadsto \mathsf{fma}\left({\left({\left(\pi \cdot 0.5\right)}^{0.3333333333333333}\right)}^{2}, \sqrt[3]{\pi \cdot 0.5}, -\sin^{-1} \left(1 - x\right)\right) \]

Alternatives

Alternative 1
Error	57.3
Cost	26048

\[\pi \cdot 0.5 - {\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)}\right)}^{3} \]

Alternative 2
Error	57.3
Cost	26048

\[\pi \cdot 0.5 - {\left(\sqrt{\sin^{-1} \left(1 - x\right)}\right)}^{2} \]

Alternative 3
Error	59.5
Cost	19972

\[\begin{array}{l} t_0 := \cos^{-1} \left(1 - x\right) + -1\\ \mathbf{if}\;1 - x \leq 1:\\ \;\;\;\;1 + {\left(\sqrt[3]{t_0}\right)}^{3}\\ \mathbf{else}:\\ \;\;\;\;1 + \left|t_0\right|\\ \end{array} \]

Alternative 4
Error	57.9
Cost	19908

\[\begin{array}{l} t_0 := \cos^{-1} \left(1 - x\right)\\ t_1 := t_0 + -1\\ \mathbf{if}\;t_0 \leq 0:\\ \;\;\;\;1 + \left|t_1\right|\\ \mathbf{else}:\\ \;\;\;\;1 + \frac{1}{\frac{1}{t_1}}\\ \end{array} \]

Alternative 5
Error	57.9
Cost	13188

\[\begin{array}{l} t_0 := \cos^{-1} \left(1 - x\right)\\ \mathbf{if}\;x \leq 5.6 \cdot 10^{-17}:\\ \;\;\;\;\pi - t_0\\ \mathbf{else}:\\ \;\;\;\;1 + \frac{1}{\frac{1}{t_0 + -1}}\\ \end{array} \]

Alternative 6
Error	59.5
Cost	7104

\[1 + \frac{1}{\frac{1}{\cos^{-1} \left(1 - x\right) + -1}} \]

Alternative 7
Error	59.5
Cost	6592

\[\cos^{-1} \left(1 - x\right) \]

Reproduce

herbie shell --seed 2022343 
(FPCore (x)
  :name "bug323 (missed optimization)"
  :precision binary64
  :pre (and (<= 0.0 x) (<= x 0.5))

  :herbie-target
  (* 2.0 (asin (sqrt (/ x 2.0))))

  (acos (- 1.0 x)))