Sunday 21 June 2009

logic behind long division square root algorithm

Let's say we are to find the square root of a. The algorithm is finding one more digit to the square root at each 'go'. That means it is approaching the actual value of the square root from below, or that at each step the approximation is always less than or equal to the actual value of the square root. If x is the approximation found this far, at each go, one wants to find a better approximation x + r so that x + r ≤ √a. From this inequality follows:

x + r


(x + r)2


x2 + 2xr + r2

x2 + (2x + r) r a

(2x + r) r


and the last line corresponds to the step where the user tries different values of r on that empty line so that 2x and something times something is less than the subtraction result.

No comments: