Editing Integer square root (section)

==Introductory remark==
Let <math>y</math> and <math>k</math> be non-negative integers.

Algorithms that compute (the [[decimal representation]] of) <math>\sqrt y</math> '''run forever''' on each input <math>y</math> which is not a [[square number|perfect square]].<ref group="note">[[Square root#As decimal expansions|The square roots of the perfect squares (e.g., 0, 1, 4, 9, 16) are integers. In all other cases, the square roots of positive integers are irrational numbers.]]</ref>

Algorithms that compute <math>\lfloor \sqrt y \rfloor</math> '''do not run forever'''. They are nevertheless capable of computing <math>\sqrt y</math> up to any desired accuracy <math>k</math>.

Choose any <math>k</math> and compute <math display="inline">\lfloor \sqrt {y \times 100^k} \rfloor</math>.

'''For example''' (setting <math>y = 2</math>):
<math display="block">\begin{align}
& k = 0: \lfloor \sqrt {2 \times 100^{0}} \rfloor = \lfloor \sqrt {2} \rfloor = 1 \\
& k = 1: \lfloor \sqrt {2 \times 100^{1}} \rfloor = \lfloor \sqrt {200} \rfloor = 14 \\
& k = 2: \lfloor \sqrt {2 \times 100^{2}} \rfloor = \lfloor \sqrt {20000} \rfloor = 141 \\
& k = 3: \lfloor \sqrt {2 \times 100^{3}} \rfloor = \lfloor \sqrt {2000000} \rfloor = 1414 \\
& \vdots \\
& k = 8: \lfloor \sqrt {2 \times 100^{8}} \rfloor = \lfloor \sqrt {20000000000000000} \rfloor = 141421356 \\
& \vdots \\
\end{align}</math>

Compare the results with <math>\sqrt {2} = 1.41421356237309504880168872420969807856967187537694 ...</math>

It appears that the multiplication of the input by <math>100^k</math> gives an accuracy of {{mvar|k}} decimal digits.<ref group="note">It is no surprise that the repeated multiplication by {{math|100}} is a feature in {{harvtxt|Jarvis|2006}}</ref>

To compute the (entire) decimal representation of <math>\sqrt y</math>, one can execute <math>\operatorname{isqrt}(y)</math> an infinite number of times, increasing <math>y</math> by a factor <math>100</math> at each pass.

Assume that in the next program (<math>\operatorname{sqrtForever}</math>) the procedure <math>\operatorname{isqrt}(y)</math> is already defined and &mdash; for the sake of the argument &mdash; that all variables can hold integers of unlimited magnitude.

Then <math>\operatorname{sqrtForever}(y)</math> will print the entire decimal representation of <math>\sqrt y</math>.<ref group="note">The fractional part of square roots of perfect squares is rendered as {{math|000...}}.</ref>

<syntaxhighlight lang="c" line="1">
// Print sqrt(y), without halting
void sqrtForever(unsigned int y)
{
	unsigned int result = isqrt(y);
	printf("%d.", result);	// print result, followed by a decimal point

	while (true)	// repeat forever ...
	{
		y = y * 100;	// theoretical example: overflow is ignored
		result = isqrt(y);
		printf("%d", result % 10);	// print last digit of result
	}
}
</syntaxhighlight>

The conclusion is that algorithms which compute {{code|isqrt()}} are computationally equivalent to [[Methods of computing square roots|algorithms which compute {{code|sqrt()}}]].