Average Error: 33.2 → 6.8
Time: 31.5s
Precision: 64
Internal Precision: 128
\[\frac{\left(-b\right) - \sqrt{b \cdot b - 4 \cdot \left(a \cdot c\right)}}{2 \cdot a}\]
↓
\[\begin{array}{l} \mathbf{if}\;b \le -8.276414657528413 \cdot 10^{+95}:\\ \;\;\;\;\frac{-c}{b}\\ \mathbf{elif}\;b \le -6.321237892731252 \cdot 10^{-282}:\\ \;\;\;\;\frac{2 \cdot c}{\sqrt{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}} \cdot \sqrt{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}}\\ \mathbf{elif}\;b \le 4.2775014312729314 \cdot 10^{+106}:\\ \;\;\;\;\left(\left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}\right) \cdot \frac{1}{a \cdot 2}\\ \mathbf{else}:\\ \;\;\;\;-\frac{b}{a}\\ \end{array}\]

Error

Bits error versus a

Bits error versus b

Bits error versus c

Target

Original33.2
Target20.7
Herbie6.8
\[\begin{array}{l} \mathbf{if}\;b \lt 0:\\ \;\;\;\;\frac{c}{a \cdot \frac{\left(-b\right) + \sqrt{b \cdot b - 4 \cdot \left(a \cdot c\right)}}{2 \cdot a}}\\ \mathbf{else}:\\ \;\;\;\;\frac{\left(-b\right) - \sqrt{b \cdot b - 4 \cdot \left(a \cdot c\right)}}{2 \cdot a}\\ \end{array}\]

Derivation

  1. Split input into 4 regimes

  2. if b < -8.276414657528413e+95

    1. Initial program 58.1

      \[\frac{\left(-b\right) - \sqrt{b \cdot b - 4 \cdot \left(a \cdot c\right)}}{2 \cdot a}\]

    2. Simplified58.1

      \[\leadsto \color{blue}{\frac{\left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}{2 \cdot a}}\]
    3. Using strategy rm

    4. Applied div-inv58.1

      \[\leadsto \color{blue}{\left(\left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}\right) \cdot \frac{1}{2 \cdot a}}\]

    5. Taylor expanded around -inf 2.4

      \[\leadsto \color{blue}{-1 \cdot \frac{c}{b}}\]

    6. Simplified2.4

      \[\leadsto \color{blue}{\frac{-c}{b}}\]

    if -8.276414657528413e+95 < b < -6.321237892731252e-282

    1. Initial program 32.3

      \[\frac{\left(-b\right) - \sqrt{b \cdot b - 4 \cdot \left(a \cdot c\right)}}{2 \cdot a}\]

    2. Simplified32.2

      \[\leadsto \color{blue}{\frac{\left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}{2 \cdot a}}\]
    3. Using strategy rm

    4. Applied div-inv32.3

      \[\leadsto \color{blue}{\left(\left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}\right) \cdot \frac{1}{2 \cdot a}}\]
    5. Using strategy rm

    6. Applied flip--32.4

      \[\leadsto \color{blue}{\frac{\left(-b\right) \cdot \left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*} \cdot \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}} \cdot \frac{1}{2 \cdot a}\]

    7. Applied associate-*l/32.4

      \[\leadsto \color{blue}{\frac{\left(\left(-b\right) \cdot \left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*} \cdot \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}\right) \cdot \frac{1}{2 \cdot a}}{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}}\]

    8. Simplified15.1

      \[\leadsto \frac{\color{blue}{\left(0 - \left(c \cdot a\right) \cdot -4\right) \cdot \frac{\frac{1}{2}}{a}}}{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}\]

    9. Taylor expanded around inf 8.3

      \[\leadsto \frac{\color{blue}{2 \cdot c}}{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}\]
    10. Using strategy rm

    11. Applied add-sqr-sqrt8.6

      \[\leadsto \frac{2 \cdot c}{\color{blue}{\sqrt{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}} \cdot \sqrt{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}}}\]

    if -6.321237892731252e-282 < b < 4.2775014312729314e+106

    1. Initial program 9.6

      \[\frac{\left(-b\right) - \sqrt{b \cdot b - 4 \cdot \left(a \cdot c\right)}}{2 \cdot a}\]

    2. Simplified9.6

      \[\leadsto \color{blue}{\frac{\left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}{2 \cdot a}}\]
    3. Using strategy rm

    4. Applied div-inv9.7

      \[\leadsto \color{blue}{\left(\left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}\right) \cdot \frac{1}{2 \cdot a}}\]

    if 4.2775014312729314e+106 < b

    1. Initial program 46.2

      \[\frac{\left(-b\right) - \sqrt{b \cdot b - 4 \cdot \left(a \cdot c\right)}}{2 \cdot a}\]

    2. Simplified46.1

      \[\leadsto \color{blue}{\frac{\left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}{2 \cdot a}}\]
    3. Using strategy rm

    4. Applied div-inv46.2

      \[\leadsto \color{blue}{\left(\left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}\right) \cdot \frac{1}{2 \cdot a}}\]
    5. Using strategy rm

    6. Applied flip--61.3

      \[\leadsto \color{blue}{\frac{\left(-b\right) \cdot \left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*} \cdot \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}} \cdot \frac{1}{2 \cdot a}\]

    7. Applied associate-*l/61.3

      \[\leadsto \color{blue}{\frac{\left(\left(-b\right) \cdot \left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*} \cdot \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}\right) \cdot \frac{1}{2 \cdot a}}{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}}\]

    8. Simplified61.5

      \[\leadsto \frac{\color{blue}{\left(0 - \left(c \cdot a\right) \cdot -4\right) \cdot \frac{\frac{1}{2}}{a}}}{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}\]

    9. Taylor expanded around 0 4.0

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

    10. Simplified4.0

      \[\leadsto \color{blue}{\frac{-b}{a}}\]
  3. Recombined 4 regimes into one program.

  4. Final simplification6.8

    \[\leadsto \begin{array}{l} \mathbf{if}\;b \le -8.276414657528413 \cdot 10^{+95}:\\ \;\;\;\;\frac{-c}{b}\\ \mathbf{elif}\;b \le -6.321237892731252 \cdot 10^{-282}:\\ \;\;\;\;\frac{2 \cdot c}{\sqrt{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}} \cdot \sqrt{\left(-b\right) + \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}}}\\ \mathbf{elif}\;b \le 4.2775014312729314 \cdot 10^{+106}:\\ \;\;\;\;\left(\left(-b\right) - \sqrt{(\left(-4 \cdot a\right) \cdot c + \left(b \cdot b\right))_*}\right) \cdot \frac{1}{a \cdot 2}\\ \mathbf{else}:\\ \;\;\;\;-\frac{b}{a}\\ \end{array}\]

Reproduce

herbie shell --seed 2019008 +o rules:numerics
(FPCore (a b c)
  :name "The quadratic formula (r2)"

  :herbie-target
  (if (< b 0) (/ c (* a (/ (+ (- b) (sqrt (- (* b b) (* 4 (* a c))))) (* 2 a)))) (/ (- (- b) (sqrt (- (* b b) (* 4 (* a c))))) (* 2 a)))

  (/ (- (- b) (sqrt (- (* b b) (* 4 (* a c))))) (* 2 a)))

Details

Time bar (total: 30.4s)Debug log

sample124.0ms

Algorithm
intervals

simplify90.0ms

Counts
1 → 1
Calls

1 calls. Slowest were:

90.0ms
(/ (- (- b) (sqrt (- (* b b) (* 4 (* a c))))) (* 2 a))

prune16.0ms

Pruning

2 alts after pruning (2 fresh and 0 done)

Merged error: 33.9b

localize29.0ms

Local error

Found 4 expressions with local error:

23.7b
(sqrt (fma (* -4 a) c (* b b)))
0.8b
(- (- b) (sqrt (fma (* -4 a) c (* b b))))
0.1b
(/ (- (- b) (sqrt (fma (* -4 a) c (* b b)))) (* 2 a))
0.0b
(fma (* -4 a) c (* b b))

rewrite36.0ms

Algorithm
rewrite-expression-head
Counts
4 → 100
Calls

4 calls. Slowest were:

16.0ms
(/ (- (- b) (sqrt (fma (* -4 a) c (* b b)))) (* 2 a))
10.0ms
(- (- b) (sqrt (fma (* -4 a) c (* b b))))
8.0ms
(sqrt (fma (* -4 a) c (* b b)))

series210.0ms

Counts
4 → 12
Calls

4 calls. Slowest were:

79.0ms
(/ (- (- b) (sqrt (fma (* -4 a) c (* b b)))) (* 2 a))
56.0ms
(sqrt (fma (* -4 a) c (* b b)))
45.0ms
(- (- b) (sqrt (fma (* -4 a) c (* b b))))
30.0ms
(fma (* -4 a) c (* b b))

simplify3.7s

Counts
93 → 112
Calls

93 calls. Slowest were:

231.0ms
(- (* (- b) (- b)) (* (sqrt (fma (* -4 a) c (* b b))) (sqrt (fma (* -4 a) c (* b b)))))
198.0ms
(- (pow (- b) 3) (pow (sqrt (fma (* -4 a) c (* b b))) 3))
107.0ms
(- (* 2 (/ (* a c) b)) (* 2 b))

prune1.2s

Pruning

9 alts after pruning (9 fresh and 0 done)

Merged error: 6.6b

localize7.0ms

Local error

Found 4 expressions with local error:

23.7b
(sqrt (fma (* -4 a) c (* b b)))
0.8b
(- (- b) (sqrt (fma (* -4 a) c (* b b))))
0.2b
(* (- (- b) (sqrt (fma (* -4 a) c (* b b)))) (/ 1 (* 2 a)))
0.0b
(fma (* -4 a) c (* b b))

rewrite31.0ms

Algorithm
rewrite-expression-head
Counts
4 → 100
Calls

4 calls. Slowest were:

18.0ms
(* (- (- b) (sqrt (fma (* -4 a) c (* b b)))) (/ 1 (* 2 a)))
10.0ms
(- (- b) (sqrt (fma (* -4 a) c (* b b))))
2.0ms
(sqrt (fma (* -4 a) c (* b b)))

series182.0ms

Counts
4 → 12
Calls

4 calls. Slowest were:

60.0ms
(* (- (- b) (sqrt (fma (* -4 a) c (* b b)))) (/ 1 (* 2 a)))
51.0ms
(- (- b) (sqrt (fma (* -4 a) c (* b b))))
40.0ms
(sqrt (fma (* -4 a) c (* b b)))
31.0ms
(fma (* -4 a) c (* b b))

simplify5.5s

Counts
92 → 112
Calls

92 calls. Slowest were:

764.0ms
(* (- (* (- b) (- b)) (* (sqrt (fma (* -4 a) c (* b b))) (sqrt (fma (* -4 a) c (* b b))))) 1)
538.0ms
(* (- (pow (- b) 3) (pow (sqrt (fma (* -4 a) c (* b b))) 3)) 1)
413.0ms
(* (- (- b) (sqrt (fma (* -4 a) c (* b b)))) (/ 1 (* 2 a)))

prune1.3s

Pruning

10 alts after pruning (9 fresh and 1 done)

Merged error: 6.6b

localize37.0ms

Local error

Found 4 expressions with local error:

23.7b
(sqrt (fma (* -4 a) c (* b b)))
15.4b
(* (- 0 (* (* c a) -4)) (/ 1/2 a))
0.9b
(+ (- b) (sqrt (fma (* -4 a) c (* b b))))
0.1b
(/ (* (- 0 (* (* c a) -4)) (/ 1/2 a)) (+ (- b) (sqrt (fma (* -4 a) c (* b b)))))

rewrite38.0ms

Algorithm
rewrite-expression-head
Counts
4 → 92
Calls

4 calls. Slowest were:

19.0ms
(/ (* (- 0 (* (* c a) -4)) (/ 1/2 a)) (+ (- b) (sqrt (fma (* -4 a) c (* b b)))))
8.0ms
(+ (- b) (sqrt (fma (* -4 a) c (* b b))))
8.0ms
(* (- 0 (* (* c a) -4)) (/ 1/2 a))

series241.0ms

Counts
4 → 12
Calls

4 calls. Slowest were:

135.0ms
(/ (* (- 0 (* (* c a) -4)) (/ 1/2 a)) (+ (- b) (sqrt (fma (* -4 a) c (* b b)))))
54.0ms
(+ (- b) (sqrt (fma (* -4 a) c (* b b))))
48.0ms
(sqrt (fma (* -4 a) c (* b b)))
5.0ms
(* (- 0 (* (* c a) -4)) (/ 1/2 a))

simplify8.2s

Counts
61 → 104
Calls

61 calls. Slowest were:

693.0ms
(* (- 0 (* (* c a) -4)) (/ 1/2 a))
538.0ms
(* (- (pow 0 3) (pow (* (* c a) -4) 3)) (/ 1/2 a))
505.0ms
(* (- (pow 0 3) (pow (* (* c a) -4) 3)) (/ 1/2 a))

prune1.2s

Pruning

9 alts after pruning (8 fresh and 1 done)

Merged error: 6.6b

localize6.0ms

Local error

Found 4 expressions with local error:

23.7b
(sqrt (fma (* -4 a) c (* b b)))
0.9b
(+ (- b) (sqrt (fma (* -4 a) c (* b b))))
0.1b
(/ (* 2 c) (+ (- b) (sqrt (fma (* -4 a) c (* b b)))))
0.0b
(fma (* -4 a) c (* b b))

rewrite13.0ms

Algorithm
rewrite-expression-head
Counts
4 → 68
Calls

4 calls. Slowest were:

7.0ms
(/ (* 2 c) (+ (- b) (sqrt (fma (* -4 a) c (* b b)))))
4.0ms
(+ (- b) (sqrt (fma (* -4 a) c (* b b))))
1.0ms
(sqrt (fma (* -4 a) c (* b b)))

series335.0ms

Counts
4 → 12
Calls

4 calls. Slowest were:

186.0ms
(/ (* 2 c) (+ (- b) (sqrt (fma (* -4 a) c (* b b)))))
69.0ms
(+ (- b) (sqrt (fma (* -4 a) c (* b b))))
42.0ms
(sqrt (fma (* -4 a) c (* b b)))
37.0ms
(fma (* -4 a) c (* b b))

simplify1.4s

Counts
36 → 80
Calls

36 calls. Slowest were:

517.0ms
(+ (* (- b) (- b)) (- (* (sqrt (fma (* -4 a) c (* b b))) (sqrt (fma (* -4 a) c (* b b)))) (* (- b) (sqrt (fma (* -4 a) c (* b b))))))
108.0ms
(- (* 2 (/ (* a c) b)) (* 2 b))
107.0ms
(/ (* (* (* 2 c) (* 2 c)) (* 2 c)) (* (* (+ (- b) (sqrt (fma (* -4 a) c (* b b)))) (+ (- b) (sqrt (fma (* -4 a) c (* b b))))) (+ (- b) (sqrt (fma (* -4 a) c (* b b))))))

prune725.0ms

Pruning

8 alts after pruning (7 fresh and 1 done)

Merged error: 6.6b

regimes481.0ms

Accuracy

94.8% (1.3b remaining)

Error of 6.8b against oracle of 5.5b and baseline of 29.7b

bsearch871.0ms

end0.0ms

sample4.6s

Algorithm
intervals