Square Root Of java.math.BigInteger
j1mb0jay
at all of the java.math.BigInteger class, why is this?
I have tried to write a simple trial and error Square Root function that
works with BigIntegers. It does not return decimal values and instead
returns null if the number is decimal, or rounds the numbers depending.
The code is below, i am currently trying to re-implement my prime checker
using BigIntegers and require this method, it seems to find the square
root of several thousand digit numbers in just over a second which i
think is pretty good, please can i have some thoughts on how to improve
the code.
Regards j1mb0jay.
--------------------Some Code-------------------------------------
/**
* A number is square free if it is divisible by no perfect
square (except 1).
*
* @param testSubject
* @return - true if the "testSubject" is a square free number.
*/
public static boolean isSquareFree(double testSubject)
{
double answer;
for(int i = 1; i < testSubject; i++)
{
answer = Math.sqrt(testSubject / (double)i);
if(answer < 1)
return false;
if(answer % 1.0 == 0)
return false;
}
return true;
}
bugbear
> I was very surprised to see that java did not have a square root method
> at all of the java.math.BigInteger class, why is this?
Probably because the result isn't a BigInteger
>
> I have tried to write a simple trial and error Square Root function that
> works with BigIntegers. It does not return decimal values and instead
> returns null if the number is decimal, or rounds the numbers depending.
>
> The code is below, i am currently trying to re-implement my prime checker
> using BigIntegers and require this method, it seems to find the square
> root of several thousand digit numbers in just over a second which i
> think is pretty good, please can i have some thoughts on how to improve
> the code.
Look up "numerical analysis". It's what you're doing,
albeit unknowingly.
BugBear
j1mb0jay
Why would the result of square rooting an BigInteger not be a BigInteger
does that not depend on the number you are square rooting, what is the
square root of 2^132874985327329875329 is that not a BigInteger itself ???
I will look up numerical analysis and see if i missed anything out.
Regards j1mb0jay
j1mb0jay
-------------Square Root Code --------------------
package math;
import java.math.BigInteger;
public class SquareRoot
{
public static BigInteger squareRoot(BigInteger testSubject,
boolean round)
{
int digitsInTestSubject = testSubject.toString().length();
double sPoint = (double)digitsInTestSubject / 2.0;
BigInteger startPoint = BigInteger.valueOf(Math.round
(sPoint));
BigInteger lastGuess = null;
BigInteger guess = null;
BigInteger lower= null;
BigInteger upper = null;
if(digitsInTestSubject < 3)
{
lastGuess = BigInteger.valueOf(0L);
lower = lastGuess;
guess = BigInteger.valueOf(5L);
upper = BigInteger.valueOf(10L);
}
else
{
startPoint = startPoint.subtract
(BigInteger.valueOf(1L));
startPoint = pow(BigInteger.valueOf
(10L),startPoint);
lastGuess = startPoint;
lower = lastGuess;
guess = startPoint.multiply(BigInteger.valueOf
(5L));
upper= startPoint.multiply(BigInteger.valueOf
(10L));
}
int guesses = 0;
while(true)
{
guesses++;
BigInteger ans = guess.pow(2);
if(ans.compareTo(testSubject) == 0)
{
break;
}
if(lastGuess.compareTo(guess) == 0)
{
if(round)
{
if(guess.compareTo(testSubject)
== 1)
{
guess = guess.subtract
(BigInteger.valueOf(1));
}
else
{
guess = guess.add
(BigInteger.valueOf(1));
}
}
else
{
guess = null;
}
break;
}
if(ans.compareTo(testSubject) == 1)
{
BigInteger tmp;
if(guess.compareTo(lastGuess) == 1)
{
upper = guess;
tmp = upper.subtract(lower);
tmp = tmp.divide
(BigInteger.valueOf(2L));
tmp = lower.add(tmp);
}
else
{
upper = guess;
tmp = upper.subtract
( upper.subtract(lower).divide(BigInteger.valueOf(2L) ));
}
lastGuess = guess;
guess = tmp;
}
else
{
BigInteger tmp;
if(guess.compareTo(lastGuess) == 1)
{
lower = guess;
tmp = upper.subtract(lower);
tmp = tmp.divide
(BigInteger.valueOf(2L));
tmp = upper.subtract(tmp);
}
else
{
lower = guess;
tmp = lower.add( upper.subtract
(lower).divide(BigInteger.valueOf(2L) ));
}
lastGuess = guess;
guess = tmp;
}
}
return guess;
}
public static BigInteger pow(BigInteger testSubject, BigInteger
pow)
{
BigInteger index = BigInteger.valueOf(1L);
BigInteger retVal = BigInteger.valueOf(10L);
while(index.compareTo(pow) != 0)
{
retVal = retVal.multiply(testSubject);
index = index.add(BigInteger.valueOf(1L));
}
return retVal;
}
}
Lew
> Why would the result of square rooting an BigInteger not be a BigInteger
> does that not depend on the number you are square rooting, what is the
> square root of 2^132874985327329875329 is that not a BigInteger itself ???
What is the square root of 2?
What should be the square root of BigInteger.valueOf( 2 )?
--
Lew
Larry A Barowski
"j1mb0jay" <j1mb...@uni.ac.uk> wrote in message
news:spbdg5x...@news.aber.ac.uk...
>I was very surprised to see that java did not have a square root method
> at all of the java.math.BigInteger class, why is this?
>
> I have tried to write a simple trial and error Square Root function that
> works with BigIntegers. It does not return decimal values and instead
> returns null if the number is decimal, or rounds the numbers depending.
Find the approximate square root using the first few significant
bits and the magnitude, then use Newton's method starting there.
But if all you need is a working implementation, I'm sure you
can find several with a web search.
Eric Sosman
>
> Why would the result of square rooting an BigInteger not be a BigInteger
Your mission, should you choose to accept it, is to find
a value for `root' that keeps the `assert' in this fragment
from firing:
BigInteger square = new BigInteger("-1000");
BigInteger root = /* supply your candidate value here */ ;
assert root.multiply(root).equals(square);
As usual, if you or any of your team are killed or captured,
the Secretary will declare the whole enterprise irrational
and imaginary.
--
Eric Sosman
eso...@ieee-dot-org.invalid
j1mb0jay
Whats the first few significant bits of a number that is made up of
several thousand if not a few million bits. I sure i could find a few on
the Internet, but would like to try and build my own. I already have a an
implementation that works, just would like to try and make it a little
more efficient.
Regards j1mb0jay
j1mb0jay
If the number is less than (2^64)-1 then i wouldn't use a BigInteger
Object to calculate the square root. I would just use a long.
But in the case of my program it would return null as i am only
interested if the number has a perfect square not an accurate decimal
answer. Although their is an option to return 1 as that is the correct
rounded answer.
Square root of 2 is 1.414213562. which rounds to 1.
Regards j1mb0jay
j1mb0jay
A square number is a number multiplied by itself. When you multiply two
identical numbers you always get a positive number !!! - When we are not
in the matix (the real world)
But if you are going all imaginary on me then maybe the answer might be
31.622776602i - rather complex !!!!
Although you did use the Object.equals() rather than the BI.compareTo()
which makes me wonder !!
Regards j1mb0jay
Tom Anderson
> I was very surprised to see that java did not have a square root method
> at all of the java.math.BigInteger class, why is this?
People don't often do roots on integers. Roots tend to be a continuous
maths thing.
> I have tried to write a simple trial and error Square Root function that
> works with BigIntegers. It does not return decimal values and instead
> returns null if the number is decimal, or rounds the numbers depending.
You could look and see if anyone's made a bigint maths library for java
that does square roots. There's been plenty of work on this kind of thing
- look up "integer square root".
The standard approach is to use an iterative process based on Newton's
method to find roots. You can use 1 for the initial guess, or speed things
up by using 1 << ((x.bitLength()) / 2).
Although this guy's figured out something faster, with no multiplies:
http://lists.apple.com/archives/Java-dev/2004/Dec/msg00302.html
> The code is below, i am currently trying to re-implement my prime
> checker using BigIntegers and require this method, it seems to find the
> square root of several thousand digit numbers in just over a second
> which i think is pretty good, please can i have some thoughts on how to
> improve the code.
>
> --------------------Some Code-------------------------------------
>
> /**
> * A number is square free if it is divisible by no perfect
> square (except 1).
> *
> * @param testSubject
> * @return - true if the "testSubject" is a square free number.
> */
> public static boolean isSquareFree(double testSubject)
> {
> double answer;
> for(int i = 1; i < testSubject; i++)
> {
> answer = Math.sqrt(testSubject / (double)i);
> if(answer < 1)
> return false;
> if(answer % 1.0 == 0)
> return false;
> }
> return true;
> }
>
Okay, firstly, this isn't a square root algorithm. Is this the right code?
Secondly, you're using doubles to represent integers. Stop that. A double
is effectively a 53-bit integer with a scale field. It's got less useful
bits than a long. This code *will* be incorrect for large enough numbers.
And god alone knows how modulus of floating-point numbers works (if he's
read the IEEE 754 spec, that is).
tom
--
I need a proper outlet for my tendency towards analytical thought. --
Geneva Melzack
j1mb0jay
No this was not the correct code, i did re-post the correct code, had the
wrong code on the clipboard !!, i will have a look for some pre built
packages but really did want my own method for this.
j1mb0jay
Patricia Shanahan
I strongly agree with Larry's recommendation. However, some aspects will
be easier if you work with BigDecimal in the actual Newton's method, and
only round when you have enough digits to be confident of the answer.
Alternatively, in the late stages Newton's method will get you down to a
small candidate range, and you can just check each number in that range
for being the square root.
Suppose your number has a million bits, and the first four are 1011,
equivalent to decimal 11. There are 999,996 bits we are going to ignore
in the initial approximation step. The square root of 2^999,996 is
2^499998 so the approximate answer is three, the approximate square root
of 1011, times 2^499998.
Now suppose your input as 1001 bits, and still has 1011 as the first
four. The answer will be the square root of 2^1000 times the square root
of 10110. Or you can take the first five bits if the number of bits is
odd, the first four if even.
Patricia
Patricia Shanahan
Here's an alternative approach to getting the initial approximation.
First convert to BigDecimal. Use movePointLeft by an even number of
digits, 2*n, to get a BigDecimal in the double precision range. Use
Math.sqrt to get the square root of the double. Use movePointRight by n
digits to get your initial approximation. Proceed with Newton's method
starting from that approximation.
In effect, this does several iterations of Newton's method on an
approximation to the number you want using double, which tends to be
very fast due to hardware support.
Patricia
Tom Anderson
ALGEBRAIC!
http://youtube.com/watch?v=LNVYWJOEy9A
But seriously, i kind of took it as read that j1mb0 was talking about
integer square root, int(floor(sqrt(x))), which is not an uncommon thing
to need when doing various bits of discrete maths.
tom
--
[Philosophy] is kind of like being driven behind the sofa by Dr Who -
scary, but still entertaining. -- itchyfidget
john
Disclaimer: My familiarity with BigInteger is mostly looking at the
API just now and I have no meaningful knowledge of the detailed
representation of a double in Java other than a vague belief that
about half the bits are just an integer representing the leading
digits and about half are just an integer representing an exponent.
Newtons method is pretty hard to beat, I think the person who
recommended it was giving the right suggestion. If you aren't familiar
with it here: To get the square root of b you start with a beginning
guess x_0 and then take successive guesses by using
x_(n+1) = (x_n / 2) + (b / (2 * x_n)). Given that both of these are
rounded you should probably do
x_(n+1) = ( x_n + b/x_n ) / 2
A lot of newtons method time is narrowing in on a good first guess so
even though even a first guess of x_0 = 1 will work, here are some
better first guesses. They probably don't need to be too
sophisticated:
To get a first guess for b just take anything which takes about half
as many bits to represent as b does. It looks like you can do this by
using bitlength to count the bits, then start with a biginteger which
is 0 and set the bit at position bitlength/2 and that gives you an x_0
that is decent and will hone in fairly quickly.
Here is probably a not very good idea which does give you a high
quality first guess, but I doubt it is worth your while:
If you want a better first guess x_0, then let L be the bitlength of b
and let M = (L/2)*2. The point of M is that it makes L even, which
will be useful as we will need M/2 to be an integer. Say you want
about the first 16 bits to be correct, then you could start by
dividing b by 2^N where N = M - 32. This value c = b/(2^N) is now a
big integer which only has 32 or 33 bits. Then cast c to a double and
take its square root to get sqrt(c). Now truncate the result, cast it
to a string, create a BigInteger out of that string and multiply by
the BigInteger 2^(M/2-16). That is your first guess x_0 and its first
16 or so decimal places should already be correct. Wew! That sounds
like a pain! Probably better to just go with the easier first guess.
Compute 2^N and 2^(M/2-16) in the above by starting with BigInteger
zero and setting the appropriate bit to 1 (i.e. the bit in position N
to get 2^N and in position M/2-16 to get 2^(M/2-16) ). Just use
hexidecimal (or binary if you want) literals for 2^16 (0x10000) and
2^32 (0x100000000). In case you want to know, what we did here was
scale b down so it would fit into a double, took the square root of
the double, truncated it so the result was an integer. Constructed a
BigInteger out of it and multiplied by a scaling factor to correct for
the effect of scaling b down.
Some math footnotes:
There is an algorithm which looks strangely like long division for
calculating a square root one decimal place at a time, however newtons
method is probably much faster.
Since we are using a BigInteger we are actually rounding the result at
each application of newtons method. That is not really unusual since
we always round even when taking the square root of a float or double,
we just round further down in the decimal representation for these.
However in this case we really care about that last digit or two near
where we are rounding so one might wonder whether newtons method might
get caught near but not at the right answer due to the effects of
rounding. For this particular problem when b has an integer square
root you can actually write out a proof that this does not happen.
Eric Sosman
> [...]
> But if you are going all imaginary on me then maybe the answer might be
> 31.622776602i - rather complex !!!!
Exactly: An irrational and imaginary value, not something
a BigInteger can represent.
Note that if you're willing to live with approximations
to irrationals (and with NaN for imaginaries), you can get a
pretty good square root with the tools already available:
BigInteger big = ...;
double approximateRoot = Math.sqrt(big.doubleValue());
I say "pretty good" because if the value of `big' is greater
than Double.MAX_VALUE, `big.doubleValue()' will produce
Double.POSITIVE_INFINITY and the square root calculation
will be doomed before it starts. So for `big' values of more
than about 1025 bits you'll need to roll your own, probably
using Newton-Raphson and getting an initial estimate by just
right-shifting `big' by half its bit count.
john
Well, looks like while I was writing you got several much slicker
versions of what I was suggesting. I shouldn't have bothered. :) A
couple of notes though:
While large primes are reasonably common, very very large perfect
squares are much rarer. If you pick a number at random with n digits
then your odds of it being a perfect square are about 1 out of 2*10^(n/
2), so for a hundred digit number that is
1/200000000000000000000000000000000000000000000000000. For a 50 digit
number they are more reasonable, a mere
1/20000000000000000000000000. :) Also if you want to quickly eliminate
a number as nonsquare you might just check and see whether it ends
with 2,3,7 or 9, in which case it isn't square. Given how very rare
they are there should be a faster way to eliminate "many" numbers as
nonsquare quickly and then just run your algorithm for the rest, but I
can't think of a better one offhand.
-John
john
Woops, make that "ends in 2,3,7 or 8. Perfect squares can end in 9
(e.g. 3^2).
-John
Eric Sosman
> On Wed, 21 May 2008, Eric Sosman wrote:
>
>> j1mb0jay wrote:
>>
>>> Why would the result of square rooting an BigInteger not be a BigInteger
>>
>> Your mission, should you choose to accept it, is to find
>> a value for `root' that keeps the `assert' in this fragment
>> from firing:
>>
>> BigInteger square = new BigInteger("-1000");
>> BigInteger root = /* supply your candidate value here */ ;
>> assert root.multiply(root).equals(square);
>>
>> As usual, if you or any of your team are killed or captured, the
>> Secretary will declare the whole enterprise irrational and imaginary.
>
> ALGEBRAIC!
>
> http://youtube.com/watch?v=LNVYWJOEy9A
>
> But seriously, i kind of took it as read that j1mb0 was talking about
> integer square root, int(floor(sqrt(x))), which is not an uncommon thing
> to need when doing various bits of discrete maths.
Probably, but what he actually asked was "Why would the result
of square rooting an [sic] BigInteger not be a BigInteger," so ...
For floor(sqrt(x)) I know of two methods. One is to use
the Newton-Raphson iteration everyone is taught in school
nowadays, just truncating the divisions as needed. The other
is to use the extend-from-the-leading-digits pencil-and-paper
method that everyone *used* to be taught a generation or so
ago. In the range of hardware-supported integers I've found
N-R to be faster, but for BigInteger where divisions can be
very costly the old-hat way might be superior. (As it was
formerly taught it required division, too, but that's because
it used decimal representation; in binary you can use compare
and subtract, at the cost of about lg(10) times as many steps.)
john
I meant they can't end in 2,3, 7 or 8. Perfect squares can end in 9.
Eric Sosman
> [...] Also if you want to quickly eliminate
> a number as nonsquare you might just check and see whether it ends
> with 2,3,7 or 9, in which case it isn't square. Given how very rare
> they are there should be a faster way to eliminate "many" numbers as
> nonsquare quickly and then just run your algorithm for the rest, but I
> can't think of a better one offhand.
(Corrections in follow-ups noted.) It's expensive to
compute the low-order decimal digit of a BigInteger, but
your suggestion can be adapted to power-of-two bases for
a quicker triage. For example, in base 16 all perfect
squares end in 0, 1, 4, or 9, so inspecting the low-order
four bits suffices to screen out 75% of the candidates
quite cheaply. In base 256 all perfect squares end in
just forty-four different values, so inspecting the low-
order byte culls 83% of the herd. A precomputed array
of 256 booleans might be a worthwhile investment if a lot
of square-testing is to be done:
private static final boolean[] possibleSquare
= new boolean[256];
static {
for (int r = 0; r < 256; ++r)
possibleSquare[ (r * r) & 0xFF ] = true;
}
In base two it's even simpler: All perfect squares
end in either 0 or 1. Just inspect the low-order bit,
and if it's something other than 0 or 1 the number is
not a square. ;-)
Tom Anderson
> There is an algorithm which looks strangely like long division for
> calculating a square root one decimal place at a time, however newtons
> method is probably much faster.
I wonder. The thing about Newton is that it involves doing arithmetic on
whole BigIntegers, which means creating and destroying a bunch of
potentially quite large objects. This is not a good way to get high
performance.
The long division algorithm, on the other hand, works through the number,
dealing with it in small chunks, and generating digits as it goes. That
means you can create one array to hold your computed digits (which would
probably be in base 256, ie bytes), work through, and then construct one
single BigInteger at the end. You might spend more cycles on arithmetic,
but you'd spend fewer on memory management.
Roedy Green
wrote, quoted or indirectly quoted someone who said :
>I was very surprised to see that java did not have a square root method
>at all of the java.math.BigInteger class, why is this?
Square root is normally considered to be a floating point operation
since most roots are not perfect integers.
--
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
Andreas Leitgeb
In integral contexts, the "integer square root" of a nonnegative integer
n is (afaik) usually defined as the largest integer i, for which i*i<=n.
Tcl (since 8.5) has such a function and calls it "isqrt". I think
it calculates it by starting with the floating-point approximation
and then gradually exactifying it with a couple iterations of Newton's
approximation algorithm (I've been told that with that start it
converges really fast). On my rather aged machine (1.2GHz), the
isqrt of a number of 150 randomly typed digits takes about
120 microseconds, double length takes about 380 microseconds, and
4times the length takes almost a millisecond.
That would make the roots of 2 and 3 to be both 1 (unlike rounding)
I'm aware that the OP asked for different behaviour than that.
Arne Vajhøj
> On Wed, 21 May 2008 12:40:58 +0100, bugbear wrote:
>> j1mb0jay wrote:
>>> I was very surprised to see that java did not have a square root method
>>> at all of the java.math.BigInteger class, why is this?
>> Probably because the result isn't a BigInteger
BigInteger's is surprisingly like int's.
3 is an int.
sqrt(3) is not an int.
QED
Arne
j1mb0jay
> On Wed, 21 May 2008 11:57:32 +0100, j1mb0jay <j1mb...@uni.ac.uk> wrote,
> quoted or indirectly quoted someone who said :
>
>>I was very surprised to see that java did not have a square root method
>>at all of the java.math.BigInteger class, why is this?
>
> Square root is normally considered to be a floating point operation
> since most roots are not perfect integers.
I understand this but the main use for the code that i have written is to
find out is a number has a perfect square, i use this to see if a number
is prime.
The method that I have written is very quick and will find the square
root of a thousand digit number of my newish laptop in just over 1000
milliseconds.
j1mb0jay
There has been much a do about other methods to use, but what about this
method. I understand that my use of doubles is poor and needs changing, I
have started to work on this already.
Please can I have some other ways of speeding it up, what about the start
point on the program is it an accurate enough start point?
Regards j1mb0jay
Jeremy Watts
round up/down the resulting decimal and convert it to a BigInteger.
It uses Newton-Raphson.
/**
* Write a description of class bigRoot here.
*
* @author jeremy watts
* @version (a version number or a date)
* @modified 22/10/06
*/
import java.math.BigDecimal;
public class bigRoot
{
// instance variables - replace the example below with your own
public static void main(String[] args)
{
BigDecimal argument;
BigDecimal result;
BigDecimal reconstituted;
int workingDecimalPlaceNumber;
argument = new BigDecimal("8.0");
workingDecimalPlaceNumber = 25;
int root = 10;
int index;
result = bigRoot(argument, root, workingDecimalPlaceNumber);
reconstituted = result;
reconstituted = reconstituted.pow(root);
System.out.println(result);
System.out.println(reconstituted);
}
public static BigDecimal bigRoot(BigDecimal argument, int root, int
workingDecimalPlaceNumber)
{
/* returns uncorrected root of a BigDecimal - uses the Newton Raphson
method.
* argument must be positive
*/
BigDecimal result;
BigDecimal xn;
BigDecimal oldxn;
BigDecimal xnPlusOne;
BigDecimal numerator;
BigDecimal denominator;
BigDecimal quotient;
BigDecimal constant;
int index;
int runIndex;
int iterationNumber = 200;
constant = new BigDecimal(root);
boolean halt;
if (argument.compareTo(BigDecimal.ZERO) != 0) {
xn = argument;
oldxn = xn;
halt = false;
runIndex = 1;
while ((halt == false) & (runIndex <= iterationNumber)) {
oldxn = xn;
numerator = xn;
denominator = numerator;
numerator = numerator.pow(root);
denominator = denominator.pow(root - 1);
denominator = (constant.multiply(denominator));
numerator = (numerator.subtract(argument));
if (denominator.compareTo(BigDecimal.ZERO) == 0) {
halt = true;
}
else {
quotient = (numerator.divide(denominator,
workingDecimalPlaceNumber, BigDecimal.ROUND_HALF_UP));
xnPlusOne = (xn.subtract(quotient));
xnPlusOne = xnPlusOne.setScale(workingDecimalPlaceNumber,
BigDecimal.ROUND_HALF_UP);
xn = xnPlusOne;
if (xnPlusOne.compareTo(oldxn) == 0) {
halt = true;
}
}
runIndex++;
}
result = xn;
}
else {
result = BigDecimal.ZERO;
}
return(result);
}
}
"j1mb0jay" <j1mb...@uni.ac.uk> wrote in message
news:spbdg5x...@news.aber.ac.uk...
>I was very surprised to see that java did not have a square root method
> at all of the java.math.BigInteger class, why is this?
>
Jeremy Watts
"Jeremy Watts" <jwatt...@hotmail.com> wrote in message
news:6vvZj.12$SA7...@newsfe09.ams2...
>I have a BigDecimal square root finder here you can have, just use it and
>round up/down the resulting decimal and convert it to a BigInteger.
>
> It uses Newton-Raphson.
just to not to confuse you, it actually finds the nth root of any number,
its currently in a demonstration class and is set at '10' so remember to
change it to '2' before you use it.
jeremy
Daniel Pitts
BigInteger square = new BigInteger("-1000");
BigInteger root = new BigInteger("0") {
public BigInteger multiply(BigInteger val) {
return new BigInteger("-1000");
}
};
assert root.multiply(root).equals(square);
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
j1mb0jay
Thank you will try it out !!
Regards j1mb0jay
Arne Vajhøj
> Posted the wring code, the code is below LOL !!!!
>
> -------------Square Root Code --------------------
>
> package math;
>
> import java.math.BigInteger;
>
> public class SquareRoot
> {
> public static BigInteger squareRoot(BigInteger testSubject,
> boolean round)
> {
My suggestion:
private final static BigInteger one = new BigInteger("1");
private final static BigInteger two = new BigInteger("2");
public static BigInteger sqrt(BigInteger v) {
int n = v.toByteArray().length;
byte[] b = new byte[n/2+1];
b[0] = 1;
BigInteger guess = new BigInteger(b);
while(true) {
BigInteger guessadd1 = guess.add(one);
BigInteger guesssub1 = guess.subtract(one);
if(guess.multiply(guess).compareTo(v) > 0) {
if(guesssub1.multiply(guesssub1).compareTo(v) <= 0) {
return guesssub1;
}
} else {
if(guessadd1.multiply(guessadd1).compareTo(v) > 0) {
return guess;
}
}
guess = guess.add(v.divide(guess)).divide(two);
}
}
Arne
burs...@gmail.com
The closed: JDK-8032027 : Add BigInteger square root methods
https://bugs.java.com/view_bug.do?bug_id=8032027
In the bug there is a mention of Zimmerman, but Hacker is in OpenJDK:
* @implNote The implementation is based on the material in Henry S. Warren,
* Jr., <i>Hacker's Delight (2nd ed.)</i> (Addison Wesley, 2013), 279-282.
https://github.com/netroby/jdk9-dev/blob/master/jdk/src/java.base/share/classes/java/math/MutableBigInteger.java#L1883
burs...@gmail.com
could gain more speed, if it would do instead of:
int shift = bitLength - 63;
Something as follows:
int shift = bitLength - 104;
The doubleValue() will take half even rounded 52 bits
of it, and an exponent, the sqrt() will again produce
52 bits, and when shifting back by shift/2, the Newton
start value will have 52 bits and not only 31 bits.
Then after ca. 10^1000 there should be threshold and
a switch to a Zimmerman implementation.