快速整数平方根

Question

有没有更快或更直接的方法来计算整数平方根呢？以下是关于整数平方根的维基百科链接：http://en.wikipedia.org/wiki/Integer_square_root。在C#中，可以这样实现：

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

?

- J Fabian Meier

---

http://blog.wouldbetheologian.com/2011/11/fast-approximate-sqrt-method-in-c.html - qqbenq

如果我正确理解了源代码，它是一种快速近似计算浮点数平方根的方法。我的问题更像是：我能通过避免 long -> double -> long 的转换来节省时间吗？ - J Fabian Meier

转换只会发生一次，而sqrt算法是迭代的。除非这是极其关键的代码，从性能上考虑，否则我不会费心。 - Rik

此外，“整数平方根”通常指的是“实际平方根的整数值”，即向下取整。因此，我建议您考虑使用Math.Floor。在您当前的代码中，Math.Round是多余的，因为它已经在Convert.ToInt64中完成了。 - Rik

FYI - "Convert.ToInt64(Math.Sqrt(value));" 对于26位以下的数字是准确的。但是在67108864以上的数字中，它会出现误差，偏差为+/- 1。 - SunsetQuest

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

如果你想让效率更高一些，可以通过创建一个平行的第二个列表来避免使用字典查找。

- Thomas Jungblut

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

- SunsetQuest

Answer 3

如果你可以接受一个小的绝对误差，那么你将很难超越这个（误差项每个大于9的奇数次幂增加1位）

uint16_t sqrtFav(uint32_t num) {
    if (num == 0) {
        return 0;
    }
    uint8_t bitpos = (32 - __builtin_clzl(num)) >> 1; // Find the (MSB + 1) / 2
    return ((num >> (bitpos + 1)) + (1 << (bitpos - 1))); // offseting bitpos to remove the need to average
}

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

clz可以用你喜欢的任何编译器内置函数替换，这只是我在开发AVR平台时快速达到它的一种方式。

对于带有移位寄存器的微控制器来说，它是恒定时间的，对于没有移位寄存器的微控制器来说，它相对便宜，在8位AVR上对完整的uint32_t范围只需不到200个周期。

你可以按照需要调整变量大小，比如64位、128位等。

- Reroute

---

看起来像是C或C++代码，但这是一个C#的问题。类似的代码也可以用C#编写，使用BitOperations.LeadingZeroCount函数。 - undefined

这是一种相当与编程语言无关的方法，我想在互联网上记录下来，因为我花了太长时间才找到这个方法，例如，32可以变成（sizeof(num) * 4），bitpos可以自动化，完美的模板就出现了。 如果你将num增加1，它也会稍微更准确一些。 - undefined