计算BigInteger的平方根（System.Numerics.BigInteger）

Question

.NET 4.0为任意大整数提供了System.Numerics.BigInteger类型。我需要计算BigInteger的平方根（或合理的近似值 - 例如整数平方根）。所以我不必重新实现轮子，有没有人有一个很好的扩展方法呢？

Answer 1

最简单可行的方法来计算平方根为任意精度大概是Newton's method.

Answer 2

我不知道，如果牛顿的方法是计算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<<b))**2, we have r**2 already. 
     r2+=(uint)((r<<(1+b))+(1<<(b+b)));  
     r+=(uint)(1<<b); 
     if (r2>x) 
     { 
      r=sr; 
      r2=sr2; 
     } 
     b--; 
    } 
    return r; 
} 

有只使用加法和移位，称为“Dijkstras平方根”类似的方法，例如在这里解释说：

• http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf

Answer 3

Check if BigInteger is not a perfect 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中的乘法作为热点。

Answer 4

简短的回答：（但要注意，看到下面有详细介绍）

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^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输入处理什么上限。要检查上限，我们可以查看自然日志的正常形式，即ln x = y。换句话说，e^y = x。由于double是BigInteger.Log()的返回类型，因此最大的BigInteger将会是e增加到double.MaxValue。在我的电脑上，那将是e^1.79769313486232E+308。不精确性未被处理。任何人想要执行BigDecimal并更新BigInteger.Log()？

消费者当心，但它会让你在附近，并且平方结果的确会产生一个类似于原始输入的数字，达到如此多的数字，而不是像RedGreenCode的答案那样精确。快乐（方形）生根！ ;）

Answer 5

您可以将其转换为您选择的语言和变量类型。这里是JavaScript中截断的squareroot（对我来说是最新鲜的），它利用了1 + 3 + 5 ... +第n个奇数= n^2。所有的变量都是整数，只是加减。

var truncSqrt=function(n){ 
var oddNumber=1; 
var result=0; 
while (n>=oddNumber) { 
    n-=oddNumber; 
    oddNumber+=2; 
    result++; } 
return result; }`