Быстрый Целочисленный Квадратный Корень

Question

Есть ли более быстрый или более прямой способ вычисления целочисленного квадратного корня:

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

в C# как

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

?

Answer 1

Если вы заранее знаете диапазон, вы можете создать индекс поиска для квадрата и целочисленного квадратного корня.

Вот простой код:

// 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

Вы можете обойти поиск по словарю, создав параллельный второй список, если хотите, чтобы он был более эффективным.

Answer 2

(С опозданием на несколько лет, но, возможно, это поможет кому-то еще. Однако я потратил некоторое время на эту тему .)

Самый быстрый приблизительный квадратный корень (как и тот, что указан в списке)...

      // ApproxSqrt - Result can be +/- 1
static long ApproxSqrt(long x)
{
    if (x < 0)
        throw new ArgumentOutOfRangeException("Negitive values are not supported.");

    return (long)Math.Sqrt(x);
}

Если вы хотите что-то, что было бы с точностью до всех 64 бит...

      // Fast Square Root for Longs / Int64 - Ryan Scott White 2023 - MIT License
static long Sqrt(long x)
{
    if (x < 0)
        throw new ArgumentOutOfRangeException("Negitive values are not supported.");

    long vInt = (long)Math.Sqrt(x);
    if (vInt * vInt > x)
        vInt--;
    return vInt;
}

Для ulong/UInt64...

      // Fast Square Root for Unsigned Longs - Ryan Scott White 2023 - MIT License
static ulong Sqrt(ulong x)
{
    ulong vInt = (ulong)Math.Sqrt(x);
    ulong prod = vInt * vInt;
    if (prod > x || prod == 0)
        vInt--;
    return vInt;
}