commit e5197c60ea61983cce2cd379f6c82ffc0563d366
parent df420b8a1796a09dc70089480210c5249b3527a1
Author: Andrew Laack <andrew@laack.co>
Date: Wed, 19 Aug 2026 20:43:21 -0500
Busiest collatz + newton's sqrt method
Diffstat:
1 file changed, 265 insertions(+), 0 deletions(-)
diff --git a/ch1_self_learning/exercises_p2.ipynb b/ch1_self_learning/exercises_p2.ipynb
@@ -0,0 +1,265 @@
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "ef154598-e0d1-4721-a171-f8cdb8340bc8",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "(* 15\n",
+ "\n",
+ "NEW IDEA: recursion that stops when it is close enough, because floats cannot\n",
+ "be compared for equality.\n",
+ "\n",
+ "newton_sqrt x approximates the square root of x >= 0 by Newton's method. Start\n",
+ "from a guess and repeatedly improve it with\n",
+ "\n",
+ " next = (guess +. x /. guess) /. 2.\n",
+ "\n",
+ "Stop when the guess is good enough, when abs_float (guess *. guess -. x) is\n",
+ "below a small tolerance such as 1e-10. Note that x itself works as a starting\n",
+ "guess, except for x = 0.\n",
+ "\n",
+ "Do not write guess *. guess = x. Floats are approximations, that test would\n",
+ "loop forever, and it is the same reason 0.1 +. 0.2 = 0.3 is false in every\n",
+ "language with binary floats.\n",
+ "\n",
+ "newton_sqrt 2.0 is about 1.4142135, newton_sqrt 81.0 = 9.0,\n",
+ "newton_sqrt 0.0 = 0.0.\n",
+ "\n",
+ "Afterwards try newton_sqrt 1e12 and work out why an absolute tolerance of\n",
+ "1e-10 cannot terminate there. A double has about 16 significant digits, so near\n",
+ "1e12 the gap between neighbouring representable values is already larger than\n",
+ "1e-10. Fixing it means comparing relatively, for instance stopping when\n",
+ "successive guesses barely change.\n",
+ "\n",
+ "*)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 54,
+ "id": "11e1e0c3-1f65-4251-998a-69804398e6a3",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "val abs_diff : float -> float -> float = <fun>\n"
+ ]
+ },
+ "execution_count": 54,
+ "metadata": {},
+ "output_type": "execute_result"
+ },
+ {
+ "data": {
+ "text/plain": [
+ "val newton_sqrt : float -> float = <fun>\n"
+ ]
+ },
+ "execution_count": 54,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "let abs_diff x y = abs_float (x -. y);;\n",
+ "\n",
+ "let newton_sqrt x = \n",
+ " let rec go guess = \n",
+ " let diff = abs_diff x (guess *. guess) in\n",
+ " if diff < 0.0000000001\n",
+ " then guess\n",
+ " else go ((guess +. x /. guess) /. 2.)\n",
+ " in go x;;\n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 55,
+ "id": "1c13de25-3a65-4c53-be93-30aeaa43e3f4",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "- : unit = ()\n",
+ "Findlib has been successfully loaded. Additional directives:\n",
+ " #require \"package\";; to load a package\n",
+ " #list;; to list the available packages\n",
+ " #camlp4o;; to load camlp4 (standard syntax)\n",
+ " #camlp4r;; to load camlp4 (revised syntax)\n",
+ " #predicates \"p,q,...\";; to set these predicates\n",
+ " Topfind.reset();; to force that packages will be reloaded\n",
+ " #thread;; to enable threads\n",
+ "\n",
+ "- : unit = ()\n"
+ ]
+ }
+ ],
+ "source": [
+ "#use \"topfind\";;\n",
+ "#require \"qcheck\";;"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 56,
+ "id": "c54a0a4c-a9f0-4ebd-bd59-d7fc331b51ad",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "val abs_diff : float -> float -> float = <fun>\n"
+ ]
+ },
+ "execution_count": 56,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "let abs_diff x y = abs_float (x -. y);;"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 57,
+ "id": "3bc48b8e-6aee-4438-9db0-561c4045ce99",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "- : float = 2.00000000000451061\n"
+ ]
+ },
+ "execution_count": 57,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "newton_sqrt 2. *. newton_sqrt 2."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 58,
+ "id": "f307630e-b1a1-45a1-a42f-6a934f0602dd",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "- : bool = true\n"
+ ]
+ },
+ "execution_count": 58,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "(abs_diff 2. ((newton_sqrt 2.) *. (newton_sqrt 2.))) < 0.01"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 59,
+ "id": "04f59f1f-fbb1-40f3-a8e8-67dc1aa54231",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "(* 16\n",
+ "\n",
+ "NEW IDEA: two accumulators tracking the best answer so far, the functional\n",
+ "version of keeping a running maximum.\n",
+ "\n",
+ "busiest_collatz lo hi returns which n in the range lo..hi takes the most\n",
+ "Collatz steps to reach 1. On a tie, return the smallest such n.\n",
+ "\n",
+ "*)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 103,
+ "id": "2030e995-98d6-4ca4-b450-d50004487746",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "val busiest_collatz : int -> int -> int = <fun>\n"
+ ]
+ },
+ "execution_count": 103,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "let busiest_collatz lo hi = \n",
+ " let rec col_calc n = \n",
+ " if n = 1 then 1 else\n",
+ " if n mod 2 = 0 \n",
+ " then ((col_calc (n / 2))) + 1\n",
+ " else ((col_calc ((3 * n) + 1))) + 1\n",
+ " in \n",
+ " let rec go best_num best_count current_num =\n",
+ " if current_num < lo then best_num\n",
+ " else\n",
+ " let current_count = (col_calc current_num) in\n",
+ " if current_count >= best_count\n",
+ " then go current_num current_count (current_num - 1)\n",
+ " else\n",
+ " go best_num best_count (current_num - 1)\n",
+ " in go 0 0 hi"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 106,
+ "id": "a17b339d-0d3b-455c-8f31-2c6d10251134",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "- : int = 837799\n"
+ ]
+ },
+ "execution_count": 106,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "busiest_collatz 1 1000000"
+ ]
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "OCaml default",
+ "language": "OCaml",
+ "name": "ocaml-jupyter"
+ },
+ "language_info": {
+ "codemirror_mode": "text/x-ocaml",
+ "file_extension": ".ml",
+ "mimetype": "text/x-ocaml",
+ "name": "OCaml",
+ "nbconverter_exporter": null,
+ "pygments_lexer": "OCaml",
+ "version": "4.14.2"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 5
+}
