Calculate square root of a BigInteger (System.Nume

问题:

.NET 4.0 provides the System.Numerics.BigInteger type for arbitrarily-large integers. I need to compute the square root (or a reasonable approximation -- e.g., integer square root) of a BigInteger. So that I don't have to reimplement the wheel, does anyone have a nice extension method for this?

回答1:

Check if BigInteger is not a perfect square has code to compute the integer square root of a Java BigInteger. Here it is translated into C#, as an extension method.

    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);
    }

Informal testing indicates that this is about 75X slower than Math.Sqrt, for small integers. The VS profiler points to the multiplications in isSqrt as the hotspots.

回答2:

I am not sure if Newton's Method is the best way to compute bignum square roots, because it involves divisions which are slow for bignums. You can use a CORDIC method, which uses only addition and shifts (shown here for unsigned ints)

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;
}

There's a similar method which uses only addition and shifts, called 'Dijkstras Square Root', explained for example here:

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

回答3:

The simplest feasible way to compute a square root to an arbitrary precision is probably Newton's method.

回答4:

You can convert this to the language and variable types of your choice. Here is a truncated squareroot in JavaScript (freshest for me) that takes advantage of 1+3+5...+nth odd number = n^2. All the variables are integers, and it only adds and subtracts.

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

回答5:

Short answer: (but beware, see below for more details)

Math.Pow(Math.E, BigInteger.Log(pd) / 2)

Where pd represents the BigInteger on which you want to perform the square root operation.

Long answer and explanation:

Another way to understanding this problem is understanding how square roots and logs work.

If you have the equation 5^x = 25, to solve for x we must use logs. In this example, I will use natural logs (logs in other bases are also possible, but the natural log is the easy way).

5^x = 25

Rewriting, we have:

x(ln 5) = ln 25

To isolate x, we have

x = ln 25 / ln 5

We see this results in x = 2. But since we already know x (x = 2, in 5^2), let's change what we don't know and write a new equation and solve for the new unknown. Let x be the result of the square root operation. This gives us

2 = ln 25 / ln x

Rewriting to isolate x, we have

ln x = (ln 25) / 2

To remove the log, we now use a special identity of the natural log and the special number e. Specifically, e^ln x = x. Rewriting the equation now gives us

e^ln x = e^((ln 25) / 2)

Simplifying the left hand side, we have

x = e^((ln 25) / 2)

where x will be the square root of 25. You could also extend this idea to any root or number, and the general formula for the yth root of x becomes e^((ln x) / y).

Now to apply this specifically to C#, BigIntegers, and this question specifically, we simply implement the formula. WARNING: Although the math is correct, there are finite limits. This method will only get you in the neighborhood, with a large unknown range (depending on how big of a number you operate on). Perhaps this is why Microsoft did not implement such a method.

// A sample generated public key modulus
var pd = BigInteger.Parse("101017638707436133903821306341466727228541580658758890103412581005475252078199915929932968020619524277851873319243238741901729414629681623307196829081607677830881341203504364437688722228526603134919021724454060938836833023076773093013126674662502999661052433082827512395099052335602854935571690613335742455727");
var sqrt = Math.Pow(Math.E, BigInteger.Log(pd) / 2);

Console.WriteLine(sqrt);

NOTE: The BigInteger.Log() method returns a double, so two concerns arise. 1) The number is imprecise, and 2) there is an upper limit on what Log() can handle for BigInteger inputs. To examine the upper limit, we can look at normal form for the natural log, that is ln x = y. In other words, e^y = x. Since double is the return type of BigInteger.Log(), it would stand to reason the largest BigInteger would then be e raised to double.MaxValue. On my computer, that would e^1.79769313486232E+308. The imprecision is unhandled. Anyone want to implement BigDecimal and update BigInteger.Log()?

Consumer beware, but it will get you in the neighborhood, and squaring the result does produce a number similar to the original input, up to so many digits and not as precise as RedGreenCode's answer. Happy (square) rooting! ;)