c# - 平方根的快速逼近？

Question

我正在编写的程序中进行一些计算。虽然我的问题可能看起来晦涩难懂，也许可以避免，但事实并非如此，即使是，我现在也不想避免它:-D

问题是我有一个巨大的数字(数千位，有时可能数百万)，我需要找到一个近似的 SQRT。我正在使用 System.Numerics.BigInteger，我需要近似值小于或等于实际 SQRT。例如，如果提供的数字是 100，我会喜欢 7、8、9 或 10，但不会喜欢 11。

当前代码:

public static BigInteger IntegerSqrt(BigInteger n)
{
    var oldValue = new BigInteger(0);
    BigInteger newValue = n;

    while (BigInteger.Abs(newValue - oldValue) >= 1)
    {
        oldValue = newValue;
        newValue = (oldValue + (n / oldValue)) / 2;
    }

    return newValue;
}

虽然这给了我正确的答案(据我所知)，但它在尝试获得精确答案时速度太慢了。

如果获得立方根或其他类似的东西会更快，我会很高兴。另外，是的，我知道快速找到平方根可以让你赚很多钱，但这并不是我真正想要做的，我只是想要一个快速的近似值......

如果你能给我任何帮助，那就太好了!

编辑 - Gabe

这是我正在使用的更新后的 IntegerSqrt 函数，它似乎并没有更快地工作。

public static BigInteger IntegerSqrt(BigInteger n)
{
    var oldValue = n.RoughSqrt();
    BigInteger newValue = n;
    while (BigInteger.Abs(newValue - oldValue) >= 1)
    {
        oldValue = newValue;
        newValue = (oldValue + (n / oldValue)) / 2;
    }

    return newValue;
}

编辑 2这是你想的吗？ - 我在一个大样本(50k 位)上运行了 30 分钟，它循环了大约 100 次而没有完成。我觉得好像我错过了什么......

public static BigInteger IntegerSqrt(BigInteger n)
{
    var oldValue = new BigInteger(0);
    BigInteger newValue = n.RoughSqrt();
    int i = 0;
    while (BigInteger.Abs(newValue - oldValue) >= 1)
    {
        oldValue = newValue;
        newValue = (oldValue + (n / oldValue)) / 2;
        i++;
    }
    return newValue;
}

Answer 1

使用我的回答 here为了计算Log₂(N)，我准备了一个测试用例。

尽管您的代码更接近于实数平方根，但我的测试显示当输入数字越来越大时速度提高了数百万倍。

我认为您必须在更精确的结果与数千/数百万倍的加速之间做出选择，

Random rnd = new Random();
var bi = new BigInteger(Enumerable.Range(0, 1000).Select(x => (byte)rnd.Next(16))
                                                 .ToArray());


var sqrt1 = bi.Sqrt().ToString();
var sqrt2 = IntegerSqrt(bi).ToString();

var t1 = Measure(10 * 200000, () => bi.Sqrt());
var t2 = Measure(10, () => IntegerSqrt(bi));

BigInteger.Sqrt的扩展方法

public static class BigIntegerExtensions
{
    static int[] PreCalc = new int[] { 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
    static int Log2(this BigInteger bi)
    {
        byte[] buf = bi.ToByteArray();
        int len = buf.Length;
        return len * 8 - PreCalc[buf[len - 1]] - 1;
    }

    public static BigInteger Sqrt(this BigInteger bi)
    {
        return new BigInteger(1) << (Log2(bi) / 2);
    }
}

测速代码

long Measure(int n,Action action)
{
    action(); 
    var sw = Stopwatch.StartNew();
    for (int i = 0; i < n; i++)
    {
        action();
    }
    return sw.ElapsedMilliseconds;
}

结果:

在我的电脑上，两个代码都在 8 秒内产生结果，但我发布的代码运行 10*200000 次，相比之下你的代码只运行了 10 次。 (是的，难以置信，对于 8000 位数，差异是 200,000 倍)

与 16000 位数相比，差异增加到 1,000,000 倍...