Question

How do you find the square root of `13`?

Answer 1

Use a Newton Raphson method to find:

`sqrt(13) ~~ 842401/233640 ~~ 3.60555127547`

Explanation:

Since `13` is a prime number, there is no simpler form for its square root. `sqrt(13)` is an irrational number somewhere between `3 = sqrt(9)` and `4 = sqrt(16)`.

Linearly interpolating, a reasonable first approximation would be:

`sqrt(13) ~~ 3.6 = 18/5`

We can get better approximations from our initial one (call it `a_0`) using a Newton Raphson method.

A typical formula used to derive a more accurate approximation for `sqrt(n)` would be:

`a_(i+1) = (a_i^2+n)/(2a_i)`

I prefer to separate `a_i` into numerator `p_i` and denominator `q_i`. So `a_i = p_i/q_i` and we can iterate using the formulae:

`{ (p_(i+1) = p_i^2 + n q_i^2), (q_(i+1) = 2 p_i q_i) :}`

In our example, `n = 13`, `p_0 = 18`, `q_0 = 5` and we find:

`{ (p_1 = p_0^2 + 13 q_0^2 = 324 + 13*25 = 649), (q_1 = 2 p_0 q_0 = 180) :}`

If we stopped here our approximation would be:

`sqrt(13) ~~ 649/180 = 3.60bar(5)`

Let's try one more iteration:

`{ (p_2 = p_1^2 + 13 q_1^2 = 421201 + 13*32400 = 842401), (q_2 = 2 p_1 q_1 = 233640) :}`

Stopping here, we have:

`sqrt(13) ~~ 842401/233640 ~~ 3.60555127547`

Using a calculator:

`sqrt(13) ~~ 3.60555127546398929311`

Answer 2

Find `sqrt(13) ~~ 23382/6485 ~~ 3.60555127` using a generalised continued fraction method.

Explanation:

Look for a generalised continued fraction of the form:

`sqrt(13) = a + b/(2a+b/(2a+b/(2a+...)))`

`color(white)(sqrt(13)) = a + b/(a+sqrt(13))`

Multiply both ends by `(a+sqrt(13))` to find:

`color(red)(cancel(color(black)(a sqrt(13)))) + 13 = a^2 + color(red)(cancel(color(black)(a sqrt(13)))) + b`

Hence:

`b = 13 - a^2`

In order that our generalised continued fraction converges quickly choose a rational approximation `a` slightly smaller than `sqrt(13)`.

Note that `3 = sqrt(9) < sqrt(13) < sqrt(16) = 4` so linearly interpolating we find a good approximation:

`sqrt(13) ~~ 3.6 = 18/5`

Note also that:

`(18/5)^2 = 324/25 < 325/25 = 13`

So let `a=18/5` and `b = 13 - a^2 = 1/25` to get:

`sqrt(13) = 18/5 + (1/25)/(36/5 + (1/25)/(36/5 + (1/25)/(36/5+...)))`

We can truncate this continued fraction to get a rational approximation of any desired accuracy.

For example:

`sqrt(13) ~~ 18/5 + (1/25)/(36/5) = 18/5+1/180 = 649/180 = 3.60bar(5)`

Or:

`sqrt(13) ~~ 18/5 + (1/25)/(36/5 + (1/25)/(36/5)) = 23382/6485 ~~ 3.60555127`