計算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; }`