Ancient ritual recovered, part 2

How does that method work? Say you have a number x which can be written as \sum_{i=0}^n 100^ix_i, where the x_i are positive integers less than 100, that is, they are pairs of digits in x. Start with x_n and find the largest digit a_n whose square is no greater than x_n, that is, x_n=a_n^2+r_n.

Now consider 100x_n+x_{n-1}, that is, the number formed from the first two pairs of digits in x. Its square root is a little more than (or equal to) 10a_n+a_{n-1} where a_{n-1} is the largest digit which, appended to a_n, gives you a number whose square is no greater than 100x_n+x_{n-1}. That is, 100x_n+x_{n-1} = (10a_n+a_{n-1})^2+r_{n-1}. But (10a_n+a_{n-1})^2 = 100a_n^2+(20a_n+a_{n-1})a_{n-1} and so 100r_n+x_{n-1} = (20a_n+a_{n-1})a_{n-1}+r_{n-1}. The number on the left is just the remainder from the previous step with the next pair of digits from x appended, and the first term on the right is twice the result from the previous step with a new digit appended, multiplied by that new digit. Their difference gives our new remainder, r_{n-1}.

Iterate that process and you get each digit a_n of the square root.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s