Fast Integer Square Root

Question

Is there any faster or more direct way of computing the integer square root:

http://en.wikipedia.org/wiki/Integer_square_root

in C# as

private long LongSqrt(long value)
{
    return Convert.ToInt64(Math.Sqrt(value));
}

?

Answer 1

If you know the range in advance you can create a lookup index for a squared value and its integer square root.

Here is some simple code:

// populate the lookup cache
var lookup = new Dictionary<long, long>();
for (int i = 0; i < 20000; i++)
{
    lookup[i * i] = i;
}

// build a sorted index
var index = new List<long>(lookup.Keys);
index.Sort();

// search for a sample 27 
var foundIndex = index.BinarySearch(27);
if (foundIndex < 0)
{
    // if there was no direct hit, lookup the smaller value
    // TODO please check for out of bounds that might happen
    Console.WriteLine(lookup[index[~foundIndex - 1]]);
}
else
{
    Console.WriteLine(lookup[foundIndex]);
}

// yields 5

You can get around the dictionary lookup by creating a parallel second list, if you want it to be more efficient.