BigInteger square root help

Question

I was hoping BigInteger(n, (int)0.5) would work but this always returns 1. So could some kind soul tell me how to find square root of a BigInteger please? Out in the cyber space I did find java based functions which implemented sqaure root using BitInteger. All of them are home brewed, would rather have one industry made.

thanks
anand

Answer 1

Hello anand,

In C#, we call System.Math.Sqrt to get a square root of a double value. 

http://msdn.microsoft.com/en-us/library/system.math.sqrt.aspx

We do not have BigInteger in the BCL classes. Are you using any third party library? If you can provide further information on this, I'd like to do more researches and see if I can help on this.

Best regards,
Ji Zhou

MSDN Subscriber Support in Forum

If you have any feedback on our support, please contact [e-mail]

---

Please remember to mark the replies as answers if they help and unmark them if they provide no help.

Answer 2

Use Newton's method (N/g + g)/2.

    private BigInteger SqRtN(BigInteger N)
    {
      BigInteger G = new BigInteger((N.shiftRight((N.bitLength() + 1) / 2)).ToString());
      BigInteger LastG = null;
      do
      {
        LastG = G;
        G = N.divide(G).add(G).shiftRight(1);
      }
      while (!(G.xor(LastG).ToString() == "0"));
      return G;
    }

The following code corrects the comparison error in the above code:

    BigInteger SqRtN(BigInteger N)

    {

      BigInteger G = new BigInteger((N.shiftRight((N.bitLength() + 1) / 2)).ToString());

      BigInteger LastG = null;

      BigInteger One = new BigInteger("1");

      while (true)

      {

        LastG = G;

        G = N.divide(G).add(G).shiftRight(1);

        int i = G.compareTo(LastG);

        if (i == 0) return G;

        if (i < 0)

        {

          if (LastG.subtract(G).compareTo(One) == 0)

            if (G.multiply(G).compareTo(N) < 0 && LastG.multiply(LastG).compareTo(N) > 0) return G;

        }

        else

        {

          if (G.subtract(LastG).compareTo(One) == 0)

            if (LastG.multiply(LastG).compareTo(N) < 0 && G.multiply(G).compareTo(N) > 0) return LastG;

        }

      }

    }

Answer 3

 Well, In C# 2.0 you can do following....

            Int64 i = Int64.MaxValue;
            MessageBox.Show(i.ToString());

            Int64Converter converted = new Int64Converter();
            double d = (double)converted.ConvertTo(i, typeof(double));
            MessageBox.Show(Math.Sqrt(d).ToString());

But you have to Include "vjslib" dll to deal with BigInteger so you can create instance of BigInteger like following 

            string positiveString = "144";

            BigInteger bigIntFromDouble = new BigInteger(positiveString);

but in that there is not much help.

In .Net 4.0 they have introduced new Class BigInterger and ComplexNumber in System.Numbers

---

Tejas Mer

Answer 4

Hi John,

Thanks very much for the neat solution. However ShiftRight and bitLength are not to be found. It says I am missing a directive. I googled and found java has it. Please tell me how can I get this to work on VS 2010 C#?
 "
BigInteger BinaryShift(BigInteger b, int n) {
   return b * BigInteger.Pow(2, n); }
This function is a convenience only, but an
important one when porting code from other               --> From the internet
languages. For example it could replace the
ubiquitous Java functions
 BigInteger shiftLeft(int n)  [this << n]
 BigInteger shiftRight(int n) [this >> n]
"

Also the divide function does not work as it seems to work for you.
I can do BigInteger.divide(dividend, divisor) I cannot do what you do
BigIntger N;
N.divide(divisor) --> The divide function is not seen when I do N.
Niether do I see the xor.

I guess if I include the missing reference then all of them will work

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.ComponentModel;
using System.Globalization;
using System.Numerics;

namespace Test
{
    public class Junk
    {
        static void Main(string[] args)
        {
            BigInteger n = 12341234234234234234;
            SqRtN(n);
        }

        static public BigInteger SqRtN(BigInteger N)
        {
            BigInteger G = new BigInteger((N.shiftRight((N.bitLength() + 1) / 2)
).ToString());
            BigInteger LastG = null;
            do
            {
                LastG = G;
                G = N.divide(G).add(G).shiftRight(1);
            }
            while (!(G.xor(LastG).ToString() == "0"));
            return G;
        }
    }
}

Hi Ji and Tejas, thnanks for advice. Sorry it is my mistake I should have mentioned that I am using 2010. John's solution is more appealing and so let me work with him and get this resovled.
thanks to all

ananda

Answer 5

I'm sorry, I am not an evaluator of experimental software.  There should be instructions for reporting your experiences with the software on the Help menu.  The code I posted references the java.math namespace of vjslib.

Answer 6

There is a built in way, but be warned, it doesn't give the same precision as a BigInteger when performing the square root function:

BigInteger i = BigInteger.Parse("123456123456123234342343234235252535352535325325235456123456");
Complex sqrt = Complex.Sqrt((Complex)i);
Console.WriteLine(sqrt);

---

Coding Light - Illuminated Ideas and Algorithms in Software
Coding Light Wiki • LinkedIn • ForumsBrowser

Answer 7

Thanks to JohnWein I have a fully working code using System.numerics in VS 2010 and C#. For the original code using java.math please refer john's code up in this forum stack. I have tested this with some 10 different big numbers and both produced identical results. This does not work with 15, 35 and I am many other numbers.... John's original algorithm also fails for 15 and 35 ... Tomorrow I will debug this. If anyone has a solution please post

      public static BigInteger SqRtN(BigInteger N)
        {
            /*++
             *  Using Newton Raphson method we calculate the
             *  square root (N/g + g)/2
             */
            BigInteger rootN = N;
            int bitLength = 1; // There is a bug in finding bit length hence we start with 1 not 0
            while (rootN / 2 != 0)
            {
                rootN /= 2;
                bitLength++;
            }
            bitLength = (bitLength + 1) / 2;
            rootN = N >> bitLength;

            BigInteger lastRoot = BigInteger.Zero;
            do
            {
                lastRoot = rootN;
                rootN = (BigInteger.Divide(N, rootN) + rootN) >> 1;
            }
            while (!((rootN ^ lastRoot).ToString() == "0"));
            return rootN;
        } // SqRtN

 

Answer 8

 public static BigInteger SqRtN(BigInteger N)
        {
            /*++
             *  Using Newton Raphson method we calculate the
             *  square root (N/g + g)/2
             */
            BigInteger rootN = N;
            int count = 0;
            int bitLength = 1; // There is a bug in finding bit length hence we start with 1 not 0
            while (rootN / 2 != 0)
            {
                rootN /= 2;
                bitLength++;
            }
            bitLength = (bitLength + 1) / 2;
            rootN = N >> bitLength;

            BigInteger lastRoot = BigInteger.Zero;
            do
            {
                if (lastRoot > rootN)
                {
                    if (count++ > 1000)                   // Work around for the bug where it gets into an infinite loop
                    {
                        return rootN;
                    }
                }
                lastRoot = rootN;
                rootN = (BigInteger.Divide(N, rootN) + rootN) >> 1;
            }
            while (!((rootN ^ lastRoot).ToString() == "0"));
            return rootN;
        } // SqRtN

Answer 9

Henry S. Warren wrote "Hacker's Delight". Two solutions, the hardware algorithm (I am using VB, shouldn't be hard to translate to C...):


 Private Function sqr(ByVal x As BigInteger) As BigInteger
    Dim y As BigInteger = BigInteger.valueOf(0)
    Dim b As BigInteger
    Dim m As BigInteger = BigInteger.valueOf(2).shiftLeft((x.bitLength - 2) Or 1)
    While m.signum > 0
      b = y.or(m)
      y = y.shiftRight(1)
      If x.compareTo(b) >= 0 Then
        x = x.subtract(b)
        y = y.or(m)
      End If
      m = m.shiftRight(2)
    End While
    Return y
  End Function


and Newton's method (x>0):

 Private Function sqr(ByVal x As BigInteger) As BigInteger
    Dim S As Integer = (x.bitLength + 1) >> 1
    Dim g0 As BigInteger = BigInteger.valueOf(1).shiftLeft(S)
    Dim g1 As BigInteger = g0.add(x.shiftRight(S)).shiftRight(1)
    While g1.compareTo(g0) < 0
      g0 = g1
      g1 = g0.add(x.divide(g0)).shiftRight(1)
    End While
    Return g0
  End Function


The divide operation is slow, I am working at it, see:

http://permute.007sites.com/

Regards

Peter