我正在编写的程序中进行一些计算。虽然我的问题可能看起来晦涩难懂,也许可以避免,但事实并非如此,即使是,我现在也不想避免它:-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;
}
最佳答案
使用我的回答 here为了计算Log2(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
倍...
关于c# - 平方根的快速逼近?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20977218/