Average Error: 19.9 → 0.8
Time: 34.2s
Precision: 64
Internal Precision: 128
\[\frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}}\]
↓
\[\begin{array}{l} \mathbf{if}\;x \le 0.0002627851237806562:\\ \;\;\;\;\frac{\sqrt{\frac{1}{x} - \frac{1}{1 + x}}}{\frac{\frac{1}{\sqrt{1 + x}} + \frac{1}{\sqrt{x}}}{\sqrt{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} - \frac{1}{\sqrt{1 + x}} \cdot \frac{1}{\sqrt{1 + x}}}}}\\ \mathbf{else}:\\ \;\;\;\;\frac{1}{\frac{(x \cdot \left(\frac{\frac{1 + x}{\sqrt{x}}}{x}\right) + \left(\frac{x}{\sqrt{1 + x}}\right))_*}{\left(\frac{1}{\sqrt{1 + x}} \cdot \frac{1}{\sqrt{1 + x}} - \frac{1}{\sqrt{1 + x}} \cdot \frac{1}{\sqrt{x}}\right) + \frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}}}}\\ \end{array}\]

Error

Bits error versus x

Target

Original19.9
Target0.7
Herbie0.8
\[\frac{1}{\left(x + 1\right) \cdot \sqrt{x} + x \cdot \sqrt{x + 1}}\]

Derivation

  1. Split input into 2 regimes

  2. if x < 0.0002627851237806562

    1. Initial program 0.3

      \[\frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}}\]
    2. Using strategy rm

    3. Applied flip--0.3

      \[\leadsto \color{blue}{\frac{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}} \cdot \frac{1}{\sqrt{x + 1}}}{\frac{1}{\sqrt{x}} + \frac{1}{\sqrt{x + 1}}}}\]
    4. Using strategy rm

    5. Applied add-sqr-sqrt0.3

      \[\leadsto \frac{\color{blue}{\sqrt{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}} \cdot \frac{1}{\sqrt{x + 1}}} \cdot \sqrt{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}} \cdot \frac{1}{\sqrt{x + 1}}}}}{\frac{1}{\sqrt{x}} + \frac{1}{\sqrt{x + 1}}}\]

    6. Applied associate-/l*0.3

      \[\leadsto \color{blue}{\frac{\sqrt{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}} \cdot \frac{1}{\sqrt{x + 1}}}}{\frac{\frac{1}{\sqrt{x}} + \frac{1}{\sqrt{x + 1}}}{\sqrt{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}} \cdot \frac{1}{\sqrt{x + 1}}}}}}\]

    7. Simplified0.2

      \[\leadsto \frac{\color{blue}{\sqrt{\frac{1}{x} - \frac{1}{x + 1}}}}{\frac{\frac{1}{\sqrt{x}} + \frac{1}{\sqrt{x + 1}}}{\sqrt{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}} \cdot \frac{1}{\sqrt{x + 1}}}}}\]

    if 0.0002627851237806562 < x

    1. Initial program 39.0

      \[\frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}}\]
    2. Using strategy rm

    3. Applied flip--39.0

      \[\leadsto \color{blue}{\frac{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}} \cdot \frac{1}{\sqrt{x + 1}}}{\frac{1}{\sqrt{x}} + \frac{1}{\sqrt{x + 1}}}}\]
    4. Using strategy rm

    5. Applied frac-times48.9

      \[\leadsto \frac{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} - \color{blue}{\frac{1 \cdot 1}{\sqrt{x + 1} \cdot \sqrt{x + 1}}}}{\frac{1}{\sqrt{x}} + \frac{1}{\sqrt{x + 1}}}\]

    6. Applied frac-times39.0

      \[\leadsto \frac{\color{blue}{\frac{1 \cdot 1}{\sqrt{x} \cdot \sqrt{x}}} - \frac{1 \cdot 1}{\sqrt{x + 1} \cdot \sqrt{x + 1}}}{\frac{1}{\sqrt{x}} + \frac{1}{\sqrt{x + 1}}}\]

    7. Applied frac-sub38.5

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

    8. Simplified11.1

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

    9. Simplified10.9

      \[\leadsto \frac{\frac{1}{\color{blue}{(x \cdot x + x)_*}}}{\frac{1}{\sqrt{x}} + \frac{1}{\sqrt{x + 1}}}\]
    10. Using strategy rm

    11. Applied associate-/l/10.9

      \[\leadsto \color{blue}{\frac{1}{\left(\frac{1}{\sqrt{x}} + \frac{1}{\sqrt{x + 1}}\right) \cdot (x \cdot x + x)_*}}\]
    12. Using strategy rm

    13. Applied flip3-+29.5

      \[\leadsto \frac{1}{\color{blue}{\frac{{\left(\frac{1}{\sqrt{x}}\right)}^{3} + {\left(\frac{1}{\sqrt{x + 1}}\right)}^{3}}{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} + \left(\frac{1}{\sqrt{x + 1}} \cdot \frac{1}{\sqrt{x + 1}} - \frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x + 1}}\right)}} \cdot (x \cdot x + x)_*}\]

    14. Applied associate-*l/29.5

      \[\leadsto \frac{1}{\color{blue}{\frac{\left({\left(\frac{1}{\sqrt{x}}\right)}^{3} + {\left(\frac{1}{\sqrt{x + 1}}\right)}^{3}\right) \cdot (x \cdot x + x)_*}{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} + \left(\frac{1}{\sqrt{x + 1}} \cdot \frac{1}{\sqrt{x + 1}} - \frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x + 1}}\right)}}}\]

    15. Simplified1.3

      \[\leadsto \frac{1}{\frac{\color{blue}{(x \cdot \left(\frac{\frac{x + 1}{\sqrt{x}}}{x}\right) + \left(\frac{x}{\sqrt{x + 1}}\right))_*}}{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} + \left(\frac{1}{\sqrt{x + 1}} \cdot \frac{1}{\sqrt{x + 1}} - \frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x + 1}}\right)}}\]
  3. Recombined 2 regimes into one program.

  4. Final simplification0.8

    \[\leadsto \begin{array}{l} \mathbf{if}\;x \le 0.0002627851237806562:\\ \;\;\;\;\frac{\sqrt{\frac{1}{x} - \frac{1}{1 + x}}}{\frac{\frac{1}{\sqrt{1 + x}} + \frac{1}{\sqrt{x}}}{\sqrt{\frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}} - \frac{1}{\sqrt{1 + x}} \cdot \frac{1}{\sqrt{1 + x}}}}}\\ \mathbf{else}:\\ \;\;\;\;\frac{1}{\frac{(x \cdot \left(\frac{\frac{1 + x}{\sqrt{x}}}{x}\right) + \left(\frac{x}{\sqrt{1 + x}}\right))_*}{\left(\frac{1}{\sqrt{1 + x}} \cdot \frac{1}{\sqrt{1 + x}} - \frac{1}{\sqrt{1 + x}} \cdot \frac{1}{\sqrt{x}}\right) + \frac{1}{\sqrt{x}} \cdot \frac{1}{\sqrt{x}}}}\\ \end{array}\]

Reproduce

herbie shell --seed 2019010 +o rules:numerics
(FPCore (x)
  :name "2isqrt (example 3.6)"

  :herbie-target
  (/ 1 (+ (* (+ x 1) (sqrt x)) (* x (sqrt (+ x 1)))))

  (- (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))

Details

Time bar (total: 33.6s)Debug log

sample101.0ms

Algorithm
intervals

simplify6.0ms

Counts
1 → 1
Calls
1 calls:
Slowest
6.0ms
(- (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1))))

prune5.0ms

Pruning

1 alts after pruning (1 fresh and 0 done)

Merged error: 19.2b

localize15.0ms

Local error

Found 4 expressions with local error:

3.3b
(- (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1))))
0.3b
(/ 1 (sqrt x))
0.1b
(/ 1 (sqrt (+ x 1)))
0.0b
(sqrt (+ x 1))

rewrite28.0ms

Algorithm
rewrite-expression-head
Rules
24×prod-diff
23×*-un-lft-identity
22×add-sqr-sqrt
19×add-cube-cbrt
17×div-inv
12×sqrt-div
10×associate-/r/
9×associate-/r*
6×add-log-exp
6×flip-+
6×sqrt-prod
6×add-exp-log
6×flip3-+
6×pow1
4×distribute-lft-out--
4×pow-flip
4×log1p-expm1-u
4×fma-neg
4×add-cbrt-cube
4×expm1-log1p-u
3×pow1/2
2×inv-pow
2×frac-2neg
2×clear-num
2×rec-exp
1×difference-of-squares
1×flip--
1×frac-sub
1×diff-log
1×flip3--
1×sub-neg
1×rem-sqrt-square
Counts
4 → 107
Calls
4 calls:
Slowest
6.0ms
(- (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1))))
2.0ms
(/ 1 (sqrt (+ x 1)))
1.0ms
(sqrt (+ x 1))
1.0ms
(/ 1 (sqrt x))

series78.0ms

Counts
4 → 12
Calls
4 calls:
Slowest
29.0ms
(- (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1))))
20.0ms
(/ 1 (sqrt (+ x 1)))
17.0ms
(sqrt (+ x 1))
11.0ms
(/ 1 (sqrt x))

simplify3.4s

Counts
92 → 119
Calls
92 calls:
Slowest
182.0ms
(fma (- (sqrt (+ (* x x) (- (* 1 1) (* x 1))))) (/ 1 (sqrt (+ (pow x 3) (pow 1 3)))) (* (sqrt (+ (* x x) (- (* 1 1) (* x 1)))) (/ 1 (sqrt (+ (pow x 3) (pow 1 3))))))
170.0ms
(fma (- (sqrt (+ (* x x) (- (* 1 1) (* x 1))))) (/ 1 (sqrt (+ (pow x 3) (pow 1 3)))) (* (sqrt (+ (* x x) (- (* 1 1) (* x 1)))) (/ 1 (sqrt (+ (pow x 3) (pow 1 3))))))
169.0ms
(fma (sqrt (/ 1 (sqrt x))) (sqrt (/ 1 (sqrt x))) (- (* (sqrt (+ (* x x) (- (* 1 1) (* x 1)))) (/ 1 (sqrt (+ (pow x 3) (pow 1 3)))))))
162.0ms
(fma (- (sqrt (+ (* x x) (- (* 1 1) (* x 1))))) (/ 1 (sqrt (+ (pow x 3) (pow 1 3)))) (* (sqrt (+ (* x x) (- (* 1 1) (* x 1)))) (/ 1 (sqrt (+ (pow x 3) (pow 1 3))))))
160.0ms
(fma (- (sqrt (- x 1))) (/ 1 (sqrt (- (* x x) (* 1 1)))) (* (sqrt (- x 1)) (/ 1 (sqrt (- (* x x) (* 1 1))))))

prune950.0ms

Pruning

10 alts after pruning (10 fresh and 0 done)

Merged error: 18.6b

localize16.0ms

Local error

Found 4 expressions with local error:

3.3b
(- (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1)))))
0.5b
(* (/ 1 (sqrt x)) (/ 1 (sqrt x)))
0.3b
(/ (- (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1))))) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
0.3b
(/ 1 (sqrt x))

rewrite69.0ms

Algorithm
rewrite-expression-head
Rules
40×*-un-lft-identity
32×frac-sub
28×times-frac
24×div-inv
20×distribute-lft-out
20×add-cube-cbrt
20×add-sqr-sqrt
18×associate-/l/
17×un-div-inv
17×associate-*r/
17×associate-*l/
17×frac-times
16×pow1
15×add-exp-log
12×pow-flip
10×associate-/r*
9×difference-of-squares
8×add-cbrt-cube
7×inv-pow
6×add-log-exp
6×pow-prod-up
5×pow1/2
5×rec-exp
4×associate-/l*
4×log1p-expm1-u
4×prod-exp
4×pow-prod-down
4×associate-*l*
4×associate-*r*
4×expm1-log1p-u
3×associate-/r/
2×flip--
2×flip3--
2×frac-2neg
2×clear-num
1×flip-+
1×cbrt-unprod
1×*-commutative
1×frac-add
1×prod-diff
1×div-exp
1×div-sub
1×diff-log
1×fma-neg
1×pow-plus
1×flip3-+
1×sub-neg
1×cbrt-undiv
1×pow2
Counts
4 → 166
Calls
4 calls:
Slowest
42.0ms
(/ (- (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1))))) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
11.0ms
(- (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1)))))
10.0ms
(* (/ 1 (sqrt x)) (/ 1 (sqrt x)))
2.0ms
(/ 1 (sqrt x))

series96.0ms

Counts
4 → 12
Calls
4 calls:
Slowest
49.0ms
(/ (- (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1))))) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
27.0ms
(- (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1)))))
11.0ms
(/ 1 (sqrt x))
9.0ms
(* (/ 1 (sqrt x)) (/ 1 (sqrt x)))

simplify16.4s

Counts
179 → 178
Calls
179 calls:
Slowest
589.0ms
(- (* (* (/ 1 (sqrt x)) 1) (* (sqrt (+ x 1)) (sqrt (+ x 1)))) (* (sqrt x) (* 1 1)))
421.0ms
(- (* (/ 1 (sqrt x)) (* (sqrt (+ x 1)) (sqrt (+ x 1)))) (* (sqrt x) (* 1 1)))
405.0ms
(/ (- (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1))))) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
383.0ms
(/ (- (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1))))) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
382.0ms
(/ (- (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1))))) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))

prune1.1s

Pruning

5 alts after pruning (5 fresh and 0 done)

Merged error: 4.7b

localize9.0ms

Local error

Found 4 expressions with local error:

4.6b
(/ (/ 1 (fma x x x)) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
0.3b
(/ 1 (fma x x x))
0.3b
(/ 1 (sqrt x))
0.1b
(/ 1 (sqrt (+ x 1)))

rewrite14.0ms

Algorithm
rewrite-expression-head
Rules
41×*-un-lft-identity
32×div-inv
28×times-frac
21×add-cube-cbrt
21×add-sqr-sqrt
20×distribute-lft-out
19×associate-/r*
11×add-exp-log
7×pow1
6×add-cbrt-cube
5×pow-flip
5×associate-/r/
4×add-log-exp
4×associate-/l*
4×log1p-expm1-u
4×frac-2neg
4×clear-num
4×rec-exp
4×expm1-log1p-u
3×inv-pow
3×sqrt-prod
2×flip-+
2×div-exp
2×sqrt-div
2×pow1/2
2×flip3-+
1×associate-/l/
1×frac-add
1×cbrt-undiv
Counts
4 → 119
Calls
4 calls:
Slowest
9.0ms
(/ (/ 1 (fma x x x)) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
1.0ms
(/ 1 (sqrt (+ x 1)))
1.0ms
(/ 1 (fma x x x))
1.0ms
(/ 1 (sqrt x))

series88.0ms

Counts
4 → 12
Calls
4 calls:
Slowest
54.0ms
(/ (/ 1 (fma x x x)) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
12.0ms
(/ 1 (sqrt (+ x 1)))
11.0ms
(/ 1 (sqrt x))
11.0ms
(/ 1 (fma x x x))

simplify5.1s

Counts
102 → 131
Calls
102 calls:
Slowest
385.0ms
(/ (/ 1 (fma x x x)) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
340.0ms
(/ (/ 1 (fma x x x)) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
340.0ms
(/ (/ 1 (fma x x x)) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
338.0ms
(/ (/ 1 (fma x x x)) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))
338.0ms
(/ (/ 1 (fma x x x)) (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))))

prune838.0ms

Pruning

9 alts after pruning (9 fresh and 0 done)

Merged error: 4.6b

localize6.0ms

Local error

Found 4 expressions with local error:

4.6b
(* (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))) (fma x x x))
0.5b
(/ 1 (* (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))) (fma x x x)))
0.3b
(/ 1 (sqrt x))
0.1b
(/ 1 (sqrt (+ x 1)))

rewrite23.0ms

Algorithm
rewrite-expression-head
Rules
13×*-un-lft-identity
11×add-exp-log
11×pow1
10×associate-/r*
9×add-cube-cbrt
9×add-sqr-sqrt
7×div-inv
7×associate-*l*
6×pow-flip
6×associate-*l/
6×add-cbrt-cube
5×associate-/r/
4×add-log-exp
4×distribute-lft-out
4×log1p-expm1-u
4×rec-exp
4×expm1-log1p-u
3×inv-pow
3×flip-+
3×sqrt-prod
3×associate-*r*
3×flip3-+
3×frac-2neg
3×clear-num
2×fma-udef
2×prod-exp
2×frac-add
2×pow-prod-down
2×sqrt-div
2×pow1/2
1×cbrt-unprod
1×*-commutative
1×distribute-lft-in
1×distribute-rgt-in
Counts
4 → 92
Calls
4 calls:
Slowest
13.0ms
(* (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))) (fma x x x))
6.0ms
(/ 1 (* (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))) (fma x x x)))
1.0ms
(/ 1 (sqrt (+ x 1)))
1.0ms
(/ 1 (sqrt x))

series115.0ms

Counts
4 → 12
Calls
4 calls:
Slowest
52.0ms
(/ 1 (* (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))) (fma x x x)))
40.0ms
(* (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))) (fma x x x))
12.0ms
(/ 1 (sqrt (+ x 1)))
11.0ms
(/ 1 (sqrt x))

simplify2.1s

Counts
46 → 104
Calls
46 calls:
Slowest
651.0ms
(* (+ (pow (/ 1 (sqrt x)) 3) (pow (/ 1 (sqrt (+ x 1))) 3)) (fma x x x))
556.0ms
(* (+ (* 1 (sqrt (+ x 1))) (* (sqrt x) 1)) (fma x x x))
247.0ms
(* (+ (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1)))) (fma x x x))
198.0ms
(+ (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (- (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1)))) (* (/ 1 (sqrt x)) (/ 1 (sqrt (+ x 1))))))
133.0ms
(* (- (* (/ 1 (sqrt x)) (/ 1 (sqrt x))) (* (/ 1 (sqrt (+ x 1))) (/ 1 (sqrt (+ x 1))))) (fma x x x))

prune614.0ms

Pruning

9 alts after pruning (8 fresh and 1 done)

Merged error: 0.3b

regimes51.0ms

Accuracy

95.4% (0.2b remaining)

Error of 0.8b against oracle of 0.5b and baseline of 5.7b

bsearch30.0ms

end0.0ms

sample2.4s

Algorithm
intervals