class/square_root.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyM3s8BCckQIH+t6/+zuRvEw",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/werowe/HypatiaAcademy/blob/master/class/square_root.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Look at [this spreadsheet](https://docs.google.com/spreadsheets/d/1noN6833hwEyjjVPXy9CP_kOFtGqR0cJzwPIffYEqtZY/edit?usp=sharing)\n"
      ],
      "metadata": {
        "id": "fGKHRD4y7yp-"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Babylonian Method for Finding Square Roots\n",
        "\n",
        "The **Babylonian method** (also known as Heron’s method) is an ancient algorithm for finding square roots that works by iterative approximation. The logic behind this method is based on improving guesses through averaging.\n",
        "\n",
        "### Problem Setup\n",
        "\n",
        "Suppose we want to find the square root of a number $N$.\n",
        "\n",
        "1. **Initial Guess**: Start with an initial guess $x_0$ for the square root of $N$. This guess can be any positive number, though a value close to $N$ makes the method converge faster.\n",
        "\n",
        "### Iterative Step\n",
        "\n",
        "Each iteration of the method refines the guess $x_i$. The update rule is:\n",
        "\n",
        "$$\n",
        "x_{i+1} = \\frac{1}{2} \\left( x_i + \\frac{N}{x_i} \\right)\n",
        "$$\n",
        "\n",
        "Here’s why this works:\n",
        "\n",
        "### Logic of the Method\n",
        "\n",
        "1. **Improving the Guess**:\n",
        "   - At each step, you have a current guess $x_i$. The value $\\frac{N}{x_i}$ represents how much your guess is \"off\" in terms of magnitude. If $x_i$ is an overestimate, $\\frac{N}{x_i}$ will be less than $x_i$, and vice versa if it’s an underestimate.\n",
        "   - By taking the average of $x_i$ and $\\frac{N}{x_i}$, the method balances the overestimate or underestimate and gets closer to the actual square root.\n",
        "\n",
        "2. **Why Averaging Helps**:\n",
        "   - The true square root $\\sqrt{N}$ satisfies $x \\cdot x = N$. If $x_i$ is an overestimate, $\\frac{N}{x_i}$ will be an underestimate of $\\sqrt{N}$, and the reverse is true if $x_i$ is an underestimate.\n",
        "   - Taking the average of $x_i$ and $\\frac{N}{x_i}$ moves your guess closer to $\\sqrt{N}$ because you are \"balancing\" the overestimate and the underestimate.\n",
        "\n",
        "3. **Convergence**:\n",
        "   - Each iteration improves the accuracy of the estimate by reducing the error. Mathematically, it can be shown that the sequence $x_i$ converges to $\\sqrt{N}$.\n",
        "   - As the guesses become closer to the actual square root, the difference between $x_i$ and $\\frac{N}{x_i}$ becomes smaller, so their average approaches the true square root.\n",
        "\n",
        "### Example:\n",
        "\n",
        "Let’s say we want to find $\\sqrt{10}$:\n",
        "\n",
        "1. **Initial guess**: Start with $x_0 = 3$ (a reasonable approximation).\n",
        "\n",
        "2. **Apply the Babylonian update**:\n",
        "\n",
        "$$\n",
        "x_1 = \\frac{1}{2} \\left( 3 + \\frac{10}{3} \\right) = \\frac{1}{2} \\left( 3 + 3.333 \\right) = \\frac{1}{2} \\times 6.333 = 3.166\n",
        "$$\n",
        "\n",
        "This is already a much better approximation.\n",
        "\n",
        "3. **Next iteration**:\n",
        "\n",
        "$$\n",
        "x_2 = \\frac{1}{2} \\left( 3.166 + \\frac{10}{3.166} \\right) = \\frac{1}{2} \\left( 3.166 + 3.159 \\right) = \\frac{1}{2} \\times 6.325 = 3.1625\n",
        "$$\n",
        "\n",
        "Now we’re even closer to $\\sqrt{10} \\approx 3.162$.\n",
        "\n",
        "### Summary of the Logic:\n",
        "\n",
        "- The Babylonian method refines an initial guess by balancing between over- and underestimates.\n",
        "- The averaging technique reduces the error in each iteration.\n",
        "- The method is mathematically guaranteed to converge to the correct square root over time.\n",
        "\n",
        "This iterative process is efficient and rapidly converges to the true square root with just a few steps.\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "noTtqaj8naz5"
      }
    },
    {
      "cell_type": "code",
      "source": [
        " a=2\n",
        " a1 = (a / 2)\n",
        " b1=a/a1\n",
        " a2 = 1/2 * (a1 + b1)\n",
        " b2=a/a2\n",
        " a3= 1/2 * (a2 + b2)\n",
        " b3 = a/a3\n",
        " a4 = 1/2 * (a3 + b3)\n",
        " b4 = a / a4\n",
        " a5 = 1/2 * (a4 + b4)\n",
        " b5 = a / a5\n",
        "\n",
        "\n",
        "b5"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aMD6E7GcQtca",
        "outputId": "5d12c4c2-a3eb-4dc8-e344-411f09d41f4e"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1.4142135623715002"
            ]
          },
          "metadata": {},
          "execution_count": 35
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# watch this converge to the square root of 2, which is 1.414"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CPWKQz62pqHW",
        "outputId": "44448512-0396-4002-e602-b972ee887e40"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1.4142135623715002"
            ]
          },
          "metadata": {},
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        " print(\"a / 2 = a1 =\", a1)\n",
        " print(\"a / a1 = b1 = \", b1)\n",
        " print(\"\\n1/2 * (a1 + b1)= a1 =\", a2)\n",
        " print(\"a / a2 = b2 = \", b2)\n",
        " print(\"\\n1/2 * (a2 + b2) = a3 =\", a3)\n",
        " print(\"a / a3 = b3 =\", b3)\n",
        " print(\"\\n1/2 * (a3 + b3) = a4 = \", a4)\n",
        " print(\"a / a4 = b4 =\", b4)\n",
        " print(\"\\n1/2 * (a4 + b4) = a5 = \", a5)\n",
        " print(\"a / a5 = b5 =\", b5)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YZg2sBqfSo1T",
        "outputId": "0db470c3-bc76-4eae-a766-20e9d4b8c59f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "a / 2 = 1.0\n",
            "a / a1 = 2.0\n",
            "\n",
            "1/2 * (a1 + b1)= 1.0\n",
            "a / a2 = 1.3333333333333333\n",
            "\n",
            "1/2 * (a2 + b2) = 1.4166666666666665\n",
            "a / a3 = 1.411764705882353\n",
            "\n",
            "1/2 * (a3 + b3) = 1.4142156862745097\n",
            "a / a4 = 1.41421143847487\n",
            "\n",
            "1/2 * (a4 + b4) = 1.4142135623746899\n",
            "a / a5 = 1.4142135623715002\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Here is solution:\n",
        "\n",
        "a=2\n",
        "\n",
        "a1 = (a/2)+1\n",
        "b1 = a/a1\n",
        "aminus1 = a1\n",
        "bminus1 = b1\n",
        "\n",
        "\n",
        "while (aminus1-bminus1 > 0):\n",
        "    an = 0.5 * (aminus1 + bminus1)\n",
        "    bn = a / an\n",
        "    aminus1 = an\n",
        "    bminus1 = bn\n",
        "\n",
        "print(an)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NVGP0rXzu8Gm",
        "outputId": "1012498a-7b0f-42ec-8c0a-47587d3edbab"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1.414213562373095\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Google Sheets\n",
        "\n",
        "Here is the solution in [Google Sheets](https://docs.google.com/spreadsheets/d/10-JUANA68Elhf-plU7VceNDtUoQ-9xvU-ImE20m4Ibc/edit?usp=sharing).\n"
      ],
      "metadata": {
        "id": "8Yj2NUrhyHET"
      }
    }
  ]
}