Editing Integer square root (section)

==Basic algorithms==
The '''integer square root''' of a [[non-negative integer]] <math>y</math> can be defined as
<math display="block">\lfloor \sqrt y \rfloor = x : x^2 \leq y <(x+1)^2, x \in \mathbb{N}</math>

For example, <math>\operatorname{isqrt}(27) = \lfloor \sqrt{27} \rfloor = 5</math> because <math>6^2 > 27 \text{ and } 5^2 \ngtr 27</math>.

===Algorithm using linear search===
The following C programs are straightforward implementations.

{{flex columns
|1=
<syntaxhighlight lang="c">
// Integer square root
// (using linear search, ascending)
unsigned int isqrt(unsigned int y)
{
	// initial underestimate, L <= isqrt(y)
	unsigned int L = 0;

	while ((L + 1) * (L + 1) <= y)
		L = L + 1;

	return L;
}
</syntaxhighlight>
|2=
<syntaxhighlight lang="c">
// Integer square root
// (using linear search, descending)
unsigned int isqrt(unsigned int y)
{
	// initial overestimate, isqrt(y) <= R
	unsigned int R = y;

	while (R * R > y)
		R = R - 1;

	return R;
}
</syntaxhighlight>
}}

===Linear search using addition===
In the program above (linear search, ascending) one can replace multiplication by addition, using the equivalence
<math display="block">(L+1)^2 = L^2 + 2L + 1 = L^2 + 1 + \sum_{i=1}^L 2.</math>

<syntaxhighlight lang="c" line="1">
// Integer square root
// (linear search, ascending) using addition
unsigned int isqrt(unsigned int y)
{
	unsigned int L = 0;
	unsigned int a = 1;
	unsigned int d = 3;

	while (a <= y)
	{
		a = a + d;	// (a + 1) ^ 2
		d = d + 2;
		L = L + 1;
	}

	return L;
}
</syntaxhighlight>

===Algorithm using binary search===
{{Disputed-section|date=May 2025}}
[[Binary search algorithm#Linear search|Linear search]] sequentially checks every value until it hits the smallest <math>x</math> where <math>x^2 > y</math>.

A speed-up is achieved by using [[Binary search algorithm#Procedure for finding the leftmost element|binary search]] instead. The following C-program is an implementation. 

<syntaxhighlight lang="c" line="1">
// Integer square root (using binary search)
unsigned int isqrt(unsigned int y)
{
	unsigned int L = 0;
	unsigned int M;
	unsigned int R = y + 1;

    while (L != R - 1)
    {
        M = (L + R) / 2;

		if (M * M <= y)
			L = M;
		else
			R = M;
	}

    return L;
}
</syntaxhighlight>

'''Numerical example'''

For example, if one computes <math>\operatorname{isqrt}(2000000)</math> using binary search, one obtains the <math>[L,R]</math> sequence
<math display="block">\begin{align}
& [0,2000001] \rightarrow [0,1000000] \rightarrow [0,500000] \rightarrow [0,250000] \rightarrow [0,125000] \rightarrow [0,62500] \rightarrow [0,31250] \rightarrow [0,15625] \\
& \rightarrow [0,7812] \rightarrow [0,3906] \rightarrow [0,1953] \rightarrow [976,1953] \rightarrow [976,1464] \rightarrow [1220,1464] \rightarrow [1342,1464] \rightarrow [1403,1464] \\
& \rightarrow [1403,1433] \rightarrow [1403,1418] \rightarrow [1410,1418] \rightarrow [1414,1418] \rightarrow [1414,1416] \rightarrow [1414,1415]
\end{align}</math>

This computation takes 21 iteration steps, whereas linear search (ascending, starting from <math>0</math>) needs {{val|1414}} steps.