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)

> {

> 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