快速整数平方根

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;
}

Answer 3

如果你能忍受一个小的绝对误差，你将很难克服这个（9 以上每 2 的奇数次幂，误差项就会增加 1 位）

uint16_t sqrtFav(uint32_t num) {
    if (num == 0) {
        return 0;
    }
    uint8_t bitpos = 15 - ((__builtin_clzl(num) + 1) >> 1);
    uint32_t approx = ((num >> bitpos) + (1 << bitpos)) >> 1; 
    return approx;
}

这是我自己在尝试优化运动控制加速曲线时达成的创作，其中相对误差比绝对误差更重要。

clz 可以替换为您喜欢的内置编译器，这只是在我正在开发的 AVR 平台上实现它的快速方法。

在带有桶形移位器的微控制器上具有恒定的时间，并且在缺少桶形移位器的微控制器上相对便宜，在 8 位 AVR 上的整个 uint32_t 范围低于 200 个周期，

您可以缩放变量大小为 64、128 位等，