bug366, discussion (missed optimization)

Percentage Accurate: 53.2% → 99.4%
Time: 4.4s
Alternatives: 4
Speedup: 107.0×

Specification

?
\[\sqrt{a \cdot a - b \cdot b} \]

Local Percentage Accuracy vs ?

The average percentage accuracy by input value. Horizontal axis shows value of an input variable; the variable is choosen in the title. Vertical axis is accuracy; higher is better. Red represent the original program, while blue represents Herbie's suggestion. These can be toggled with buttons below the plot. The line is an average while dots represent individual samples.

Accuracy vs Speed?

Herbie found 4 alternatives:

AlternativeAccuracySpeedup
The accuracy (vertical axis) and speed (horizontal axis) of each alternatives. Up and to the right is better. The red square shows the initial program, and each blue circle shows an alternative.The line shows the best available speed-accuracy tradeoffs.

Alternative 1: 99.4% accurate, 1.0× speedup?

\[\begin{array}{l} \mathbf{if}\;a \leq -1 \cdot 10^{-285}:\\ \;\;\;\;\left(b \cdot \frac{b}{a}\right) \cdot 0.5 - a\\ \mathbf{else}:\\ \;\;\;\;\mathsf{fma}\left(-0.5, \frac{b}{\frac{a}{b}}, a\right)\\ \end{array} \]
Derivation
  1. Split input into 2 regimes

  2. if a < -1.00000000000000007e-285

    1. Initial program 51.1%

      \[\sqrt{a \cdot a - b \cdot b} \]
    2. Step-by-step derivation

      1. difference-of-squares51.7%

        \[\leadsto \sqrt{\color{blue}{\left(a + b\right) \cdot \left(a - b\right)}} \]

    3. Simplified51.7%

      \[\leadsto \color{blue}{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}} \]
    4. Step-by-step derivation

      1. add-cube-cbrt50.7%

        \[\leadsto \color{blue}{\left(\sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}} \cdot \sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}}\right) \cdot \sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}}} \]

      2. pow350.7%

        \[\leadsto \color{blue}{{\left(\sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}}\right)}^{3}} \]

      3. pow1/347.6%

        \[\leadsto {\color{blue}{\left({\left(\sqrt{\left(a + b\right) \cdot \left(a - b\right)}\right)}^{0.3333333333333333}\right)}}^{3} \]

      4. pow1/247.6%

        \[\leadsto {\left({\color{blue}{\left({\left(\left(a + b\right) \cdot \left(a - b\right)\right)}^{0.5}\right)}}^{0.3333333333333333}\right)}^{3} \]

      5. difference-of-squares47.1%

        \[\leadsto {\left({\left({\color{blue}{\left(a \cdot a - b \cdot b\right)}}^{0.5}\right)}^{0.3333333333333333}\right)}^{3} \]

      6. pow-pow47.1%

        \[\leadsto {\color{blue}{\left({\left(a \cdot a - b \cdot b\right)}^{\left(0.5 \cdot 0.3333333333333333\right)}\right)}}^{3} \]

      7. fma-neg47.6%

        \[\leadsto {\left({\color{blue}{\left(\mathsf{fma}\left(a, a, -b \cdot b\right)\right)}}^{\left(0.5 \cdot 0.3333333333333333\right)}\right)}^{3} \]

      8. metadata-eval47.6%

        \[\leadsto {\left({\left(\mathsf{fma}\left(a, a, -b \cdot b\right)\right)}^{\color{blue}{0.16666666666666666}}\right)}^{3} \]

    5. Applied egg-rr47.6%

      \[\leadsto \color{blue}{{\left({\left(\mathsf{fma}\left(a, a, -b \cdot b\right)\right)}^{0.16666666666666666}\right)}^{3}} \]

    6. Taylor expanded in a around -inf 93.8%

      \[\leadsto \color{blue}{0.16666666666666666 \cdot \left({1}^{0.3333333333333333} \cdot \frac{{b}^{2}}{a}\right) + \left(0.3333333333333333 \cdot \frac{{b}^{2}}{a} + -1 \cdot a\right)} \]
    7. Step-by-step derivation

      1. associate-+r+93.8%

        \[\leadsto \color{blue}{\left(0.16666666666666666 \cdot \left({1}^{0.3333333333333333} \cdot \frac{{b}^{2}}{a}\right) + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) + -1 \cdot a} \]

      2. neg-mul-193.8%

        \[\leadsto \left(0.16666666666666666 \cdot \left({1}^{0.3333333333333333} \cdot \frac{{b}^{2}}{a}\right) + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) + \color{blue}{\left(-a\right)} \]

      3. unsub-neg93.8%

        \[\leadsto \color{blue}{\left(0.16666666666666666 \cdot \left({1}^{0.3333333333333333} \cdot \frac{{b}^{2}}{a}\right) + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) - a} \]

      4. pow-base-193.8%

        \[\leadsto \left(0.16666666666666666 \cdot \left(\color{blue}{1} \cdot \frac{{b}^{2}}{a}\right) + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) - a \]

      5. associate-*r*93.8%

        \[\leadsto \left(\color{blue}{\left(0.16666666666666666 \cdot 1\right) \cdot \frac{{b}^{2}}{a}} + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) - a \]

      6. metadata-eval93.8%

        \[\leadsto \left(\color{blue}{0.16666666666666666} \cdot \frac{{b}^{2}}{a} + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) - a \]

      7. unpow293.8%

        \[\leadsto \left(0.16666666666666666 \cdot \frac{\color{blue}{b \cdot b}}{a} + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) - a \]

      8. unpow293.8%

        \[\leadsto \left(0.16666666666666666 \cdot \frac{b \cdot b}{a} + 0.3333333333333333 \cdot \frac{\color{blue}{b \cdot b}}{a}\right) - a \]

      9. distribute-rgt-out93.8%

        \[\leadsto \color{blue}{\frac{b \cdot b}{a} \cdot \left(0.16666666666666666 + 0.3333333333333333\right)} - a \]

      10. associate-*r/100.0%

        \[\leadsto \color{blue}{\left(b \cdot \frac{b}{a}\right)} \cdot \left(0.16666666666666666 + 0.3333333333333333\right) - a \]

      11. metadata-eval100.0%

        \[\leadsto \left(b \cdot \frac{b}{a}\right) \cdot \color{blue}{0.5} - a \]

    8. Simplified100.0%

      \[\leadsto \color{blue}{\left(b \cdot \frac{b}{a}\right) \cdot 0.5 - a} \]

    if -1.00000000000000007e-285 < a

    1. Initial program 46.9%

      \[\sqrt{a \cdot a - b \cdot b} \]
    2. Step-by-step derivation

      1. difference-of-squares47.2%

        \[\leadsto \sqrt{\color{blue}{\left(a + b\right) \cdot \left(a - b\right)}} \]

    3. Simplified47.2%

      \[\leadsto \color{blue}{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}} \]

    4. Taylor expanded in a around inf 95.7%

      \[\leadsto \color{blue}{0.5 \cdot \left(b + -1 \cdot b\right) + \left(0.5 \cdot \frac{-1 \cdot {b}^{2} - {\left(0.5 \cdot \left(b + -1 \cdot b\right)\right)}^{2}}{a} + a\right)} \]
    5. Step-by-step derivation

      1. fma-def95.7%

        \[\leadsto \color{blue}{\mathsf{fma}\left(0.5, b + -1 \cdot b, 0.5 \cdot \frac{-1 \cdot {b}^{2} - {\left(0.5 \cdot \left(b + -1 \cdot b\right)\right)}^{2}}{a} + a\right)} \]

      2. distribute-rgt1-in95.7%

        \[\leadsto \mathsf{fma}\left(0.5, \color{blue}{\left(-1 + 1\right) \cdot b}, 0.5 \cdot \frac{-1 \cdot {b}^{2} - {\left(0.5 \cdot \left(b + -1 \cdot b\right)\right)}^{2}}{a} + a\right) \]

      3. metadata-eval95.7%

        \[\leadsto \mathsf{fma}\left(0.5, \color{blue}{0} \cdot b, 0.5 \cdot \frac{-1 \cdot {b}^{2} - {\left(0.5 \cdot \left(b + -1 \cdot b\right)\right)}^{2}}{a} + a\right) \]

      4. mul0-lft95.7%

        \[\leadsto \mathsf{fma}\left(0.5, \color{blue}{0}, 0.5 \cdot \frac{-1 \cdot {b}^{2} - {\left(0.5 \cdot \left(b + -1 \cdot b\right)\right)}^{2}}{a} + a\right) \]

      5. fma-udef95.7%

        \[\leadsto \color{blue}{0.5 \cdot 0 + \left(0.5 \cdot \frac{-1 \cdot {b}^{2} - {\left(0.5 \cdot \left(b + -1 \cdot b\right)\right)}^{2}}{a} + a\right)} \]

      6. metadata-eval95.7%

        \[\leadsto \color{blue}{0} + \left(0.5 \cdot \frac{-1 \cdot {b}^{2} - {\left(0.5 \cdot \left(b + -1 \cdot b\right)\right)}^{2}}{a} + a\right) \]

      7. +-lft-identity95.7%

        \[\leadsto \color{blue}{0.5 \cdot \frac{-1 \cdot {b}^{2} - {\left(0.5 \cdot \left(b + -1 \cdot b\right)\right)}^{2}}{a} + a} \]

    6. Simplified99.7%

      \[\leadsto \color{blue}{\mathsf{fma}\left(-0.5, \frac{b}{\frac{a}{b}}, a\right)} \]
  3. Recombined 2 regimes into one program.

  4. Final simplification99.8%

    \[\leadsto \begin{array}{l} \mathbf{if}\;a \leq -1 \cdot 10^{-285}:\\ \;\;\;\;\left(b \cdot \frac{b}{a}\right) \cdot 0.5 - a\\ \mathbf{else}:\\ \;\;\;\;\mathsf{fma}\left(-0.5, \frac{b}{\frac{a}{b}}, a\right)\\ \end{array} \]

Alternative 2: 99.1% accurate, 9.7× speedup?

\[\begin{array}{l} \mathbf{if}\;a \leq -4 \cdot 10^{-304}:\\ \;\;\;\;\left(b \cdot \frac{b}{a}\right) \cdot 0.5 - a\\ \mathbf{else}:\\ \;\;\;\;a\\ \end{array} \]
Derivation
  1. Split input into 2 regimes

  2. if a < -3.99999999999999988e-304

    1. Initial program 51.1%

      \[\sqrt{a \cdot a - b \cdot b} \]
    2. Step-by-step derivation

      1. difference-of-squares51.7%

        \[\leadsto \sqrt{\color{blue}{\left(a + b\right) \cdot \left(a - b\right)}} \]

    3. Simplified51.7%

      \[\leadsto \color{blue}{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}} \]
    4. Step-by-step derivation

      1. add-cube-cbrt50.7%

        \[\leadsto \color{blue}{\left(\sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}} \cdot \sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}}\right) \cdot \sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}}} \]

      2. pow350.7%

        \[\leadsto \color{blue}{{\left(\sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}}\right)}^{3}} \]

      3. pow1/347.6%

        \[\leadsto {\color{blue}{\left({\left(\sqrt{\left(a + b\right) \cdot \left(a - b\right)}\right)}^{0.3333333333333333}\right)}}^{3} \]

      4. pow1/247.6%

        \[\leadsto {\left({\color{blue}{\left({\left(\left(a + b\right) \cdot \left(a - b\right)\right)}^{0.5}\right)}}^{0.3333333333333333}\right)}^{3} \]

      5. difference-of-squares47.1%

        \[\leadsto {\left({\left({\color{blue}{\left(a \cdot a - b \cdot b\right)}}^{0.5}\right)}^{0.3333333333333333}\right)}^{3} \]

      6. pow-pow47.1%

        \[\leadsto {\color{blue}{\left({\left(a \cdot a - b \cdot b\right)}^{\left(0.5 \cdot 0.3333333333333333\right)}\right)}}^{3} \]

      7. fma-neg47.6%

        \[\leadsto {\left({\color{blue}{\left(\mathsf{fma}\left(a, a, -b \cdot b\right)\right)}}^{\left(0.5 \cdot 0.3333333333333333\right)}\right)}^{3} \]

      8. metadata-eval47.6%

        \[\leadsto {\left({\left(\mathsf{fma}\left(a, a, -b \cdot b\right)\right)}^{\color{blue}{0.16666666666666666}}\right)}^{3} \]

    5. Applied egg-rr47.6%

      \[\leadsto \color{blue}{{\left({\left(\mathsf{fma}\left(a, a, -b \cdot b\right)\right)}^{0.16666666666666666}\right)}^{3}} \]

    6. Taylor expanded in a around -inf 93.8%

      \[\leadsto \color{blue}{0.16666666666666666 \cdot \left({1}^{0.3333333333333333} \cdot \frac{{b}^{2}}{a}\right) + \left(0.3333333333333333 \cdot \frac{{b}^{2}}{a} + -1 \cdot a\right)} \]
    7. Step-by-step derivation

      1. associate-+r+93.8%

        \[\leadsto \color{blue}{\left(0.16666666666666666 \cdot \left({1}^{0.3333333333333333} \cdot \frac{{b}^{2}}{a}\right) + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) + -1 \cdot a} \]

      2. neg-mul-193.8%

        \[\leadsto \left(0.16666666666666666 \cdot \left({1}^{0.3333333333333333} \cdot \frac{{b}^{2}}{a}\right) + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) + \color{blue}{\left(-a\right)} \]

      3. unsub-neg93.8%

        \[\leadsto \color{blue}{\left(0.16666666666666666 \cdot \left({1}^{0.3333333333333333} \cdot \frac{{b}^{2}}{a}\right) + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) - a} \]

      4. pow-base-193.8%

        \[\leadsto \left(0.16666666666666666 \cdot \left(\color{blue}{1} \cdot \frac{{b}^{2}}{a}\right) + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) - a \]

      5. associate-*r*93.8%

        \[\leadsto \left(\color{blue}{\left(0.16666666666666666 \cdot 1\right) \cdot \frac{{b}^{2}}{a}} + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) - a \]

      6. metadata-eval93.8%

        \[\leadsto \left(\color{blue}{0.16666666666666666} \cdot \frac{{b}^{2}}{a} + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) - a \]

      7. unpow293.8%

        \[\leadsto \left(0.16666666666666666 \cdot \frac{\color{blue}{b \cdot b}}{a} + 0.3333333333333333 \cdot \frac{{b}^{2}}{a}\right) - a \]

      8. unpow293.8%

        \[\leadsto \left(0.16666666666666666 \cdot \frac{b \cdot b}{a} + 0.3333333333333333 \cdot \frac{\color{blue}{b \cdot b}}{a}\right) - a \]

      9. distribute-rgt-out93.8%

        \[\leadsto \color{blue}{\frac{b \cdot b}{a} \cdot \left(0.16666666666666666 + 0.3333333333333333\right)} - a \]

      10. associate-*r/100.0%

        \[\leadsto \color{blue}{\left(b \cdot \frac{b}{a}\right)} \cdot \left(0.16666666666666666 + 0.3333333333333333\right) - a \]

      11. metadata-eval100.0%

        \[\leadsto \left(b \cdot \frac{b}{a}\right) \cdot \color{blue}{0.5} - a \]

    8. Simplified100.0%

      \[\leadsto \color{blue}{\left(b \cdot \frac{b}{a}\right) \cdot 0.5 - a} \]

    if -3.99999999999999988e-304 < a

    1. Initial program 46.9%

      \[\sqrt{a \cdot a - b \cdot b} \]
    2. Step-by-step derivation

      1. difference-of-squares47.2%

        \[\leadsto \sqrt{\color{blue}{\left(a + b\right) \cdot \left(a - b\right)}} \]

    3. Simplified47.2%

      \[\leadsto \color{blue}{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}} \]

    4. Taylor expanded in a around inf 99.5%

      \[\leadsto \color{blue}{a} \]
  3. Recombined 2 regimes into one program.

  4. Final simplification99.7%

    \[\leadsto \begin{array}{l} \mathbf{if}\;a \leq -4 \cdot 10^{-304}:\\ \;\;\;\;\left(b \cdot \frac{b}{a}\right) \cdot 0.5 - a\\ \mathbf{else}:\\ \;\;\;\;a\\ \end{array} \]

Alternative 3: 98.8% accurate, 26.3× speedup?

\[\begin{array}{l} \mathbf{if}\;a \leq -1 \cdot 10^{-285}:\\ \;\;\;\;-a\\ \mathbf{else}:\\ \;\;\;\;a\\ \end{array} \]
Derivation
  1. Split input into 2 regimes

  2. if a < -1.00000000000000007e-285

    1. Initial program 51.1%

      \[\sqrt{a \cdot a - b \cdot b} \]
    2. Step-by-step derivation

      1. difference-of-squares51.7%

        \[\leadsto \sqrt{\color{blue}{\left(a + b\right) \cdot \left(a - b\right)}} \]

    3. Simplified51.7%

      \[\leadsto \color{blue}{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}} \]
    4. Step-by-step derivation

      1. add-cube-cbrt50.7%

        \[\leadsto \color{blue}{\left(\sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}} \cdot \sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}}\right) \cdot \sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}}} \]

      2. pow350.7%

        \[\leadsto \color{blue}{{\left(\sqrt[3]{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}}\right)}^{3}} \]

      3. pow1/347.6%

        \[\leadsto {\color{blue}{\left({\left(\sqrt{\left(a + b\right) \cdot \left(a - b\right)}\right)}^{0.3333333333333333}\right)}}^{3} \]

      4. pow1/247.6%

        \[\leadsto {\left({\color{blue}{\left({\left(\left(a + b\right) \cdot \left(a - b\right)\right)}^{0.5}\right)}}^{0.3333333333333333}\right)}^{3} \]

      5. difference-of-squares47.1%

        \[\leadsto {\left({\left({\color{blue}{\left(a \cdot a - b \cdot b\right)}}^{0.5}\right)}^{0.3333333333333333}\right)}^{3} \]

      6. pow-pow47.1%

        \[\leadsto {\color{blue}{\left({\left(a \cdot a - b \cdot b\right)}^{\left(0.5 \cdot 0.3333333333333333\right)}\right)}}^{3} \]

      7. fma-neg47.6%

        \[\leadsto {\left({\color{blue}{\left(\mathsf{fma}\left(a, a, -b \cdot b\right)\right)}}^{\left(0.5 \cdot 0.3333333333333333\right)}\right)}^{3} \]

      8. metadata-eval47.6%

        \[\leadsto {\left({\left(\mathsf{fma}\left(a, a, -b \cdot b\right)\right)}^{\color{blue}{0.16666666666666666}}\right)}^{3} \]

    5. Applied egg-rr47.6%

      \[\leadsto \color{blue}{{\left({\left(\mathsf{fma}\left(a, a, -b \cdot b\right)\right)}^{0.16666666666666666}\right)}^{3}} \]

    6. Taylor expanded in a around -inf 99.3%

      \[\leadsto \color{blue}{-1 \cdot a} \]
    7. Step-by-step derivation

      1. neg-mul-199.3%

        \[\leadsto \color{blue}{-a} \]

    8. Simplified99.3%

      \[\leadsto \color{blue}{-a} \]

    if -1.00000000000000007e-285 < a

    1. Initial program 46.9%

      \[\sqrt{a \cdot a - b \cdot b} \]
    2. Step-by-step derivation

      1. difference-of-squares47.2%

        \[\leadsto \sqrt{\color{blue}{\left(a + b\right) \cdot \left(a - b\right)}} \]

    3. Simplified47.2%

      \[\leadsto \color{blue}{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}} \]

    4. Taylor expanded in a around inf 99.5%

      \[\leadsto \color{blue}{a} \]
  3. Recombined 2 regimes into one program.

  4. Final simplification99.4%

    \[\leadsto \begin{array}{l} \mathbf{if}\;a \leq -1 \cdot 10^{-285}:\\ \;\;\;\;-a\\ \mathbf{else}:\\ \;\;\;\;a\\ \end{array} \]

Alternative 4: 49.7% accurate, 107.0× speedup?

\[a \]
Derivation

  1. Initial program 49.0%

    \[\sqrt{a \cdot a - b \cdot b} \]
  2. Step-by-step derivation

    1. difference-of-squares49.4%

      \[\leadsto \sqrt{\color{blue}{\left(a + b\right) \cdot \left(a - b\right)}} \]

  3. Simplified49.4%

    \[\leadsto \color{blue}{\sqrt{\left(a + b\right) \cdot \left(a - b\right)}} \]

  4. Taylor expanded in a around inf 51.1%

    \[\leadsto \color{blue}{a} \]

  5. Final simplification51.1%

    \[\leadsto a \]

Developer target: 99.2% accurate, 0.2× speedup?

\[\sqrt{\left|a\right| + \left|b\right|} \cdot \sqrt{\left|a\right| - \left|b\right|} \]

Reproduce

?
herbie shell --seed 2023167 
(FPCore (a b)
  :name "bug366, discussion (missed optimization)"
  :precision binary64

  :herbie-target
  (* (sqrt (+ (fabs a) (fabs b))) (sqrt (- (fabs a) (fabs b))))

  (sqrt (- (* a a) (* b b))))