Re: Square Root Of java.math.BigInteger
On May 21, 4:57 am, j1mb0jay <j1mb0...@uni.ac.uk> 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?
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;
}
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.