{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "869c62b9",
   "metadata": {},
   "source": [
    "# Iteration: solving what you can't solve directly\n",
    "### Chapter 7 · iteration & convergence · **[PREDICT-FIRST]**\n",
    "\n",
    "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/MeiraDavidson/math_module1/blob/main/notebooks/notebook_7_1_iteration_sqrt2.ipynb)\n",
    "\n",
    "**What you'll see:** three machines fed their own output, over and over. One crawls to\n",
    "zero, one runs off to infinity — and one performs a small miracle: no matter where\n",
    "you start, it always finds $\\sqrt2$. By the end you'll have built a square-root\n",
    "algorithm with four lines of code.\n",
    "\n",
    "**Predict-first:** when you see 🔮, guess before you run."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "32e0afb4",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def iterate(machine, start, steps):\n",
    "    \"\"\"Feed a machine its own output, `steps` times, recording the path.\"\"\"\n",
    "    x = start\n",
    "    path = [x]\n",
    "    for _ in range(steps):\n",
    "        x = machine(x)\n",
    "        path.append(x)\n",
    "    return path"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a4b2e9b",
   "metadata": {},
   "source": [
    "## 1. Two simple machines: one settles, one escapes\n",
    "\n",
    "Iterating **\"halve it\"** from 32, and **\"add 3\"** from 0. Watch the long-run\n",
    "behavior — that's the whole point of iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ee59c73a",
   "metadata": {},
   "outputs": [],
   "source": [
    "halve = lambda x: x / 2\n",
    "add3  = lambda x: x + 3\n",
    "\n",
    "print(\"halve, from 32:\", [round(v, 4) for v in iterate(halve, 32, 8)])\n",
    "print(\"add 3, from 0: \", iterate(add3, 0, 8))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c41862d9",
   "metadata": {},
   "source": [
    "Halving **crawls toward 0** and never quite arrives — we call $0$ an *attractor*.\n",
    "Adding 3 just **runs off** forever. Same idea (feed the output back in), opposite\n",
    "fates — decided entirely by the machine."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acd4bcac",
   "metadata": {},
   "source": [
    "## 2. The √2-finder — a real miracle\n",
    "\n",
    "Here is the machine: take the average of $x$ and $\\tfrac{2}{x}$,\n",
    "$$f(x) = \\tfrac12\\left(x + \\tfrac{2}{x}\\right).$$\n",
    "\n",
    "🔮 **Predict first:** type *any* positive starting number you like into `start`\n",
    "below — 1, or 100, or 0.01, your choice. **Predict where it ends up before you run\n",
    "it.** Will different starts land in different places?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f379810",
   "metadata": {},
   "outputs": [],
   "source": [
    "sqrt2_finder = lambda x: 0.5 * (x + 2/x)\n",
    "\n",
    "start = 100.0       # <-- change me to ANY positive number you like\n",
    "path = iterate(sqrt2_finder, start, 6)\n",
    "\n",
    "print(f\"starting from {start}:\")\n",
    "for i, v in enumerate(path):\n",
    "    print(f\"  step {i}:  {v:.12f}\")\n",
    "print(f\"\\n  √2 (the truth): {np.sqrt(2):.12f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83c6855c",
   "metadata": {},
   "source": [
    "However wild your starting number, the machine **homes in on $\\sqrt2$ in just a\n",
    "handful of steps.** Let's watch it converge:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "86ec824c",
   "metadata": {},
   "outputs": [],
   "source": [
    "for s in [1, 5, 50, 0.1]:\n",
    "    path = iterate(sqrt2_finder, s, 6)\n",
    "    plt.plot(range(len(path)), path, \"o-\", label=f\"start = {s}\")\n",
    "plt.axhline(np.sqrt(2), color=\"#E8833A\", ls=\"--\", label=\"√2\")\n",
    "plt.ylim(0, 6); plt.xlabel(\"step\"); plt.ylabel(\"value\")\n",
    "plt.title(\"Every start lands on √2\"); plt.legend(); plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9044beb",
   "metadata": {},
   "source": [
    "## 3. You just built a square-root algorithm\n",
    "\n",
    "Swap the `2` for any number `N` and the same machine finds $\\sqrt N$. Try it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0b3cb645",
   "metadata": {},
   "outputs": [],
   "source": [
    "def root_finder(N):\n",
    "    machine = lambda x: 0.5 * (x + N/x)\n",
    "    return iterate(machine, 1.0, 8)[-1]\n",
    "\n",
    "for N in [9, 2, 1000, 7]:\n",
    "    print(f\"my machine says √{N} = {root_finder(N):.10f}   (numpy: {np.sqrt(N):.10f})\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb0e1042",
   "metadata": {},
   "source": [
    "## What just happened\n",
    "\n",
    "> **Iteration is how you *solve* things you can't solve directly.** You can't write\n",
    "> $\\sqrt2$ as a fraction — but you can write a simple machine whose repeated\n",
    "> application *converges* to it, as close as you like.\n",
    "\n",
    "Typing *any* start and always landing on $\\sqrt2$ is an experiment, not a fact — it\n",
    "had to be played with. And this is no toy: it's a 2000-year-old method, the ancestor\n",
    "of **Newton's method** (calculus) and **gradient descent** — the algorithm that\n",
    "trains every neural network. The training of every AI you've ever used is one\n",
    "machine, iterated. You just ran the seed of it."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}