Question

How do you approximate `sqrt3`?

Answer 1

Use a variant of Newton Raphson to construct a sequence of rational approximations and stop when you have enough significant digits.

Explanation:

In the case of finding an approximation for `sqrt(n)`, the Newton Raphson method boils down to choosing a reasonable first approximation `a_0`, then iterating using the formula:

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

If you apply this using decimals then you quickly run into choices as to where to truncate your decimals, etc.

If you apply it using fractions, then you frequently find yourself multiplying up the numerator and denominator to simplify the fractions.

Alternatively, notice that if `a_i = p_i / q_i` where `p_i` and `q_i` are integers, then:

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

`=(p_i^2+n q_i^2)/(2p_iq_i)`

So use:

`p_(i+1) = p_i^2+n q_i^2`

`q_(i+1) = 2p_iq_i`

It can happen (in early iterations) that `p_(i+1)` and `q_(i+1)` end up with a common factor, in which case it's best to divide both by the common factor.

For `sqrt(3)`, let `n=3`, `p_0 = 2`, `q_0 = 1`.

Then:

`(p_0, q_0) = (2, 1)`
`(p_1, q_1) = (7, 4)`
`(p_2, q_2) = (97, 56)`
`(p_3, q_3) = (18817, 10864)`

Then `p_3/q_3 = 18817/10864 ~= 1.7320508`