Just for fun:
public static BigInteger sqrt(BigInteger x) {
BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2);
BigInteger div2 = div;
// Loop until we hit the same value twice in a row, or wind
// up alternating.
for(;;) {
BigInteger y = div.add(x.divide(div)).shiftRight(1);
if (y.equals(div) || y.equals(div2))
return y;
div2 = div;
div = y;
}
}
I know of no library solution for your question. You'll have to import an external library solution from somewhere. What I give you below is less complicated than getting an external library.
You can create your own external library solution in a class with two static methods as shown below and add that to your collection of external libraries. The methods don't need to be instance methods and so they are static and, conveniently, you don't have to instance the class to use them. The norm for integer square roots is a floor value (i.e. the largest integer less than or equal to the square root), so you may need only the one static method, the floor method, in the class below for the floor value and can choose to ignore the ceiling (i.e. the smallest integer greater than or equal to the square root) method version. Right now, they are in the default package, but you can add a package statement to put them in whatever package you find convenient.
The methods are dirt simple and the iterations converge to the closest integer answer very, very fast. They throw an IllegalArgumentException if you try to give them a negative argument. You can change the exception to another one, but you must ensure that a negatve argument throws some kind of exception or at least doesn't attempt the computation. Integer square roots of negative numbers don't exist since we are not in the realm of imaginary numbers.
These come from very well known simple iterative integer square root algorithms that have been used in hand computations for centuries. It works by averaging an overestimate and underestimate to converge to a better estimate. This may be repeated until the estimate is as close as is desired.
They are based on y1 = ((x/y0) + y0) / 2 converging to the largest integer, yn, where yn * yn <= x.
This will give you a floor value for a BigInteger square root, y, of x where y * y <= x and (y + 1) * (y + 1) > x.
An adaptation can give you a ceiling value for BigInteger square root, y, of x where y * y >= x and (y - 1) * (y - 1) < x
Both methods have been tested and work. They are here:
import java.math.BigInteger;
public class BigIntSqRoot {
public static BigInteger bigIntSqRootFloor(BigInteger x)
throws IllegalArgumentException {
if (x.compareTo(BigInteger.ZERO) < 0) {
throw new IllegalArgumentException("Negative argument.");
}
// square roots of 0 and 1 are trivial and
// y == 0 will cause a divide-by-zero exception
if (x .equals(BigInteger.ZERO) || x.equals(BigInteger.ONE)) {
return x;
} // end if
BigInteger two = BigInteger.valueOf(2L);
BigInteger y;
// starting with y = x / 2 avoids magnitude issues with x squared
for (y = x.divide(two);
y.compareTo(x.divide(y)) > 0;
y = ((x.divide(y)).add(y)).divide(two));
return y;
} // end bigIntSqRootFloor
public static BigInteger bigIntSqRootCeil(BigInteger x)
throws IllegalArgumentException {
if (x.compareTo(BigInteger.ZERO) < 0) {
throw new IllegalArgumentException("Negative argument.");
}
// square roots of 0 and 1 are trivial and
// y == 0 will cause a divide-by-zero exception
if (x == BigInteger.ZERO || x == BigInteger.ONE) {
return x;
} // end if
BigInteger two = BigInteger.valueOf(2L);
BigInteger y;
// starting with y = x / 2 avoids magnitude issues with x squared
for (y = x.divide(two);
y.compareTo(x.divide(y)) > 0;
y = ((x.divide(y)).add(y)).divide(two));
if (x.compareTo(y.multiply(y)) == 0) {
return y;
} else {
return y.add(BigInteger.ONE);
}
} // end bigIntSqRootCeil
} // end class bigIntSqRoot
Strange that nobody has mentioned it earlier but in java 9 you have sqrt in BigInteger, so you can just use it like that:
BigInteger nine = BigInteger.valueOf(9);
BigInteger three = nine.sqrt();
https://docs.oracle.com/javase/9/docs/api/java/math/BigInteger.html#sqrt--
EDIT-1
Adding that there is another flavour of this function that, in addition to the floored square root, also returns the remainder.
sqrtAndRemainder() BigInteger[] Returns an array of two BigIntegers containing the integer square root s of this and its remainder this - s*s, respectively.
I can't verify the accuracy of them but there are several home grown solutions when googling. The best of them seemed to be this one: http://www.merriampark.com/bigsqrt.htm
Also try the Apache commons Math project (once Apache recovers from its bombardment after the JCP blog post).
As Jigar states, Newton's iteration is both quite simple to understand and to implement. I'll leave it up to others decide whether it is the most efficient algorithm or not for finding the square root of a number.
With recursion it can be done in just about two lines.
private static BigInteger newtonIteration(BigInteger n, BigInteger x0)
{
final BigInteger x1 = n.divide(x0).add(x0).shiftRight(1);
return x0.equals(x1)||x0.equals(x1.subtract(BigInteger.ONE)) ? x0 : newtonIteration(n, x1);
}
Where n is the number we want to find the square root of, and x0 is the number from the previous call, which will always be 1 when initiate the first call from another method. So preferably, you will complement it with something like this as well;
public static BigInteger sqrt(final BigInteger number)
{
if(number.signum() == -1)
throw new ArithmeticException("We can only calculate the square root of positive numbers.");
return newtonIteration(number, BigInteger.ONE);
}
I needed to have the square root for BigIntegers for implementing the quadratic sieve. I used some of the solutions here but the absolutely fastest and best solution so far is from Google Guava's BigInteger library.
Documentation can be found here.
An alternative approach, which is quite light. Speed-wise, Mantono's answer, that uses the Newton method, might be preferable for certain cases.
Here's my approach...
public static BigInteger sqrt(BigInteger n) {
BigInteger a = BigInteger.ONE;
BigInteger b = n.shiftRight(1).add(new BigInteger("2")); // (n >> 1) + 2 (ensure 0 doesn't show up)
while (b.compareTo(a) >= 0) {
BigInteger mid = a.add(b).shiftRight(1); // (a+b) >> 1
if (mid.multiply(mid).compareTo(n) > 0)
b = mid.subtract(BigInteger.ONE);
else
a = mid.add(BigInteger.ONE);
}
return a.subtract(BigInteger.ONE);
}
This is the best (and shortest) working solution I've found
http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/
Here is the code:
public static BigInteger sqrt(BigInteger n) {
BigInteger a = BigInteger.ONE;
BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
while(b.compareTo(a) >= 0) {
BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(BigInteger.ONE);
else a = mid.add(BigInteger.ONE);
}
return a.subtract(BigInteger.ONE);
}
I've tested it and it's working correctly (and seems fast)
BigDecimal BDtwo = new BigDecimal("2");
BigDecimal BDtol = new BigDecimal(".000000001");
private BigDecimal bigIntSQRT(BigDecimal lNew, BigDecimal lOld, BigDecimal n) {
lNew = lOld.add(n.divide(lOld, 9, BigDecimal.ROUND_FLOOR)).divide(BDtwo, 9, BigDecimal.ROUND_FLOOR);
if (lOld.subtract(lNew).abs().compareTo(BDtol) == 1) {
lNew = bigIntSQRT(lNew, lNew, n);
}
return lNew;
}
I was just working on this problem and successfully wrote a recursive square root finder in Java. You can change the BDtol to whatever you want, but this runs fairly quickly and gave me the follow example as a result:
Original number 146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025
SQRT --> 383123885216472214589586756787577295328224028242477055.000000000
Then for confirmation 146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025.000000000000000000
Simplified Jim answer and improved performance.
public class BigIntSqRoot {
private static BigInteger two = BigInteger.valueOf(2L);
public static BigInteger bigIntSqRootFloor(BigInteger x)
throws IllegalArgumentException {
if (checkTrivial(x)) {
return x;
}
if (x.bitLength() < 64) { // Can be cast to long
double sqrt = Math.sqrt(x.longValue());
return BigInteger.valueOf(Math.round(sqrt));
}
// starting with y = x / 2 avoids magnitude issues with x squared
BigInteger y = x.divide(two);
BigInteger value = x.divide(y);
while (y.compareTo(value) > 0) {
y = value.add(y).divide(two);
value = x.divide(y);
}
return y;
}
public static BigInteger bigIntSqRootCeil(BigInteger x)
throws IllegalArgumentException {
BigInteger y = bigIntSqRootFloor(x);
if (x.compareTo(y.multiply(y)) == 0) {
return y;
}
return y.add(BigInteger.ONE);
}
private static boolean checkTrivial(BigInteger x) {
if (x == null) {
throw new NullPointerException("x can't be null");
}
if (x.compareTo(BigInteger.ZERO) < 0) {
throw new IllegalArgumentException("Negative argument.");
}
// square roots of 0 and 1 are trivial and
// y == 0 will cause a divide-by-zero exception
if (x.equals(BigInteger.ZERO) || x.equals(BigInteger.ONE)) {
return true;
} // end if
return false;
}
}
Update (23July2018) : This technique does not apper to work for larger values. Have posted a different technique based on binary-search below.
I was looking into factorization and ended up writing this.
package com.example.so.math;
import java.math.BigInteger;
/**
*
* <p>https://stackguides.com/questions/4407839/how-can-i-find-the-square-root-of-a-java-biginteger</p>
* @author Ravindra
* @since 06August2017
*
*/
public class BigIntegerSquareRoot {
public static void main(String[] args) {
int[] values = {5,11,25,31,36,42,49,64,100,121};
for (int i : values) {
BigInteger result = handleSquareRoot(BigInteger.valueOf(i));
System.out.println(i+":"+result);
}
}
private static BigInteger handleSquareRoot(BigInteger modulus) {
int MAX_LOOP_COUNT = 100; // arbitrary for now.. but needs to be proportional to sqrt(modulus)
BigInteger result = null;
if( modulus.equals(BigInteger.ONE) ) {
result = BigInteger.ONE;
return result;
}
for(int i=2;i<MAX_LOOP_COUNT && i<modulus.intValue();i++) { // base-values can be list of primes...
//System.out.println("i"+i);
BigInteger bigIntegerBaseTemp = BigInteger.valueOf(i);
BigInteger bigIntegerRemainderTemp = bigIntegerBaseTemp.modPow(modulus, modulus);
BigInteger bigIntegerRemainderSubtractedByBase = bigIntegerRemainderTemp.subtract(bigIntegerBaseTemp);
BigInteger bigIntegerRemainderSubtractedByBaseFinal = bigIntegerRemainderSubtractedByBase;
BigInteger resultTemp = null;
if(bigIntegerRemainderSubtractedByBase.signum() == -1 || bigIntegerRemainderSubtractedByBase.signum() == 1) {
bigIntegerRemainderSubtractedByBaseFinal = bigIntegerRemainderSubtractedByBase.add(modulus);
resultTemp = bigIntegerRemainderSubtractedByBaseFinal.gcd(modulus);
} else if(bigIntegerRemainderSubtractedByBase.signum() == 0) {
resultTemp = bigIntegerBaseTemp.gcd(modulus);
}
if( resultTemp.multiply(resultTemp).equals(modulus) ) {
System.out.println("Found square root for modulus :"+modulus);
result = resultTemp;
break;
}
}
return result;
}
}
The approach can be visualized like this :
Hope this helps!
I am only going as far as the integer part of the square root but you can modify this rough algo to go to as much more precision as you want:
public static void main(String args[]) {
BigInteger N = new BigInteger(
"17976931348623159077293051907890247336179769789423065727343008115"
+ "77326758055056206869853794492129829595855013875371640157101398586"
+ "47833778606925583497541085196591615128057575940752635007475935288"
+ "71082364994994077189561705436114947486504671101510156394068052754"
+ "0071584560878577663743040086340742855278549092581");
System.out.println(N.toString(10).length());
String sqrt = "";
BigInteger divisor = BigInteger.ZERO;
BigInteger toDivide = BigInteger.ZERO;
String Nstr = N.toString(10);
if (Nstr.length() % 2 == 1)
Nstr = "0" + Nstr;
for (int digitCount = 0; digitCount < Nstr.length(); digitCount += 2) {
toDivide = toDivide.multiply(BigInteger.TEN).multiply(
BigInteger.TEN);
toDivide = toDivide.add(new BigInteger(Nstr.substring(digitCount,
digitCount + 2)));
String div = divisor.toString(10);
divisor = divisor.add(new BigInteger(
div.substring(div.length() - 1)));
int into = tryMax(divisor, toDivide);
divisor = divisor.multiply(BigInteger.TEN).add(
BigInteger.valueOf(into));
toDivide = toDivide.subtract(divisor.multiply(BigInteger
.valueOf(into)));
sqrt = sqrt + into;
}
System.out.println(String.format("Sqrt(%s) = %s", N, sqrt));
}
private static int tryMax(final BigInteger divisor,
final BigInteger toDivide) {
for (int i = 9; i > 0; i--) {
BigInteger div = divisor.multiply(BigInteger.TEN).add(
BigInteger.valueOf(i));
if (div.multiply(BigInteger.valueOf(i)).compareTo(toDivide) <= 0)
return i;
}
return 0;
}
Here's a solution that does not use BigInteger.multiply or BigInteger.divide:
private static final BigInteger ZERO = BigInteger.ZERO;
private static final BigInteger ONE = BigInteger.ONE;
private static final BigInteger TWO = BigInteger.valueOf(2);
private static final BigInteger THREE = BigInteger.valueOf(3);
/**
* This method computes sqrt(n) in O(n.bitLength()) time,
* and computes it exactly. By "exactly", I mean it returns
* not only the (floor of the) square root s, but also the
* remainder r, such that r >= 0, n = s^2 + r, and
* n < (s + 1)^2.
*
* @param n The argument n, as described above.
*
* @return An array of two values, where the first element
* of the array is s and the second is r, as
* described above.
*
* @throws IllegalArgumentException if n is not nonnegative.
*/
public static BigInteger[] sqrt(BigInteger n) {
if (n == null || n.signum() < 0) {
throw new IllegalArgumentException();
}
int bl = n.bitLength();
if ((bl & 1) != 0) {
++ bl;
}
BigInteger s = ZERO;
BigInteger r = ZERO;
while (bl >= 2) {
s = s.shiftLeft(1);
BigInteger crumb = n.testBit(-- bl)
? (n.testBit(-- bl) ? THREE : TWO)
: (n.testBit(-- bl) ? ONE : ZERO);
r = r.shiftLeft(2).add(crumb);
BigInteger d = s.shiftLeft(1);
if (d.compareTo(r) < 0) {
s = s.add(ONE);
r = r.subtract(d).subtract(ONE);
}
}
assert r.signum() >= 0;
assert n.equals(s.multiply(s).add(r));
assert n.compareTo(s.add(ONE).multiply(s.add(ONE))) < 0;
return new BigInteger[] {s, r};
}
The answer I posted above doesn't work for large numbers (but interestingly so!). As such posting a binary-search approach for determining square root for correctness.
package com.example.so.squareroot;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
/**
* <p>https://stackguides.com/questions/4407839/how-can-i-find-the-square-root-of-a-java-biginteger</p>
* <p> Determine square-root of a number or its closest whole number (binary-search-approach) </p>
* @author Ravindra
* @since 07-July-2018
*
*/
public class BigIntegerSquareRootV2 {
public static void main(String[] args) {
List<BigInteger> listOfSquares = new ArrayList<BigInteger>();
listOfSquares.add(BigInteger.valueOf(5).multiply(BigInteger.valueOf(5)).pow(2));
listOfSquares.add(BigInteger.valueOf(11).multiply(BigInteger.valueOf(11)).pow(2));
listOfSquares.add(BigInteger.valueOf(15485863).multiply(BigInteger.valueOf(10000019)).pow(2));
listOfSquares.add(BigInteger.valueOf(533000401).multiply(BigInteger.valueOf(982451653)).pow(2));
listOfSquares.add(BigInteger.valueOf(11).multiply(BigInteger.valueOf(23)));
listOfSquares.add(BigInteger.valueOf(11).multiply(BigInteger.valueOf(23)).pow(2));
for (BigInteger bigIntegerNumber : listOfSquares) {
BigInteger squareRoot = calculateSquareRoot(bigIntegerNumber);
System.out.println("Result :"+bigIntegerNumber+":"+squareRoot);
}
System.out.println("*********************************************************************");
for (BigInteger bigIntegerNumber : listOfSquares) {
BigInteger squareRoot = determineClosestWholeNumberSquareRoot(bigIntegerNumber);
System.out.println("Result :"+bigIntegerNumber+":"+squareRoot);
}
}
/*
Result :625:25
Result :14641:121
Result :23981286414105556927200571609:154858924231397
Result :274206311533451346298141971207799609:523647125012112853
Result :253:null
Result :64009:253
*/
public static BigInteger calculateSquareRoot(BigInteger number) {
/*
* Can be optimized by passing a bean to store the comparison result and avoid having to re-calculate.
*/
BigInteger squareRootResult = determineClosestWholeNumberSquareRoot(number);
if( squareRootResult.pow(2).equals(number)) {
return squareRootResult;
}
return null;
}
/*
Result :625:25
Result :14641:121
Result :23981286414105556927200571609:154858924231397
Result :274206311533451346298141971207799609:523647125012112853
Result :253:15
Result :64009:253
*/
private static BigInteger determineClosestWholeNumberSquareRoot(BigInteger number) {
BigInteger result = null;
if(number.equals(BigInteger.ONE)) {
return BigInteger.ONE;
} else if( number.equals(BigInteger.valueOf(2)) ) {
return BigInteger.ONE;
} else if( number.equals(BigInteger.valueOf(3)) ) {
return BigInteger.ONE;
} else if( number.equals(BigInteger.valueOf(4)) ) {
return BigInteger.valueOf(2);
}
BigInteger tempBaseLow = BigInteger.valueOf(2);
BigInteger tempBaseHigh = number.shiftRight(1); // divide by 2
int loopCount = 11;
while(true) {
if( tempBaseHigh.subtract(tempBaseLow).compareTo(BigInteger.valueOf(loopCount)) == -1 ) { // for lower numbers use for-loop
//System.out.println("Breaking out of while-loop.."); // uncomment-for-debugging
break;
}
BigInteger tempBaseMid = tempBaseHigh.subtract(tempBaseLow).shiftRight(1).add(tempBaseLow); // effectively mid = [(high-low)/2]+low
BigInteger tempBaseMidSquared = tempBaseMid.pow(2);
int comparisonResultTemp = tempBaseMidSquared.compareTo(number);
if(comparisonResultTemp == -1) { // move mid towards higher number
tempBaseLow = tempBaseMid;
} else if( comparisonResultTemp == 0 ) { // number is a square ! return the same !
return tempBaseMid;
} else { // move mid towards lower number
tempBaseHigh = tempBaseMid;
}
}
BigInteger tempBasePrevious = tempBaseLow;
BigInteger tempBaseCurrent = tempBaseLow;
for(int i=0;i<(loopCount+1);i++) {
BigInteger tempBaseSquared = tempBaseCurrent.pow(2);
//System.out.println("Squared :"+tempBaseSquared); // uncomment-for-debugging
int comparisonResultTempTwo = tempBaseSquared.compareTo(number);
if( comparisonResultTempTwo == -1 ) { // move current to previous and increment current...
tempBasePrevious = tempBaseCurrent;
tempBaseCurrent = tempBaseCurrent.add(BigInteger.ONE);
} else if( comparisonResultTempTwo == 0 ) { // is an exact match!
tempBasePrevious = tempBaseCurrent;
break;
} else { // we've identified the point of deviation.. break..
//System.out.println("breaking out of for-loop for square root..."); // uncomment-for-debugging
break;
}
}
result = tempBasePrevious;
//System.out.println("Returning :"+result); // uncomment-for-debugging
return result;
}
}
Regards Ravindra
This is an easy to understand way that may not have the best performance but it gives the solution for a single BigInteger in less than a second.
public static BigInteger sqrt(BigInteger n) {
BigInteger bottom = BigInteger.ONE;
BigInteger top = n;
BigInteger mid;
while(true) {
mid = top.add(bottom).divide(new BigInteger(""+2));
top = mid;
bottom = n.divide(top);
// System.out.println("top: "+top);
// System.out.println("mid: "+mid);
// System.out.println("bottom: "+bottom);
if(top.equals(bottom)) {
return top;
}
}
}
The C# language has similar syntax to Java. I wrote this recursive solution.
static BigInteger fsqrt(BigInteger n)
{
string sn = n.ToString();
return guess(n, BigInteger.Parse(sn.Substring(0, sn.Length >> 1)), 0);
}
static BigInteger guess(BigInteger n, BigInteger g, BigInteger last)
{
if (last >= g - 1 && last <= g + 1) return g;
else return guess(n, (g + (n / g)) >> 1, g);
}
Call this code like this (in Java I guess it would be "System.out.print").
Console.WriteLine(fsqrt(BigInteger.Parse("783648276815623658365871365876257862874628734627835648726")));
And the answer is: 27993718524262253829858552106
Disclaimer: I understand this method doesn't work for numbers less than 10; this is a BigInteger square root method.
This is easily remedied. Change the first method to the following to give the recursive portion some room to breathe.
static BigInteger fsqrt(BigInteger n)
{
if (n > 999)
{
string sn = n.ToString();
return guess(n, BigInteger.Parse(sn.Substring(0, sn.Length >> 1)), 0);
}
else return guess(n, n >> 1, 0);
}
long n = 600851475143L). – Carl G