commit df420b8a1796a09dc70089480210c5249b3527a1
parent 02f19810d65aef58bbf54f1fc629d22d354e62de
Author: Andrew Laack <andrew@laack.co>
Date: Mon, 17 Aug 2026 18:28:35 -0500
Headers
Diffstat:
1 file changed, 33 insertions(+), 2 deletions(-)
diff --git a/ch1_self_learning/newton_sqrt.ml b/ch1_self_learning/newton_sqrt.ml
@@ -1,3 +1,35 @@
+(* 15
+
+NEW IDEA: recursion that stops when it is close enough, because floats cannot
+be compared for equality.
+
+newton_sqrt x approximates the square root of x >= 0 by Newton's method. Start
+from a guess and repeatedly improve it with
+
+ next = (guess +. x /. guess) /. 2.
+
+Stop when the guess is good enough, when abs_float (guess *. guess -. x) is
+below a small tolerance such as 1e-10. Note that x itself works as a starting
+guess, except for x = 0.
+
+Do not write guess *. guess = x. Floats are approximations, that test would
+loop forever, and it is the same reason 0.1 +. 0.2 = 0.3 is false in every
+language with binary floats.
+
+newton_sqrt 2.0 is about 1.4142135, newton_sqrt 81.0 = 9.0,
+newton_sqrt 0.0 = 0.0.
+
+Afterwards try newton_sqrt 1e12 and work out why an absolute tolerance of
+1e-10 cannot terminate there. A double has about 16 significant digits, so near
+1e12 the gap between neighbouring representable values is already larger than
+1e-10. Fixing it means comparing relatively, for instance stopping when
+successive guesses barely change.
+
+*)
+
+#use "topfind";;
+#require "qcheck";;
+
let abs_diff x y = abs_float (x -. y);;
let newton_sqrt x =
@@ -13,4 +45,4 @@ let reverse = QCheck.Test.make
(QCheck.float_range 0. 100000.)
(fun n -> (abs_diff n ((newton_sqrt n) *. (newton_sqrt n))) < 0.00001);;
-QCheck_base_runner.run_tests [ reverse ];;-
\ No newline at end of file
+QCheck_base_runner.run_tests [ reverse ];;
