Skip to content

Instantly share code, notes, and snippets.

@JochemKuijpers

JochemKuijpers/BigInteger_sqrt.java

Last active August 16, 2023 09:25
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save JochemKuijpers/cd1ad9ec23d6d90959c549de5892d6cb to your computer and use it in GitHub Desktop.
Save JochemKuijpers/cd1ad9ec23d6d90959c549de5892d6cb to your computer and use it in GitHub Desktop.
Download ZIP
Raw
BigInteger_sqrt.java
BigInteger sqrt(BigInteger n) {
BigInteger a = BigInteger.ONE;
BigInteger b = n.shiftRight(5).add(BigInteger.valueOf(8));
while (b.compareTo(a) >= 0) {
BigInteger mid = a.add(b).shiftRight(1);
if (mid.multiply(mid).compareTo(n) > 0) {
b = mid.subtract(BigInteger.ONE);
} else {
a = mid.add(BigInteger.ONE);
}
}
return a.subtract(BigInteger.ONE);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment