bug366, discussion (missed optimization)

Percentage Accurate: 52.9% → 99.8%

Time: 3.6s

Alternatives: 3

Speedup: 107.0×

Specification

Math

\[\begin{array}{l} \\ \sqrt{a \cdot a - b \cdot b} \end{array} \]

FPCore

(FPCore (a b) :precision binary64 (sqrt (- (* a a) (* b b))))

C

double code(double a, double b) {
	return sqrt(((a * a) - (b * b)));
}

Fortran

real(8) function code(a, b)
    real(8), intent (in) :: a
    real(8), intent (in) :: b
    code = sqrt(((a * a) - (b * b)))
end function

Java

public static double code(double a, double b) {
	return Math.sqrt(((a * a) - (b * b)));
}

Python

def code(a, b):
	return math.sqrt(((a * a) - (b * b)))

Julia

function code(a, b)
	return sqrt(Float64(Float64(a * a) - Float64(b * b)))
end

MATLAB

function tmp = code(a, b)
	tmp = sqrt(((a * a) - (b * b)));
end

Wolfram

code[a_, b_] := N[Sqrt[N[(N[(a * a), $MachinePrecision] - N[(b * b), $MachinePrecision]), $MachinePrecision]], $MachinePrecision]

Initial Program: 52.9% accurate, 1.0× speedup

Math

\[\begin{array}{l} \\ \sqrt{a \cdot a - b \cdot b} \end{array} \]

FPCore

(FPCore (a b) :precision binary64 (sqrt (- (* a a) (* b b))))

C

double code(double a, double b) {
	return sqrt(((a * a) - (b * b)));
}

Fortran

real(8) function code(a, b)
    real(8), intent (in) :: a
    real(8), intent (in) :: b
    code = sqrt(((a * a) - (b * b)))
end function

Java

public static double code(double a, double b) {
	return Math.sqrt(((a * a) - (b * b)));
}

Python

def code(a, b):
	return math.sqrt(((a * a) - (b * b)))

Julia

function code(a, b)
	return sqrt(Float64(Float64(a * a) - Float64(b * b)))
end

MATLAB

function tmp = code(a, b)
	tmp = sqrt(((a * a) - (b * b)));
end

Wolfram

code[a_, b_] := N[Sqrt[N[(N[(a * a), $MachinePrecision] - N[(b * b), $MachinePrecision]), $MachinePrecision]], $MachinePrecision]

Alternative 1: 99.8% accurate, 0.5× speedup

Math

\[\begin{array}{l} a = |a|\\ b = |b|\\ \\ \sqrt{a - b} \cdot \frac{a + b}{\sqrt{a + b}} \end{array} \]

FPCore

NOTE: a should be positive before calling this function
NOTE: b should be positive before calling this function
(FPCore (a b)
 :precision binary64
 (* (sqrt (- a b)) (/ (+ a b) (sqrt (+ a b)))))

C

a = abs(a);
b = abs(b);
double code(double a, double b) {
	return sqrt((a - b)) * ((a + b) / sqrt((a + b)));
}

Fortran

NOTE: a should be positive before calling this function
NOTE: b should be positive before calling this function
real(8) function code(a, b)
    real(8), intent (in) :: a
    real(8), intent (in) :: b
    code = sqrt((a - b)) * ((a + b) / sqrt((a + b)))
end function

Java

a = Math.abs(a);
b = Math.abs(b);
public static double code(double a, double b) {
	return Math.sqrt((a - b)) * ((a + b) / Math.sqrt((a + b)));
}

Python

a = abs(a)
b = abs(b)
def code(a, b):
	return math.sqrt((a - b)) * ((a + b) / math.sqrt((a + b)))

Julia

a = abs(a)
b = abs(b)
function code(a, b)
	return Float64(sqrt(Float64(a - b)) * Float64(Float64(a + b) / sqrt(Float64(a + b))))
end

MATLAB

a = abs(a)
b = abs(b)
function tmp = code(a, b)
	tmp = sqrt((a - b)) * ((a + b) / sqrt((a + b)));
end

Wolfram

NOTE: a should be positive before calling this function
NOTE: b should be positive before calling this function
code[a_, b_] := N[(N[Sqrt[N[(a - b), $MachinePrecision]], $MachinePrecision] * N[(N[(a + b), $MachinePrecision] / N[Sqrt[N[(a + b), $MachinePrecision]], $MachinePrecision]), $MachinePrecision]), $MachinePrecision]

Derivation

1. Initial program 58.7%

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

   1. difference-of-squares 59.0%

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

3. Simplified 59.0%

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

   1. *-commutative 59.0%

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

   2. sqrt-prod 48.1%

      \[\leadsto \color{blue}{\sqrt{a - b} \cdot \sqrt{a + b}} \]

5. Applied egg-rr 48.1%

   \[\leadsto \color{blue}{\sqrt{a - b} \cdot \sqrt{a + b}} \]
6. Step-by-step derivation

   1. add-sqr-sqrt 21.0%

      \[\leadsto \sqrt{a - b} \cdot \sqrt{a + \color{blue}{\sqrt{b} \cdot \sqrt{b}}} \]

   2. sqrt-unprod 46.5%

      \[\leadsto \sqrt{a - b} \cdot \sqrt{a + \color{blue}{\sqrt{b \cdot b}}} \]

   3. sqr-neg 46.5%

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

   4. sqrt-unprod 26.4%

      \[\leadsto \sqrt{a - b} \cdot \sqrt{a + \color{blue}{\sqrt{-b} \cdot \sqrt{-b}}} \]

   5. add-sqr-sqrt 46.9%

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

   6. sub-neg 46.9%

      \[\leadsto \sqrt{a - b} \cdot \sqrt{\color{blue}{a - b}} \]

   7. flip-- 27.6%

      \[\leadsto \sqrt{a - b} \cdot \sqrt{\color{blue}{\frac{a \cdot a - b \cdot b}{a + b}}} \]

   8. sqrt-div 27.8%

      \[\leadsto \sqrt{a - b} \cdot \color{blue}{\frac{\sqrt{a \cdot a - b \cdot b}}{\sqrt{a + b}}} \]

7. Applied egg-rr 48.4%

   \[\leadsto \sqrt{a - b} \cdot \color{blue}{\frac{a + b}{\sqrt{a + b}}} \]
8. Step-by-step derivation

   1. +-commutative 48.4%

      \[\leadsto \sqrt{a - b} \cdot \frac{\color{blue}{b + a}}{\sqrt{a + b}} \]

   2. +-commutative 48.4%

      \[\leadsto \sqrt{a - b} \cdot \frac{b + a}{\sqrt{\color{blue}{b + a}}} \]

9. Simplified 48.4%

   \[\leadsto \sqrt{a - b} \cdot \color{blue}{\frac{b + a}{\sqrt{b + a}}} \]

10. Final simplification 48.4%

    \[\leadsto \sqrt{a - b} \cdot \frac{a + b}{\sqrt{a + b}} \]

Alternative 2: 99.5% accurate, 1.0× speedup

Math

\[\begin{array}{l} a = |a|\\ b = |b|\\ \\ \mathsf{fma}\left(-0.5, \frac{b}{\frac{a}{b}}, a\right) \end{array} \]

FPCore

NOTE: a should be positive before calling this function
NOTE: b should be positive before calling this function
(FPCore (a b) :precision binary64 (fma -0.5 (/ b (/ a b)) a))

C

a = abs(a);
b = abs(b);
double code(double a, double b) {
	return fma(-0.5, (b / (a / b)), a);
}

Julia

a = abs(a)
b = abs(b)
function code(a, b)
	return fma(-0.5, Float64(b / Float64(a / b)), a)
end

Wolfram

NOTE: a should be positive before calling this function
NOTE: b should be positive before calling this function
code[a_, b_] := N[(-0.5 * N[(b / N[(a / b), $MachinePrecision]), $MachinePrecision] + a), $MachinePrecision]

Derivation

1. Initial program 58.7%

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

   1. difference-of-squares 59.0%

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

3. Simplified 59.0%

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

4. Taylor expanded in a around -inf 0.0%

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

6. Simplified 48.8%

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

7. Final simplification 48.8%

   \[\leadsto \mathsf{fma}\left(-0.5, \frac{b}{\frac{a}{b}}, a\right) \]

Alternative 3: 98.9% accurate, 107.0× speedup

Math

\[\begin{array}{l} a = |a|\\ b = |b|\\ \\ a \end{array} \]

FPCore

NOTE: a should be positive before calling this function
NOTE: b should be positive before calling this function
(FPCore (a b) :precision binary64 a)

C

a = abs(a);
b = abs(b);
double code(double a, double b) {
	return a;
}

Fortran

NOTE: a should be positive before calling this function
NOTE: b should be positive before calling this function
real(8) function code(a, b)
    real(8), intent (in) :: a
    real(8), intent (in) :: b
    code = a
end function

Java

a = Math.abs(a);
b = Math.abs(b);
public static double code(double a, double b) {
	return a;
}

Python

a = abs(a)
b = abs(b)
def code(a, b):
	return a

Julia

a = abs(a)
b = abs(b)
function code(a, b)
	return a
end

MATLAB

a = abs(a)
b = abs(b)
function tmp = code(a, b)
	tmp = a;
end

Wolfram

NOTE: a should be positive before calling this function
NOTE: b should be positive before calling this function
code[a_, b_] := a

Derivation

1. Initial program 58.7%

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

   1. difference-of-squares 59.0%

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

3. Simplified 59.0%

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

4. Taylor expanded in a around inf 48.5%

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

5. Final simplification 48.5%

   \[\leadsto a \]

Developer target: 99.2% accurate, 0.2× speedup

Math

\[\begin{array}{l} \\ \sqrt{\left|a\right| + \left|b\right|} \cdot \sqrt{\left|a\right| - \left|b\right|} \end{array} \]

FPCore

(FPCore (a b)
 :precision binary64
 (* (sqrt (+ (fabs a) (fabs b))) (sqrt (- (fabs a) (fabs b)))))

C

double code(double a, double b) {
	return sqrt((fabs(a) + fabs(b))) * sqrt((fabs(a) - fabs(b)));
}

Fortran

real(8) function code(a, b)
    real(8), intent (in) :: a
    real(8), intent (in) :: b
    code = sqrt((abs(a) + abs(b))) * sqrt((abs(a) - abs(b)))
end function

Java

public static double code(double a, double b) {
	return Math.sqrt((Math.abs(a) + Math.abs(b))) * Math.sqrt((Math.abs(a) - Math.abs(b)));
}

Python

def code(a, b):
	return math.sqrt((math.fabs(a) + math.fabs(b))) * math.sqrt((math.fabs(a) - math.fabs(b)))

Julia

function code(a, b)
	return Float64(sqrt(Float64(abs(a) + abs(b))) * sqrt(Float64(abs(a) - abs(b))))
end

MATLAB

function tmp = code(a, b)
	tmp = sqrt((abs(a) + abs(b))) * sqrt((abs(a) - abs(b)));
end

Wolfram

code[a_, b_] := N[(N[Sqrt[N[(N[Abs[a], $MachinePrecision] + N[Abs[b], $MachinePrecision]), $MachinePrecision]], $MachinePrecision] * N[Sqrt[N[(N[Abs[a], $MachinePrecision] - N[Abs[b], $MachinePrecision]), $MachinePrecision]], $MachinePrecision]), $MachinePrecision]

Reproduce

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