Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
import square.SquareRoot;
import java.security.SecureRandom;
import java.math.BigInteger;
import java.math.BigDecimal;
public class FindSquareRoot {
public static SquareRoot sr = new SquareRoot();
public static long timeAnswer(BigInteger ans) {
long startTime = System.nanoTime();
for (int i=0;i<500;i++) // Enough reps to smooth out transients
sr.answer(ans);
return System.nanoTime() - startTime;
}
// Square Root function from http://www.java-examples.com/find-square-root-biginteger-example
// Based on Newton's method
public static BigInteger sqrt(BigInteger n) {
int firsttime = 0;
BigDecimal myNumber = new BigDecimal(n);
BigDecimal g = new BigDecimal("1");
BigDecimal my2 = new BigDecimal("2");
BigDecimal epsilon = new BigDecimal("0.0000000001");
BigDecimal nByg = myNumber.divide(g, 9, BigDecimal.ROUND_FLOOR);
//Get the value of n/g
BigDecimal nBygPlusg = nByg.add(g);
//Get the value of n/g + g
BigDecimal nBygPlusgHalf = nBygPlusg.divide(my2, 9, BigDecimal.ROUND_FLOOR);
//Get the value of (n/g + g)/2
BigDecimal saveg = nBygPlusgHalf;
firsttime = 99;
do {
g = nBygPlusgHalf;
nByg = myNumber.divide(g, 9, BigDecimal.ROUND_FLOOR);
nBygPlusg = nByg.add(g);
nBygPlusgHalf = nBygPlusg.divide(my2, 9, BigDecimal.ROUND_FLOOR);
BigDecimal savegdiff = saveg.subtract(nBygPlusgHalf);
if (savegdiff.compareTo(epsilon) == -1) {
firsttime = 0;
}
else {
saveg = nBygPlusgHalf;
}
} while (firsttime > 1);
return saveg.toBigInteger();
}
public static void main(String[] args) {
BigInteger upper = BigInteger.ONE.shiftLeft(SquareRoot.BITS*2+1); // surely larger than the root squared
BigInteger lower = BigInteger.ONE;
// OBS: BigInteger.divide() is much faster if divisor > dividend (quotient = 0)... make this the baseline
long fastDivideThresh = timeAnswer(upper) * 2;
System.out.println("time thresh: " + new Long(fastDivideThresh).toString());
// Bisect space to find root^2...
do {
BigInteger midpt = upper.subtract(lower).shiftRight(1).add(lower);
if (timeAnswer(midpt) <= fastDivideThresh) {
upper = midpt;
}
else {
lower = midpt;
}
} while (upper.subtract(lower).compareTo(BigInteger.ONE) == 1);
System.out.println("Bisection done.");
// Figure out root
BigInteger root = sqrt(upper);
System.out.println("Root calculated.");
// Try answer...
sr.answer(root);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment