bug323 (missed optimization)

Percentage Accurate: 7.1% → 10.6%

Time: 11.8s

Precision: binary64

Cost: 182336

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

Math

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

↓

\[\begin{array}{l} t_0 := \sin^{-1} \left(1 - x\right)\\ t_1 := {\left(\sqrt[3]{t_0}\right)}^{2}\\ t_2 := {t_0}^{0.16666666666666666}\\ t_3 := -t_2\\ t_4 := t_2 \cdot t_1\\ \mathsf{fma}\left(\sqrt[3]{{\pi}^{2} \cdot 0.25}, \sqrt[3]{\pi \cdot 0.5}, t_2 \cdot \left(t_1 \cdot t_3\right)\right) + \mathsf{fma}\left(t_3, t_4, t_2 \cdot t_4\right) \end{array} \]

FPCore

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

↓

(FPCore (x)
 :precision binary64
 (let* ((t_0 (asin (- 1.0 x)))
        (t_1 (pow (cbrt t_0) 2.0))
        (t_2 (pow t_0 0.16666666666666666))
        (t_3 (- t_2))
        (t_4 (* t_2 t_1)))
   (+
    (fma (cbrt (* (pow PI 2.0) 0.25)) (cbrt (* PI 0.5)) (* t_2 (* t_1 t_3)))
    (fma t_3 t_4 (* t_2 t_4)))))

C

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

↓

double code(double x) {
	double t_0 = asin((1.0 - x));
	double t_1 = pow(cbrt(t_0), 2.0);
	double t_2 = pow(t_0, 0.16666666666666666);
	double t_3 = -t_2;
	double t_4 = t_2 * t_1;
	return fma(cbrt((pow(((double) M_PI), 2.0) * 0.25)), cbrt((((double) M_PI) * 0.5)), (t_2 * (t_1 * t_3))) + fma(t_3, t_4, (t_2 * t_4));
}

Julia

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

↓

function code(x)
	t_0 = asin(Float64(1.0 - x))
	t_1 = cbrt(t_0) ^ 2.0
	t_2 = t_0 ^ 0.16666666666666666
	t_3 = Float64(-t_2)
	t_4 = Float64(t_2 * t_1)
	return Float64(fma(cbrt(Float64((pi ^ 2.0) * 0.25)), cbrt(Float64(pi * 0.5)), Float64(t_2 * Float64(t_1 * t_3))) + fma(t_3, t_4, Float64(t_2 * t_4)))
end

Wolfram

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

↓

code[x_] := Block[{t$95$0 = N[ArcSin[N[(1.0 - x), $MachinePrecision]], $MachinePrecision]}, Block[{t$95$1 = N[Power[N[Power[t$95$0, 1/3], $MachinePrecision], 2.0], $MachinePrecision]}, Block[{t$95$2 = N[Power[t$95$0, 0.16666666666666666], $MachinePrecision]}, Block[{t$95$3 = (-t$95$2)}, Block[{t$95$4 = N[(t$95$2 * t$95$1), $MachinePrecision]}, N[(N[(N[Power[N[(N[Power[Pi, 2.0], $MachinePrecision] * 0.25), $MachinePrecision], 1/3], $MachinePrecision] * N[Power[N[(Pi * 0.5), $MachinePrecision], 1/3], $MachinePrecision] + N[(t$95$2 * N[(t$95$1 * t$95$3), $MachinePrecision]), $MachinePrecision]), $MachinePrecision] + N[(t$95$3 * t$95$4 + N[(t$95$2 * t$95$4), $MachinePrecision]), $MachinePrecision]), $MachinePrecision]]]]]]

Target

Original	7.1%
Target	100.0%
Herbie	10.6%

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

Derivation

1. Initial program 7.3%

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

2. Applied egg-rr 7.3%

   \[\leadsto \color{blue}{\left(1 + \cos^{-1} \left(1 - x\right)\right) - 1} \]
   Step-by-step derivation

   [Start] 7.3	\[ \cos^{-1} \left(1 - x\right) \]
   expm1-log1p-u [=>] 7.3	\[ \color{blue}{\mathsf{expm1}\left(\mathsf{log1p}\left(\cos^{-1} \left(1 - x\right)\right)\right)} \]
   expm1-udef [=>] 7.3	\[ \color{blue}{e^{\mathsf{log1p}\left(\cos^{-1} \left(1 - x\right)\right)} - 1} \]
   log1p-udef [=>] 7.3	\[ e^{\color{blue}{\log \left(1 + \cos^{-1} \left(1 - x\right)\right)}} - 1 \]
   add-exp-log [<=] 7.3	\[ \color{blue}{\left(1 + \cos^{-1} \left(1 - x\right)\right)} - 1 \]

3. Applied egg-rr 5.5%

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

   [Start] 7.3	\[ \left(1 + \cos^{-1} \left(1 - x\right)\right) - 1 \]
   add-exp-log [=>] 7.3	\[ \color{blue}{e^{\log \left(1 + \cos^{-1} \left(1 - x\right)\right)}} - 1 \]
   log1p-udef [<=] 7.3	\[ e^{\color{blue}{\mathsf{log1p}\left(\cos^{-1} \left(1 - x\right)\right)}} - 1 \]
   expm1-udef [<=] 7.3	\[ \color{blue}{\mathsf{expm1}\left(\mathsf{log1p}\left(\cos^{-1} \left(1 - x\right)\right)\right)} \]
   expm1-log1p-u [<=] 7.3	\[ \color{blue}{\cos^{-1} \left(1 - x\right)} \]
   acos-asin [=>] 7.3	\[ \color{blue}{\frac{\pi}{2} - \sin^{-1} \left(1 - x\right)} \]
   add-sqr-sqrt [=>] 5.5	\[ \color{blue}{\sqrt{\frac{\pi}{2}} \cdot \sqrt{\frac{\pi}{2}}} - \sin^{-1} \left(1 - x\right) \]
   fma-neg [=>] 5.5	\[ \color{blue}{\mathsf{fma}\left(\sqrt{\frac{\pi}{2}}, \sqrt{\frac{\pi}{2}}, -\sin^{-1} \left(1 - x\right)\right)} \]
   div-inv [=>] 5.5	\[ \mathsf{fma}\left(\sqrt{\color{blue}{\pi \cdot \frac{1}{2}}}, \sqrt{\frac{\pi}{2}}, -\sin^{-1} \left(1 - x\right)\right) \]
   metadata-eval [=>] 5.5	\[ \mathsf{fma}\left(\sqrt{\pi \cdot \color{blue}{0.5}}, \sqrt{\frac{\pi}{2}}, -\sin^{-1} \left(1 - x\right)\right) \]
   div-inv [=>] 5.5	\[ \mathsf{fma}\left(\sqrt{\pi \cdot 0.5}, \sqrt{\color{blue}{\pi \cdot \frac{1}{2}}}, -\sin^{-1} \left(1 - x\right)\right) \]
   metadata-eval [=>] 5.5	\[ \mathsf{fma}\left(\sqrt{\pi \cdot 0.5}, \sqrt{\pi \cdot \color{blue}{0.5}}, -\sin^{-1} \left(1 - x\right)\right) \]

4. Applied egg-rr 10.8%

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

   [Start] 5.5	\[ \mathsf{fma}\left(\sqrt{\pi \cdot 0.5}, \sqrt{\pi \cdot 0.5}, -\sin^{-1} \left(1 - x\right)\right) \]
   add-cube-cbrt [=>] 10.8	\[ \mathsf{fma}\left(\sqrt{\pi \cdot 0.5}, \sqrt{\pi \cdot 0.5}, -\color{blue}{\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)} \cdot \sqrt[3]{\sin^{-1} \left(1 - x\right)}\right) \cdot \sqrt[3]{\sin^{-1} \left(1 - x\right)}}\right) \]
   pow3 [=>] 10.8	\[ \mathsf{fma}\left(\sqrt{\pi \cdot 0.5}, \sqrt{\pi \cdot 0.5}, -\color{blue}{{\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)}\right)}^{3}}\right) \]

5. Applied egg-rr 10.8%

   \[\leadsto \color{blue}{\mathsf{fma}\left(\sqrt[3]{{\pi}^{2} \cdot 0.25}, \sqrt[3]{\pi \cdot 0.5}, -{\sin^{-1} \left(1 - x\right)}^{0.16666666666666666} \cdot \left({\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)}\right)}^{2} \cdot {\sin^{-1} \left(1 - x\right)}^{0.16666666666666666}\right)\right) + \mathsf{fma}\left(-{\sin^{-1} \left(1 - x\right)}^{0.16666666666666666}, {\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)}\right)}^{2} \cdot {\sin^{-1} \left(1 - x\right)}^{0.16666666666666666}, {\sin^{-1} \left(1 - x\right)}^{0.16666666666666666} \cdot \left({\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)}\right)}^{2} \cdot {\sin^{-1} \left(1 - x\right)}^{0.16666666666666666}\right)\right)} \]
   Step-by-step derivation

   [Start] 10.8	\[ \mathsf{fma}\left(\sqrt{\pi \cdot 0.5}, \sqrt{\pi \cdot 0.5}, -{\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)}\right)}^{3}\right) \]
   fma-neg [<=] 10.8	\[ \color{blue}{\sqrt{\pi \cdot 0.5} \cdot \sqrt{\pi \cdot 0.5} - {\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)}\right)}^{3}} \]
   add-sqr-sqrt [<=] 10.8	\[ \color{blue}{\pi \cdot 0.5} - {\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)}\right)}^{3} \]
   add-cube-cbrt [=>] 7.3	\[ \color{blue}{\left(\sqrt[3]{\pi \cdot 0.5} \cdot \sqrt[3]{\pi \cdot 0.5}\right) \cdot \sqrt[3]{\pi \cdot 0.5}} - {\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)}\right)}^{3} \]
   unpow3 [=>] 7.3	\[ \left(\sqrt[3]{\pi \cdot 0.5} \cdot \sqrt[3]{\pi \cdot 0.5}\right) \cdot \sqrt[3]{\pi \cdot 0.5} - \color{blue}{\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)} \cdot \sqrt[3]{\sin^{-1} \left(1 - x\right)}\right) \cdot \sqrt[3]{\sin^{-1} \left(1 - x\right)}} \]
   add-sqr-sqrt [=>] 7.3	\[ \left(\sqrt[3]{\pi \cdot 0.5} \cdot \sqrt[3]{\pi \cdot 0.5}\right) \cdot \sqrt[3]{\pi \cdot 0.5} - \left(\sqrt[3]{\sin^{-1} \left(1 - x\right)} \cdot \sqrt[3]{\sin^{-1} \left(1 - x\right)}\right) \cdot \color{blue}{\left(\sqrt{\sqrt[3]{\sin^{-1} \left(1 - x\right)}} \cdot \sqrt{\sqrt[3]{\sin^{-1} \left(1 - x\right)}}\right)} \]
   associate-*r* [=>] 10.8	\[ \left(\sqrt[3]{\pi \cdot 0.5} \cdot \sqrt[3]{\pi \cdot 0.5}\right) \cdot \sqrt[3]{\pi \cdot 0.5} - \color{blue}{\left(\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)} \cdot \sqrt[3]{\sin^{-1} \left(1 - x\right)}\right) \cdot \sqrt{\sqrt[3]{\sin^{-1} \left(1 - x\right)}}\right) \cdot \sqrt{\sqrt[3]{\sin^{-1} \left(1 - x\right)}}} \]
   prod-diff [=>] 10.8	\[ \color{blue}{\mathsf{fma}\left(\sqrt[3]{\pi \cdot 0.5} \cdot \sqrt[3]{\pi \cdot 0.5}, \sqrt[3]{\pi \cdot 0.5}, -\sqrt{\sqrt[3]{\sin^{-1} \left(1 - x\right)}} \cdot \left(\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)} \cdot \sqrt[3]{\sin^{-1} \left(1 - x\right)}\right) \cdot \sqrt{\sqrt[3]{\sin^{-1} \left(1 - x\right)}}\right)\right) + \mathsf{fma}\left(-\sqrt{\sqrt[3]{\sin^{-1} \left(1 - x\right)}}, \left(\sqrt[3]{\sin^{-1} \left(1 - x\right)} \cdot \sqrt[3]{\sin^{-1} \left(1 - x\right)}\right) \cdot \sqrt{\sqrt[3]{\sin^{-1} \left(1 - x\right)}}, \sqrt{\sqrt[3]{\sin^{-1} \left(1 - x\right)}} \cdot \left(\left(\sqrt[3]{\sin^{-1} \left(1 - x\right)} \cdot \sqrt[3]{\sin^{-1} \left(1 - x\right)}\right) \cdot \sqrt{\sqrt[3]{\sin^{-1} \left(1 - x\right)}}\right)\right)} \]

6. Final simplification 10.8%

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

Alternatives

Alternative 1
Accuracy	10.7%
Cost	175872

\[\begin{array}{l} t_0 := \sqrt{\pi \cdot 0.5}\\ t_1 := \sin^{-1} \left(1 - x\right)\\ t_2 := {t_1}^{0.16666666666666666}\\ t_3 := -t_2\\ t_4 := {\left(\sqrt[3]{t_1}\right)}^{2}\\ t_5 := t_2 \cdot t_4\\ \mathsf{fma}\left(t_3, t_5, t_2 \cdot t_5\right) + \mathsf{fma}\left(t_0, t_0, t_2 \cdot \left(t_4 \cdot t_3\right)\right) \end{array} \]

Alternative 2
Accuracy	10.7%
Cost	45312

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

Alternative 3
Accuracy	10.6%
Cost	39488

\[\begin{array}{l} t_0 := \sin^{-1} \left(1 - x\right)\\ \cos^{-1} \left(1 - x\right) + \left({t_0}^{0.16666666666666666} \cdot {t_0}^{0.8333333333333334} - t_0\right) \end{array} \]

Alternative 4
Accuracy	10.6%
Cost	32512

\[\log \left({\left(\sqrt{1 + e^{\cos^{-1} \left(1 - x\right)}}\right)}^{2} + -1\right) \]

Alternative 5
Accuracy	10.6%
Cost	26048

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

Alternative 6
Accuracy	7.1%
Cost	19972

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

Alternative 7
Accuracy	7.1%
Cost	19908

\[\begin{array}{l} \mathbf{if}\;1 - x \leq 1:\\ \;\;\;\;e^{\log \left(-1 + \left(1 + \cos^{-1} \left(1 - x\right)\right)\right)}\\ \mathbf{else}:\\ \;\;\;\;\pi \cdot 0.5 + \sin^{-1} \left(1 - x\right)\\ \end{array} \]

Alternative 8
Accuracy	7.1%
Cost	19908

\[\begin{array}{l} \mathbf{if}\;1 - x \leq 1:\\ \;\;\;\;\log \left(\left(1 + e^{\cos^{-1} \left(1 - x\right)}\right) + -1\right)\\ \mathbf{else}:\\ \;\;\;\;\pi \cdot 0.5 + \sin^{-1} \left(1 - x\right)\\ \end{array} \]

Alternative 9
Accuracy	7.1%
Cost	13444

\[\begin{array}{l} \mathbf{if}\;1 - x \leq 1:\\ \;\;\;\;-1 + \left(1 + \cos^{-1} \left(1 - x\right)\right)\\ \mathbf{else}:\\ \;\;\;\;\pi \cdot 0.5 + \sin^{-1} \left(1 - x\right)\\ \end{array} \]

Alternative 10
Accuracy	7.1%
Cost	6848

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

Alternative 11
Accuracy	7.1%
Cost	6592

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

Reproduce

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