Square roots of positive integers
If #n# is a positive integer, then it is often best to start by breaking it down into prime factors.
If #n# is a perfect square, then every prime factor of #n# will occur an even number of times in its prime factorisation.
To break #n# down into prime factors, try each of the primes in ascending order to see if they are a factor. If you find one which divides evenly into #n#, then do so, then repeat with the remaining factor.
For example:
#1936 = 2 * 968 = 2 * 2 * 484 = 2 * 2 * 2 * 242#
#= 2 * 2 * 2 * 2 * 121 = 2 * 2 * 2 * 2 * 11 * 11#
In this example, the prime factors #2# and #11# each occur an even number of times, so #1936# is a perfect square:
#1936 = 2 * 2 * 11 * 2 * 2 * 11 = 44^2#
so #sqrt(1936) = 44#
If at least one prime factor occurs an even number of times, then even if #n# is not a perfect square, its square root can be simplified.
For example:
#252 = 2 * 2 * 3 * 3 * 7 = 6^2 * 7#
so #sqrt(252) = 6sqrt(7)#.
If #n# has no square factors, then it cannot be simplified.
For example, #30 = 2 * 3 * 5#, so #sqrt(30)# cannot be simplified.
Approximating the root of a positive integer
A standard method for constructing approximations for #sqrt(n)# is to start with an approximation #a_0#, then apply an iteration step repeatedly:
#a_(i+1) = (a_i^2 + n) / (2a_i)#
This is a form of Newton Raphson method.
Personally, I rather like working with rational approximations in the form #p/q# but avoiding fraction arithmetic as much as possible. To do this, I choose integers #p_0# and #q_0# so #p_0/q_0 = a_0#, then iterate using the formulas:
#p_(i+1) = p_i^2+nq_i^2#
#q_(i+1) = 2 p_i q_i#
The resulting #p_(i+1)/q_(i+1)# is identical to the result of putting #a_i = p_i/q_i# in the previous formula then sorting out the fraction arithmetic.
If the resulting #p_(i+1)# and #q_(i+1)# have a common factor, then divide both by that before the next iteration.
This tends to happen if you start with a crude initial approximation.
For example, approximating #sqrt(30)#, I would normally start with #p_0 = 11# and #q_0 = 2#, recognising that #30# is about halfway between #25 = 5^2# and #36 = 6^2#, so #11/2# is a reasonable first approximation.
However, if you use #p_0 = 5# and #q_0 = 1#, then this is what happens:
#p_1 = p_0^2 + n q_0^2 = 5^2 + 30*1^2 = 25 + 30 = 55#
#q_1 = 2 * p_0 * q_0 = 2 * 5 * 1 = 10#
So #p_1# and #q_1# have a common factor #5#, and we would divide both of them by #5#, resulting in #p_(1a) = 11#, #q_(1a) = 2#
So you get the picture, the next iteration goes like this:
#p_2 = p_(1a)^2 + n q_(1a)^2 = 11^2 + 30 * 2^2 = 121 + 120 = 241#
#q_2 = 2 * p_(1a) * q_(1a) = 2 * 11 * 2 = 44#
So the next approximation for #sqrt(30)# is #241 / 44 = 5.47dot(7)dot(2)#
Actually #sqrt(30) ~~ 5.477445575#
