Create a gist now

Instantly share code, notes, and snippets.

@kgrad5 / Secret
Created Mar 21, 2013

Updated to correct silly mistakes
package square;
import java.math.BigInteger;
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
// The random number is generated with a maximum number of bits located in SquareRoot.BITS. This means the max bytes
// is BITS/8. This number is then squared, so the maximum possible square root is every bit flipped in all
// bytes. We first create the maximum possible square root.
byte[] maxBytes = new byte[SquareRoot.BITS+7/8]; // avoid overflow if BITS is 0 for some reason.
Arrays.fill(maxBytes, (byte) -1);
BigInteger max = new BigInteger(1, maxBytes);
// In order to figure out when we have found the actual root we close the output stream. Then
// if there is an error, we know we have found our square root as something will have been written to
BigInteger root = BigInteger.ZERO;
// Do a brute force search from the max square root down to 0.
for (; max.compareTo(BigInteger.ZERO) > 0; max = max.subtract(BigInteger.ONE)) {
if (System.out.checkError()) {
root = max;
// The square root! We print to err just for confirmation as out is closed.
System.err.println(String.format("The root is %s.", root.toString()));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment