2isqrt (example 3.6)

Average Error: 19.6 → 0.3

Time: 16.9s

Precision: 64

Math

\[\frac{1}{\sqrt{x}} - \frac{1}{\sqrt{x + 1}}\]

↓

\[\frac{\sqrt{1}}{\sqrt{x}} \cdot \frac{\sqrt{1}}{\mathsf{fma}\left(\sqrt{x} \cdot \sqrt{1 + x}, 1, \left(1 + x\right) \cdot 1\right)}\]

C

double f(double x) {
        double r6152969 = 1.0;
        double r6152970 = x;
        double r6152971 = sqrt(r6152970);
        double r6152972 = r6152969 / r6152971;
        double r6152973 = r6152970 + r6152969;
        double r6152974 = sqrt(r6152973);
        double r6152975 = r6152969 / r6152974;
        double r6152976 = r6152972 - r6152975;
        return r6152976;
}

↓

double f(double x) {
        double r6152977 = 1.0;
        double r6152978 = sqrt(r6152977);
        double r6152979 = x;
        double r6152980 = sqrt(r6152979);
        double r6152981 = r6152978 / r6152980;
        double r6152982 = r6152977 + r6152979;
        double r6152983 = sqrt(r6152982);
        double r6152984 = r6152980 * r6152983;
        double r6152985 = r6152982 * r6152977;
        double r6152986 = fma(r6152984, r6152977, r6152985);
        double r6152987 = r6152978 / r6152986;
        double r6152988 = r6152981 * r6152987;
        return r6152988;
}

Error

Bits error versus x

Target

Original	19.6
Target	0.6
Herbie	0.3

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

Derivation

1. Initial program 19.6

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

3. Applied frac-sub 19.6

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

5. Applied flip-- 19.4

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

6. Taylor expanded around 0 0.4

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

8. Applied *-un-lft-identity 0.4

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

9. Applied add-sqr-sqrt 0.4

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

10. Applied times-frac 0.4

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

11. Applied times-frac 0.4

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

12. Simplified 0.4

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

13. Simplified 0.3

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

14. Final simplification 0.3

    \[\leadsto \frac{\sqrt{1}}{\sqrt{x}} \cdot \frac{\sqrt{1}}{\mathsf{fma}\left(\sqrt{x} \cdot \sqrt{1 + x}, 1, \left(1 + x\right) \cdot 1\right)}\]

Reproduce

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

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

  (- (/ 1.0 (sqrt x)) (/ 1.0 (sqrt (+ x 1.0)))))