计算BigInteger的平方根（System.Numerics.BigInteger）
.NET 4.0为任意大整数提供System.Numerics.BigInteger类型。 我需要计算BigInteger平方根（或合理的近似值 – 例如，整数平方根）。 所以我没有必要重新实现轮子，有没有人有一个很好的扩展方法呢？
检查BigInteger是不是一个完美的square有代码来计算Java BigInteger的整数平方根。 这里它被翻译成C＃，作为扩展方法。
public static BigInteger Sqrt(this BigInteger n) { if (n == 0) return 0; if (n > 0) { int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2))); BigInteger root = BigInteger.One << (bitLength / 2); while (!isSqrt(n, root)) { root += n / root; root /= 2; } return root; } throw new ArithmeticException("NaN"); } private static Boolean isSqrt(BigInteger n, BigInteger root) { BigInteger lowerBound = root*root; BigInteger upperBound = (root + 1)*(root + 1); return (n >= lowerBound && n < upperBound); }
非正式测试表明，对于小整数，这比Math.Sqrt慢约75倍。 VS剖析器指向isSqrt中的乘法作为热点。
我不确定Newton’s Method是否是计算bignum平方根的最佳方法，因为它涉及对bignum来说缓慢的划分。 您可以使用CORDIC方法，该方法仅使用加法和移位（此处显示为无符号整数）
static uint isqrt(uint x) { int b=15; // this is the next bit we try uint r=0; // r will contain the result uint r2=0; // here we maintain r squared while(b>=0) { uint sr2=r2; uint sr=r; // compute (r+(1<x) { r=sr; r2=sr2; } b--; } return r; }
有一种类似的方法只使用加法和移位，称为’Dijkstras Square Root’，例如这里解释：
将平方根计算为任意精度的最简单可行方法可能是牛顿方法。
您可以将其转换为您选择的语言和变量类型。 这是JavaScript中的截断的squareroot（对我来说最新鲜），它利用了1 + 3 + 5 … + nth odd number = n ^ 2。 所有变量都是整数，它只是加法和减法。
var truncSqrt=function(n){ var oddNumber=1; var result=0; while (n>=oddNumber) { n-=oddNumber; oddNumber+=2; result++; } return result; }`
简短回答:(但要注意，请参阅下面的详细信息）
Math.Pow(Math.E, BigInteger.Log(pd) / 2)
其中pd表示要在其上执行平方根操作的BigInteger 。
很长的答案和解释：
理解这个问题的另一种方法是了解平方根和日志的工作原理。
如果你有等式5^x = 25 ，要解决x我们必须使用日志。 在这个例子中，我将使用自然日志（其他基础中的日志也是可能的，但自然日志是简单的方法）。
5^x = 25
重写，我们有：
x(ln 5) = ln 25
为了隔离x，我们有
x = ln 25 / ln 5
我们在x = 2看到这个结果。 但是既然我们已经知道x（x = 2，在5 ^ 2中），让我们改变我们不知道的东西并编写一个新的等式并求解新的未知数。 设x是平方根运算的结果。 这给了我们
2 = ln 25 / ln x
重写以隔离x，我们有
ln x = (ln 25) / 2
要删除日志，我们现在使用自然日志的特殊标识和特殊编号e 。 具体来说， e^ln x = x 。 重写方程现在给了我们
e^ln x = e^((ln 25) / 2)
简化左手边，我们有
x = e^((ln 25) / 2)
其中x将是25的平方根。您也可以将此想法扩展到任何根或数字，并且x的第y个根的通用公式变为e^((ln x) / y) 。
现在专门将这个应用于C＃，BigIntegers和这个问题，我们只需实现公式。 警告：虽然数学是正确的，但有一些限制。 这种方法只能让您进入附近，具有很大的未知范围（取决于您操作的数字的大小）。 也许这就是为什么微软没有实现这样的方法。
// A sample generated public key modulus var pd = BigInteger.Parse("101017638707436133903821306341466727228541580658758890103412581005475252078199915929932968020619524277851873319243238741901729414629681623307196829081607677830881341203504364437688722228526603134919021724454060938836833023076773093013126674662502999661052433082827512395099052335602854935571690613335742455727"); var sqrt = Math.Pow(Math.E, BigInteger.Log(pd) / 2); Console.WriteLine(sqrt);
注意： BigInteger.Log()方法返回一个double，因此出现两个问题。 1）数字不精确，2） Log()可以处理BigInteger输入的上限。 为了检查上限，我们可以查看自然对数的正规forms，即ln x = y 。 换句话说， e^y = x 。 由于double是BigInteger.Log()的返回类型，因此可以将最大的BigInteger提升为double.MaxValue 。 在我的电脑上，那将是e^1.79769313486232E+308 。 不精确是不妥当的。 有人想实现BigDecimal并更新BigInteger.Log()吗？
消费者要小心，但它会让你进入邻居，并且平方结果会产生一个类似于原始输入的数字，最多可达到这么多位数，而不像RedGreenCode的答案那么精确。 快乐（正方形）生根！ ;）