Calculate square root of a BigInteger (System.Numerics.BigInteger)

Question

.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?

Answer 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.

Answer 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

Answer 3

Ok, first a few speed tests of some variants posted here. (I only considered methods which give exact results and are at least suitable for BigInteger):

+------------------------------+-------+------+------+-------+-------+--------+--------+--------+
| variant - 1000x times        |   2e5 | 2e10 | 2e15 |  2e25 |  2e50 |  2e100 |  2e250 |  2e500 |
+------------------------------+-------+------+------+-------+-------+--------+--------+--------+
| my version                   |  0.03 | 0.04 | 0.04 |  0.76 |  1.44 |   2.23 |   4.84 |  23.05 |
| RedGreenCode (bound opti.)   |  0.56 | 1.20 | 1.80 |  2.21 |  3.71 |   6.10 |  14.53 |  51.48 |
| RedGreenCode (newton method) |  0.80 | 1.21 | 2.12 |  2.79 |  5.23 |   8.09 |  19.90 |  65.36 |
| Nordic Mainframe (CORDIC)    |  2.38 | 5.52 | 9.65 | 19.80 | 46.69 |  90.16 | 262.76 | 637.82 |
| Sunsetquest (without divs)   |  2.37 | 5.48 | 9.11 | 24.50 | 56.83 | 145.52 | 839.08 | 4.62 s |
| Jeremy Kahan (js-port)       | 46.53 | #.## | #.## |  #.## |  #.## |   #.## |   #.## |   #.## |
+------------------------------+-------+------+------+-------+-------+--------+--------+--------+

+------------------------------+--------+--------+--------+---------+---------+--------+--------+
| variant - single             | 2e1000 | 2e2500 | 2e5000 | 2e10000 | 2e25000 |  2e50k | 2e100k |
+------------------------------+--------+--------+--------+---------+---------+--------+--------+
| my version                   |   0.10 |   0.77 |   3.46 |   14.97 |  105.19 | 455.68 | 1,98 s |
| RedGreenCode (bound opti.)   |   0.26 |   1.41 |   6.53 |   25.36 |  182.68 | 777.39 | 3,30 s |
| RedGreenCode (newton method) |   0.33 |   1.73 |   8.08 |   32.07 |  228.50 | 974.40 | 4,15 s |
| Nordic Mainframe (CORDIC)    |   1.83 |   7.73 |  26.86 |   94.55 |  561.03 | 2,25 s | 10.3 s |
| Sunsetquest (without divs)   |  31.84 | 450.80 | 3,48 s |  27.5 s |    #.## |   #.## |   #.## |
| Jeremy Kahan (js-port)       |   #.## |   #.## |   #.## |    #.## |    #.## |   #.## |   #.## |
+------------------------------+--------+--------+--------+---------+---------+--------+--------+

- value example: 2e10 = 20000000000 (result: 141421)
- times in milliseconds or with "s" in seconds
- #.##: need more than 5 minutes (timeout)

Descriptions:

Jeremy Kahan (js-port)

Jeremy's simple algorithm works, but the computational effort increases exponentially very fast due to the simple adding/subtracting... :)

Sunsetquest (without divs)

The approach without dividing is good, but due to the divide and conquer variant the results converges relatively slowly (especially with large numbers)

Nordic Mainframe (CORDIC)

The CORDIC algorithm is already quite powerful, although the bit-by-bit operation of the imuttable BigIntegers generates much overhead.

I have calculated the required bits this way: int b = Convert.ToInt32(Math.Ceiling(BigInteger.Log(x, 2))) / 2 + 1;

RedGreenCode (newton method)

The proven newton method shows that something old does not have to be slow. Especially the fast convergence of large numbers can hardly be topped.

RedGreenCode (bound opti.)

The proposal of Jesan Fafon to save a multiplication has brought a lot here.

my version

First: calculate small numbers at the beginning with Math.Sqrt() and as soon as the accuracy of double is no longer sufficient, then use the newton algorithm. However, I try to pre-calculate as many numbers as possible with Math.Sqrt(), which makes the newton algorithm converge much faster.

Here the source:

static readonly BigInteger FastSqrtSmallNumber = 4503599761588223UL; // as static readonly = reduce compare overhead

static BigInteger SqrtFast(BigInteger value)
{
  if (value <= FastSqrtSmallNumber) // small enough for Math.Sqrt() or negative?
  {
    if (value.Sign < 0) throw new ArgumentException("Negative argument.");
    return (ulong)Math.Sqrt((ulong)value);
  }

  BigInteger root; // now filled with an approximate value
  int byteLen = value.ToByteArray().Length;
  if (byteLen < 128) // small enough for direct double conversion?
  {
    root = (BigInteger)Math.Sqrt((double)value);
  }
  else // large: reduce with bitshifting, then convert to double (and back)
  {
    root = (BigInteger)Math.Sqrt((double)(value >> (byteLen - 127) * 8)) << (byteLen - 127) * 4;
  }

  for (; ; )
  {
    var root2 = value / root + root >> 1;
    if ((root2 == root || root2 == root + 1) && IsSqrt(value, root)) return root;
    root = value / root2 + root2 >> 1;
    if ((root == root2 || root == root2 + 1) && IsSqrt(value, root2)) return root2;
  }
}

static bool IsSqrt(BigInteger value, BigInteger root)
{
  var lowerBound = root * root;

  return value >= lowerBound && value <= lowerBound + (root << 1);
}

full Benchmark-Source:

using System;
using System.Numerics;
using System.Diagnostics;

namespace MathTest
{
  class Program
  {
    static readonly BigInteger FastSqrtSmallNumber = 4503599761588223UL; // as static readonly = reduce compare overhead
    static BigInteger SqrtMax(BigInteger value)
    {
      if (value <= FastSqrtSmallNumber) // small enough for Math.Sqrt() or negative?
      {
        if (value.Sign < 0) throw new ArgumentException("Negative argument.");
        return (ulong)Math.Sqrt((ulong)value);
      }

      BigInteger root; // now filled with an approximate value
      int byteLen = value.ToByteArray().Length;
      if (byteLen < 128) // small enough for direct double conversion?
      {
        root = (BigInteger)Math.Sqrt((double)value);
      }
      else // large: reduce with bitshifting, then convert to double (and back)
      {
        root = (BigInteger)Math.Sqrt((double)(value >> (byteLen - 127) * 8)) << (byteLen - 127) * 4;
      }

      for (; ; )
      {
        var root2 = value / root + root >> 1;
        if ((root2 == root || root2 == root + 1) && IsSqrt(value, root)) return root;
        root = value / root2 + root2 >> 1;
        if ((root == root2 || root == root2 + 1) && IsSqrt(value, root2)) return root2;
      }
    }

    static bool IsSqrt(BigInteger value, BigInteger root)
    {
      var lowerBound = root * root;

      return value >= lowerBound && value <= lowerBound + (root << 1);
    }

    // newton method
    public static BigInteger SqrtRedGreenCode(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 (!isSqrtRedGreenCode(n, root))
        {
          root += n / root;
          root /= 2;
        }

        return root;
      }

      throw new ArithmeticException("NaN");
    }
    private static bool isSqrtRedGreenCode(BigInteger n, BigInteger root)
    {
      BigInteger lowerBound = root * root;
      //BigInteger upperBound = (root + 1) * (root + 1);

      return n >= lowerBound && n <= lowerBound + root + root;
      //return (n >= lowerBound && n < upperBound);
    }

    // without divisions
    public static BigInteger SqrtSunsetquest(BigInteger number)
    {
      if (number < 9)
      {
        if (number == 0)
          return 0;
        if (number < 4)
          return 1;
        else
          return 2;
      }

      BigInteger n = 0, p = 0;
      var high = number >> 1;
      var low = BigInteger.Zero;

      while (high > low + 1)
      {
        n = (high + low) >> 1;
        p = n * n;
        if (number < p)
        {
          high = n;
        }
        else if (number > p)
        {
          low = n;
        }
        else
        {
          break;
        }
      }
      return number == p ? n : low;
    }

    // javascript port
    public static BigInteger SqrtJeremyKahan(BigInteger n)
    {
      var oddNumber = BigInteger.One;
      var result = BigInteger.Zero;
      while (n >= oddNumber)
      {
        n -= oddNumber;
        oddNumber += 2;
        result++;
      }
      return result;
    }

    // CORDIC
    public static BigInteger SqrtNordicMainframe(BigInteger x)
    {
      int b = Convert.ToInt32(Math.Ceiling(BigInteger.Log(x, 2))) / 2 + 1;
      BigInteger r = 0; // r will contain the result
      BigInteger r2 = 0; // here we maintain r squared
      while (b >= 0)
      {
        var sr2 = r2;
        var sr = r;
        // compute (r+(1<<b))**2, we have r**2 already.
        r2 += (r << 1 + b) + (BigInteger.One << b + b);
        r += BigInteger.One << b;
        if (r2 > x)
        {
          r = sr;
          r2 = sr2;
        }
        b--;
      }
      return r;
    }

    static void Main(string[] args)
    {
      var t2 = BigInteger.Parse("2" + new string('0', 10000));

      //var q1 = SqrtRedGreenCode(t2);
      var q2 = SqrtSunsetquest(t2);
      //var q3 = SqrtJeremyKahan(t2);
      //var q4 = SqrtNordicMainframe(t2);
      var q5 = SqrtMax(t2);
      //if (q5 != q1) throw new Exception();
      if (q5 != q2) throw new Exception();
      //if (q5 != q3) throw new Exception();
      //if (q5 != q4) throw new Exception();

      for (int r = 0; r < 5; r++)
      {
        var mess = Stopwatch.StartNew();
        //for (int i = 0; i < 1000; i++)
        {
          //var q = SqrtRedGreenCode(t2);
          var q = SqrtSunsetquest(t2);
          //var q = SqrtJeremyKahan(t2);
          //var q = SqrtNordicMainframe(t2);
          //var q = SqrtMax(t2);
        }
        mess.Stop();
        Console.WriteLine((mess.ElapsedTicks * 1000.0 / Stopwatch.Frequency).ToString("N2") + " ms");
      }
    }
  }
}

Answer 4

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

Answer 5

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

Answer 6

Update: For best performance, use the Newton Plus version.

That one is hundreds of times faster. I am leaving this one for reference, however, as an alternative way.

    // Source: http://mjs5.com/2016/01/20/c-biginteger-square-root-function/  Michael Steiner, Jan 2016
    // Slightly modified to correct error below 6. (thank you M Ktsis D) 
    public static BigInteger SteinerSqrt(BigInteger number)
    {
        if (number < 9)
        {
            if (number == 0)
                return 0;
            if (number < 4)
                return 1;
            else
                return 2;
        }

        BigInteger n = 0, p = 0;
        var high = number >> 1;
        var low = BigInteger.Zero;

        while (high > low + 1)
        {
            n = (high + low) >> 1;
            p = n * n;
            if (number < p)
            {
                high = n;
            }
            else if (number > p)
            {
                low = n;
            }
            else
            {
                break;
            }
        }
        return number == p ? n : low;
    }

Update: Thank you to M Ktsis D for finding a bug in this. It has been corrected with a guard clause.

Answer 7

The two methods below use the babylonian method to calculate the square root of the provided number. The Sqrt method returns BigInteger type and therefore will only provide answer to the last whole number (no decimal points).

The method will use 15 iterations, although after a few tests, I found out that 12-13 iterations are enough for 80+ digit numbers, however I decided to keep it at 15 just in case.

As the Babylonian square root approximation method requires us to pick a number that is half the length of the number that we want to find square root of, the RandomBigIntegerOfLength() method therefore provides that number.

The RandomBigIntegerOfLength() takes an integer length of a number as an argument and provides a randomly generated number of that length. The number is generated using the Next() method from the Random class, the Next() method is called twice in order to avoid the number to have 0 at the beginning (something like 041657180501613764193159871) as it causes the DivideByZeroException. It is important to point out that initially the number is generataed one by one, concatenated, and only then it is converted to BigInteger type from string.

The Sqrt method uses the RandomBigIntegerOfLength method to obtain a random number of half the length of the provided argument "number" and then calculates the square root using the babylonian method with 15 iterations. The number of iterations may be changed to smaller or bigger as you would like. As the babylonian method cannot provide square root of 0, as it requires dividing by 0, in case 0 is provided as an argument it will return 0.

//Copy the two methods
public static BigInteger Sqrt(BigInteger number)
{
    BigInteger _x = RandomBigIntegerOfLength((number.ToString().ToCharArray().Length / 2));
    
    try
    {
        for (int i = 0; i < 15; i++)
        {
            _x = (_x + number / _x) / 2;
        }
        return _x;
    }
    catch (DivideByZeroException)
    {
        return 0;
    }
}

// Copy this method as well
private static BigInteger RandomBigIntegerOfLength(int length)
{
    Random rand = new Random();

    string _randomNumber = "";
    
    _randomNumber = String.Concat(_randomNumber, rand.Next(1, 10));

    for (int i = 0; i < length-1; i++)
    {
        _randomNumber = String.Concat(_randomNumber,rand.Next(10).ToString());
    }
    if (String.IsNullOrEmpty(_randomNumber) == false) return BigInteger.Parse(_randomNumber);
    else return 0;
}

Answer 8

*** World's fastest BigInteger Sqrt for Java/C# !!!!***

Write-Up: https://www.codeproject.com/Articles/5321399/NewtonPlus-A-Fast-Big-Number-Square-Root-Function

Github: https://github.com/SunsetQuest/NewtonPlus-Fast-BigInteger-and-BigFloat-Square-Root

public static BigInteger NewtonPlusSqrt(BigInteger x)
{
    if (x < 144838757784765629)    // 1.448e17 = ~1<<57
    {
        uint vInt = (uint)Math.Sqrt((ulong)x);
        if ((x >= 4503599761588224) && ((ulong)vInt * vInt > (ulong)x))  // 4.5e15 =  ~1<<52
        {
            vInt--;
        }
        return vInt;
    }

    double xAsDub = (double)x;
    if (xAsDub < 8.5e37)   //  long.max*long.max
    {
        ulong vInt = (ulong)Math.Sqrt(xAsDub);
        BigInteger v = (vInt + ((ulong)(x / vInt))) >> 1;
        return (v * v <= x) ? v : v - 1;
    }

    if (xAsDub < 4.3322e127)
    {
        BigInteger v = (BigInteger)Math.Sqrt(xAsDub);
        v = (v + (x / v)) >> 1;
        if (xAsDub > 2e63)
        {
            v = (v + (x / v)) >> 1;
        }
        return (v * v <= x) ? v : v - 1;
    }

    int xLen = (int)x.GetBitLength();
    int wantedPrecision = (xLen + 1) / 2;
    int xLenMod = xLen + (xLen & 1) + 1;

    //////// Do the first Sqrt on hardware ////////
    long tempX = (long)(x >> (xLenMod - 63));
    double tempSqrt1 = Math.Sqrt(tempX);
    ulong valLong = (ulong)BitConverter.DoubleToInt64Bits(tempSqrt1) & 0x1fffffffffffffL;
    if (valLong == 0)
    {
        valLong = 1UL << 53;
    }

    ////////  Classic Newton Iterations ////////
    BigInteger val = ((BigInteger)valLong << 52) + (x >> xLenMod - (3 * 53)) / valLong;
    int size = 106;
    for (; size < 256; size <<= 1)
    {
        val = (val << (size - 1)) + (x >> xLenMod - (3 * size)) / val;
    }

    if (xAsDub > 4e254) // 4e254 = 1<<845.76973610139
    {
        int numOfNewtonSteps = BitOperations.Log2((uint)(wantedPrecision / size)) + 2;

        //////  Apply Starting Size  ////////
        int wantedSize = (wantedPrecision >> numOfNewtonSteps) + 2;
        int needToShiftBy = size - wantedSize;
        val >>= needToShiftBy;
        size = wantedSize;
        do
        {
            ////////  Newton Plus Iterations  ////////
            int shiftX = xLenMod - (3 * size);
            BigInteger valSqrd = (val * val) << (size - 1);
            BigInteger valSU = (x >> shiftX) - valSqrd;
            val = (val << size) + (valSU / val);
            size *= 2;
        } while (size < wantedPrecision);
    }

    /////// There are a few extra digits here, lets save them ///////
    int oversidedBy = size - wantedPrecision;
    BigInteger saveDroppedDigitsBI = val & ((BigInteger.One << oversidedBy) - 1);
    int downby = (oversidedBy < 64) ? (oversidedBy >> 2) + 1 : (oversidedBy - 32);
    ulong saveDroppedDigits = (ulong)(saveDroppedDigitsBI >> downby);


    ////////  Shrink result to wanted Precision  ////////
    val >>= oversidedBy;


    ////////  Detect a round-ups  ////////
    if ((saveDroppedDigits == 0) && (val * val > x))
    {
        val--;
    }

    ////////// Error Detection ////////
    //// I believe the above has no errors but to guarantee the following can be added.
    //// If an error is found, please report it.
    //BigInteger tmp = val * val;
    //if (tmp > x)
    //{
    //    Console.WriteLine($"Missed  , {ToolsForOther.ToBinaryString(saveDroppedDigitsBI, oversidedBy)}, {oversidedBy}, {size}, {wantedPrecision}, {saveDroppedDigitsBI.GetBitLength()}");
    //    if (saveDroppedDigitsBI.GetBitLength() >= 6)
    //        Console.WriteLine($"val^2 ({tmp}) < x({x})  off%:{((double)(tmp)) / (double)x}");
    //    //throw new Exception("Sqrt function had internal error - value too high");
    //}
    //if ((tmp + 2 * val + 1) <= x)
    //{
    //    Console.WriteLine($"(val+1)^2({((val + 1) * (val + 1))}) >= x({x})");
    //    //throw new Exception("Sqrt function had internal error - value too low");
    //}

    return val;
}

Below is a log-based chart. Please note a small difference is a huge difference in performance. All are in C# except GMP (C++/Asm) which was added for comparison. Java's version (ported to C#) has also been added.