BigInteger square root help

# BigInteger square root help

• Wednesday, December 02, 2009 5:14 AM

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

### All Replies

• Wednesday, December 02, 2009 7:25 AM
Moderator

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

Please remember to mark the replies as answers if they help and unmark them if they provide no help.
• Wednesday, December 02, 2009 9:24 AM

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

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;

}

}

}

• Wednesday, December 02, 2009 10:14 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 02, 2009 4:20 PM

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;
}
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 02, 2009 4:44 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 02, 2009 5:04 PM
Moderator

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

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

• Marked As Answer by Tuesday, December 08, 2009 4:40 AM
• Unmarked As Answer by Wednesday, December 09, 2009 12:03 AM
•
• Wednesday, December 09, 2009 12:06 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

• Marked As Answer by Wednesday, December 09, 2009 1:02 AM
•
• Sunday, January 31, 2010 4:13 PM

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