Square Root Of java.math.BigInteger

J

j1mb0jay

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;
}
 
J

j1mb0jay

Probably because the result isn't a BigInteger



Look up "numerical analysis". It's what you're doing, albeit
unknowingly.

BugBear

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
 
J

j1mb0jay

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)
{
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;
}
}
 
J

j1mb0jay

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.

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
 
J

j1mb0jay

What is the square root of 2?

What should be the square root of BigInteger.valueOf( 2 )?

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
 
J

j1mb0jay

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.

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
 
T

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
 
J

j1mb0jay

People don't often do roots on integers. Roots tend to be a continuous
maths thing.


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

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

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
 
P

Patricia Shanahan

j1mb0jay said:
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.

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
 
P

Patricia Shanahan

j1mb0jay said:
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.

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
 
T

Tom Anderson

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!


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
 
J

john

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.
 
J

john

j1mb0jay said:
[...]
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.

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
 
J

john

j1mb0jay said:
[...]
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.

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

Woops, make that "ends in 2,3,7 or 8. Perfect squares can end in 9
(e.g. 3^2).

-John
 
J

john

j1mb0jay said:
[...]
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.

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

I meant they can't end in 2,3, 7 or 8. Perfect squares can end in 9.
 
T

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.

tom
 
R

Roedy Green

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.
 
A

Andreas Leitgeb

Lew said:
What is the square root of 2?
What should be the square root of BigInteger.valueOf( 2 )?

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.
 
A

Arne Vajhøj

j1mb0jay said:
Why would the result of square rooting an BigInteger not be a BigInteger

BigInteger's is surprisingly like int's.

3 is an int.

sqrt(3) is not an int.

QED

Arne
 
J

j1mb0jay

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,830
Latest member
ZADIva7383

Latest Threads

Top