ocaml-programming

exercises_p2.ipynb (6952B)

---

 {
  "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
 }