2isqrt (example 3.6)

Average Error: 19.4 → 0.5

Time: 17.4min

Precision: binary64

• Falling back on racket egraph because egg-herbie package not installed

Math

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

↓

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

C

double code(double x) {
	return ((double) ((1.0 / ((double) sqrt(x))) - (1.0 / ((double) sqrt(((double) (x + 1.0)))))));
}

↓

double code(double x) {
	return ((double) (((double) sqrt(((((double) (1.0 * 1.0)) / ((double) (x + 1.0))) / ((double) ((x / ((double) sqrt(((double) (x + 1.0))))) + (x / ((double) sqrt(x)))))))) * ((double) (((double) sqrt((((double) sqrt((((double) (1.0 * 1.0)) / ((double) (x + 1.0))))) / ((double) sqrt(x))))) * ((double) sqrt((((double) sqrt((((double) (1.0 * 1.0)) / ((double) (x + 1.0))))) / ((double) ((((double) sqrt(x)) / ((double) sqrt(((double) (x + 1.0))))) + 1.0)))))))));
}

Error

Bits error versus x

Target

Original	19.4
Target	0.7
Herbie	0.5

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

Derivation

1. Initial program 19.4

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

3. Applied flip-- 19.4

   \[\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. Simplified 19.4

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

6. Applied frac-sub 18.9

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

7. Simplified 5.5

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

9. Applied add-sqr-sqrt 5.7

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

10. Simplified 5.6

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

11. Simplified 0.6

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

13. Applied *-un-lft-identity 0.6

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

14. Applied sqrt-prod 0.6

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

15. Applied add-sqr-sqrt 0.5

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

16. Applied times-frac 0.5

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

17. Applied *-un-lft-identity 0.5

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

18. Applied sqrt-prod 0.5

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

19. Applied add-sqr-sqrt 0.5

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

20. Applied times-frac 0.5

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

21. Applied distribute-lft-out 0.5

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

22. Applied add-sqr-sqrt 0.5

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

23. Applied times-frac 0.5

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

24. Applied sqrt-prod 0.5

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

25. Simplified 0.5

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

26. Simplified 0.5

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

27. Final simplification 0.5

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

Reproduce

herbie shell --seed 2020181 
(FPCore (x)
  :name "2isqrt (example 3.6)"
  :precision binary64

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

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