locked
BigInteger square root help RRS feed

  • 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
    Wednesday, December 2, 2009 5:14 AM

Answers

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

            }

          }

        }

    • Marked as answer by ananda vardhana Tuesday, December 8, 2009 4:33 AM
    • Edited by JohnWein Friday, December 11, 2009 9:23 AM
    Wednesday, December 2, 2009 9:24 AM
  •  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

    Wednesday, December 9, 2009 12:06 AM

All replies

  • 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 msdnmg@microsoft.com


    Please remember to mark the replies as answers if they help and unmark them if they provide no help.
    Wednesday, December 2, 2009 7:25 AM
    Moderator
  • 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;

            }

          }

        }

    • Marked as answer by ananda vardhana Tuesday, December 8, 2009 4:33 AM
    • Edited by JohnWein Friday, December 11, 2009 9:23 AM
    Wednesday, December 2, 2009 9:24 AM
  •  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
    Wednesday, December 2, 2009 10:14 AM
  • 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

    Wednesday, December 2, 2009 4:20 PM
  • 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.
    Wednesday, December 2, 2009 4:44 PM
  • 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 WikiLinkedInForumsBrowser
    Wednesday, December 2, 2009 5:04 PM
    Moderator
  • 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

     

    Tuesday, December 8, 2009 4:40 AM
  •  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

    Wednesday, December 9, 2009 12:06 AM
  • 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
    Sunday, January 31, 2010 4:13 PM