2isqrt (example 3.6)

Average Error: 20.0 → 0.3

Time: 19.3s

Precision: 64

Math

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

↓

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

C

double f(double x) {
        double r6817583 = 1.0;
        double r6817584 = x;
        double r6817585 = sqrt(r6817584);
        double r6817586 = r6817583 / r6817585;
        double r6817587 = r6817584 + r6817583;
        double r6817588 = sqrt(r6817587);
        double r6817589 = r6817583 / r6817588;
        double r6817590 = r6817586 - r6817589;
        return r6817590;
}

↓

double f(double x) {
        double r6817591 = 1.0;
        double r6817592 = cbrt(r6817591);
        double r6817593 = r6817592 * r6817592;
        double r6817594 = x;
        double r6817595 = sqrt(r6817594);
        double r6817596 = r6817593 / r6817595;
        double r6817597 = r6817594 + r6817591;
        double r6817598 = sqrt(r6817597);
        double r6817599 = r6817595 * r6817591;
        double r6817600 = r6817591 * r6817597;
        double r6817601 = fma(r6817598, r6817599, r6817600);
        double r6817602 = r6817592 / r6817601;
        double r6817603 = r6817596 * r6817602;
        return r6817603;
}

Error

Bits error versus x

Target

Original	20.0
Target	0.8
Herbie	0.3

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

Derivation

1. Initial program 20.0

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

3. Applied frac-sub 20.0

   \[\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.8

   \[\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-cube-cbrt 0.4

   \[\leadsto \frac{\frac{\color{blue}{\left(\sqrt[3]{1} \cdot \sqrt[3]{1}\right) \cdot \sqrt[3]{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[3]{1} \cdot \sqrt[3]{1}}{1} \cdot \frac{\sqrt[3]{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[3]{1} \cdot \sqrt[3]{1}}{1}}{\sqrt{x}} \cdot \frac{\frac{\sqrt[3]{1}}{1 \cdot \sqrt{x + 1} + \sqrt{x} \cdot 1}}{\sqrt{x + 1}}}\]

12. Simplified 0.4

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

13. Simplified 0.3

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

14. Final simplification 0.3

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

Reproduce

herbie shell --seed 2019172 +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)))))