Instantly share code, notes, and snippets.

# hughpyle/SquareR

Last active December 15, 2015 04:50
Show Gist options
• Save hughpyle/d0172eb66b96baa574e9 to your computer and use it in GitHub Desktop.
Solution to BigInteger square root puzzle http://corner.squareup.com/2013/03/puzzle-square-root.html
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* Solution to biginteger square root puzzle http://corner.squareup.com/2013/03/puzzle-square-root.html Uses a timing attack on BigInteger.divide(), which has a very large performance difference depending whether the divisor is larger or smaller than this. Times multiple iterations to try avoid jitter. Not at all optimized for speed :-) */ package square; import java.math.BigInteger; import java.security.SecureRandom; public class SquareRootTest { static boolean CSV = true; /* Output comma-separated values to graph later */ static boolean DEBUG = false; /* Debug the decision tree */ static boolean VERBOSE = false; /* Output the values */ static SquareRoot sqr = new SquareRoot(); static BigInteger n, nUpper, nLower; static BigInteger TWO = BigInteger.valueOf(2L); static long count=0; static double oldML, oldMU, oldSL, oldSU; static double newML, newMU, newSL, newSU; static int FUDGEITER1=1; static int FUDGEITER2=1; static BigInteger sqrt(BigInteger x) { // 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 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; } static long tryroot( BigInteger bi ) { long t = System.nanoTime(); for( int i=0; i

### hughpyle commented Mar 20, 2013

OK, it's not particularly reliable yet. For 1000-digit values I'm hitting the right answer nearly all the time. For 10k-digit values my tests are only 50%, and it takes way longer to run than I'd like. I might spend time on this later, but currently happy with this for a proof of concept.

### hughpyle commented Mar 20, 2013

Updated to stretch if the timing returns zero. More reliable and not necessarily any slower than before.

TIL the slow way: linux 2.4 has no sub-millisecond Java clock, so please use something more modern.

### hughpyle commented Mar 21, 2013

Rev3 checks its convergence path can output comma-separated values for charting. I think this should be very solid. Now to run some tests :)