Kahan p9 Example

Average Error: 20.7 → 5.2

Time: 2.8s

Precision: binary64

Cost: 2177

\[0 < x \land x < 1 \land y < 1\]

Math

\[\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\]

↓

\[\begin{array}{l} \mathbf{if}\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y} \leq 1:\\ \;\;\;\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\\ \mathbf{else}:\\ \;\;\;\;-1\\ \end{array}\]

FPCore

(FPCore (x y) :precision binary64 (/ (* (- x y) (+ x y)) (+ (* x x) (* y y))))

↓

(FPCore (x y)
 :precision binary64
 (if (<= (/ (* (- x y) (+ x y)) (+ (* x x) (* y y))) 1.0)
   (/ (* (- x y) (+ x y)) (+ (* x x) (* y y)))
   -1.0))

C

double code(double x, double y) {
	return ((x - y) * (x + y)) / ((x * x) + (y * y));
}

↓

double code(double x, double y) {
	double tmp;
	if ((((x - y) * (x + y)) / ((x * x) + (y * y))) <= 1.0) {
		tmp = ((x - y) * (x + y)) / ((x * x) + (y * y));
	} else {
		tmp = -1.0;
	}
	return tmp;
}

Error

Bits error versus x

Bits error versus y

Target

Original	20.7
Target	0.1
Herbie	5.2

\[\begin{array}{l} \mathbf{if}\;0.5 < \left|\frac{x}{y}\right| \land \left|\frac{x}{y}\right| < 2:\\ \;\;\;\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\\ \mathbf{else}:\\ \;\;\;\;1 - \frac{2}{1 + \frac{x}{y} \cdot \frac{x}{y}}\\ \end{array}\]

Alternatives

Alternative 1
Error	21.7
Cost	21184

\[\frac{x - y}{\sqrt[3]{x \cdot x + y \cdot y} \cdot \sqrt[3]{x \cdot x + y \cdot y}} \cdot \frac{x + y}{\sqrt[3]{x \cdot x + y \cdot y}}\]

Alternative 2
Error	48.0
Cost	14784

\[\sqrt{\frac{x \cdot x - y \cdot y}{x \cdot x + y \cdot y}} \cdot \sqrt{\frac{x \cdot x - y \cdot y}{x \cdot x + y \cdot y}}\]

Alternative 3
Error	20.9
Cost	14272

\[\frac{x - y}{\sqrt{x \cdot x + y \cdot y}} \cdot \frac{x + y}{\sqrt{x \cdot x + y \cdot y}}\]

Alternative 4
Error	39.5
Cost	14144

\[\frac{\left(x \cdot x - y \cdot y\right) \cdot \left(x \cdot x - y \cdot y\right)}{{x}^{4} - {y}^{4}}\]

Alternative 5
Error	20.7
Cost	13824

\[\sqrt[3]{{\left(\frac{x \cdot x - y \cdot y}{x \cdot x + y \cdot y}\right)}^{3}}\]

Alternative 6
Error	53.0
Cost	13376

\[1 - 2 \cdot e^{2 \cdot \log \left(\frac{y}{x}\right)}\]

Alternative 7
Error	42.7
Cost	13312

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

Alternative 8
Error	32.6
Cost	1472

\[\frac{\left(x + y\right) \cdot \left(x \cdot x - y \cdot y\right)}{\left(x \cdot x + y \cdot y\right) \cdot \left(x + y\right)}\]

Alternative 9
Error	20.7
Cost	960

\[\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\]

Alternative 10
Error	21.0
Cost	960

\[\left(x - y\right) \cdot \frac{x + y}{x \cdot x + y \cdot y}\]

Alternative 11
Error	42.2
Cost	704

\[1 - 2 \cdot \left(\frac{y}{x} \cdot \frac{y}{x}\right)\]

Alternative 12
Error	47.7
Cost	704

\[1 - 2 \cdot \frac{y \cdot y}{x \cdot x}\]

Alternative 13
Error	25.9
Cost	704

\[-1 + 2 \cdot \frac{x \cdot x}{y \cdot y}\]

Alternative 14
Error	42.8
Cost	64

\[1\]

Alternative 15
Error	21.2
Cost	64

\[-1\]

Alternative 16
Error	62.0
Cost	64

\[0\]

Derivation

1. Split input into 2 regimes

2. if (/.f64 (*.f64 (-.f64 x y) (+.f64 x y)) (+.f64 (*.f64 x x) (*.f64 y y))) < 1

   1. Initial program 0.0

      \[\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\]

   2. Simplified 0.0

      \[\leadsto \color{blue}{\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}}\]

   if 1 < (/.f64 (*.f64 (-.f64 x y) (+.f64 x y)) (+.f64 (*.f64 x x) (*.f64 y y)))

   1. Initial program 64.0

      \[\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\]

   2. Taylor expanded around 0 16.2

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

   3. Simplified 16.2

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

4. Final simplification 5.2

   \[\leadsto \begin{array}{l} \mathbf{if}\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y} \leq 1:\\ \;\;\;\;\frac{\left(x - y\right) \cdot \left(x + y\right)}{x \cdot x + y \cdot y}\\ \mathbf{else}:\\ \;\;\;\;-1\\ \end{array}\]

Reproduce

herbie shell --seed 2021042 
(FPCore (x y)
  :name "Kahan p9 Example"
  :precision binary64
  :pre (and (< 0.0 x 1.0) (< y 1.0))

  :herbie-target
  (if (< 0.5 (fabs (/ x y)) 2.0) (/ (* (- x y) (+ x y)) (+ (* x x) (* y y))) (- 1.0 (/ 2.0 (+ 1.0 (* (/ x y) (/ x y))))))

  (/ (* (- x y) (+ x y)) (+ (* x x) (* y y))))