Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Java (http://www.velocityreviews.com/forums/f30-java.html)
-   -   Square Root Of java.math.BigInteger (http://www.velocityreviews.com/forums/t616059-square-root-of-java-math-biginteger.html)

 j1mb0jay 05-21-2008 10:57 AM

Square Root Of java.math.BigInteger

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)
{
for(int i = 1; i < testSubject; i++)
{
return false;
return false;
}
return true;
}

 j1mb0jay 05-21-2008 11:50 AM

Re: Square Root Of java.math.BigInteger

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

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 05-21-2008 11:55 AM

Re: Square Root Of java.math.BigInteger

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

return retVal;
}
}

 j1mb0jay 05-21-2008 12:49 PM

Re: Square Root Of java.math.BigInteger

On Wed, 21 May 2008 08:06:47 -0400, Larry A Barowski wrote:

> "j1mb0jay" <j1mb0jay@uni.ac.uk> wrote in message
> news:spbdg5xp2l.ln2@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.

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 05-21-2008 12:56 PM

Re: Square Root Of java.math.BigInteger

On Wed, 21 May 2008 07:59:26 -0400, Lew wrote:

> j1mb0jay wrote:
>> 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 )?

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

Square root of 2 is 1.414213562. which rounds to 1.

Regards j1mb0jay

 j1mb0jay 05-21-2008 01:19 PM

Re: Square Root Of java.math.BigInteger

On Wed, 21 May 2008 08:46:15 -0400, 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.

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 05-21-2008 01:41 PM

Re: Square Root Of java.math.BigInteger

On Wed, 21 May 2008, 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?

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.../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)
> {
> for(int i = 1; i < testSubject; i++)
> {
> answer = Math.sqrt(testSubject / (double)i);
> 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 05-21-2008 02:43 PM

Re: Square Root Of java.math.BigInteger

On Wed, 21 May 2008 14:41:01 +0100, Tom Anderson wrote:

> On Wed, 21 May 2008, 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?

>
> 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.../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) {
>> for(int i = 1; i < testSubject; i++)
>> {
>> answer = Math.sqrt(testSubject / (double)i); if

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

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 05-21-2008 02:44 PM

Re: Square Root Of java.math.BigInteger

j1mb0jay wrote:
> On Wed, 21 May 2008 08:06:47 -0400, Larry A Barowski wrote:
>
>> "j1mb0jay" <j1mb0jay@uni.ac.uk> wrote in message
>> news:spbdg5xp2l.ln2@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.

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

 Patricia Shanahan 05-21-2008 03:10 PM

Re: Square Root Of java.math.BigInteger

j1mb0jay wrote:
> On Wed, 21 May 2008 08:06:47 -0400, Larry A Barowski wrote:
>
>> "j1mb0jay" <j1mb0jay@uni.ac.uk> wrote in message
>> news:spbdg5xp2l.ln2@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.

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

All times are GMT. The time now is 12:30 PM.