Instantly share code, notes, and snippets.

# dscherba/FindSquareRoot.javaSecret Created Mar 23, 2013

 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); } }
to join this conversation on GitHub. Already have an account? Sign in to comment