859 views

Skip to first unread message

May 21, 2008, 6:57:32 AM5/21/08

to

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?

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;

}

May 21, 2008, 7:40:58 AM5/21/08

to

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?

> 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

May 21, 2008, 7:50:23 AM5/21/08

to

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

May 21, 2008, 7:55:07 AM5/21/08

to

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;

}

}

May 21, 2008, 7:59:26 AM5/21/08

to

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

> 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

May 21, 2008, 8:06:47 AM5/21/08

to

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

May 21, 2008, 8:46:15 AM5/21/08

to

j1mb0jay wrote:

>

> Why would the result of square rooting an BigInteger not be a BigInteger

>

> 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

May 21, 2008, 8:49:58 AM5/21/08

to

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

May 21, 2008, 8:56:24 AM5/21/08

to

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

May 21, 2008, 9:19:16 AM5/21/08

to

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

May 21, 2008, 9:41:01 AM5/21/08

to

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

May 21, 2008, 10:43:13 AM5/21/08

to

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

May 21, 2008, 10:44:26 AM5/21/08

to

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

May 21, 2008, 11:10:47 AM5/21/08

to

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

May 21, 2008, 11:57:44 AM5/21/08

to

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

May 21, 2008, 12:09:52 PM5/21/08

to

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.

May 21, 2008, 12:33:24 PM5/21/08

to

j1mb0jay wrote:

> [...]

> But if you are going all imaginary on me then maybe the answer might be

> 31.622776602i - rather complex !!!!

> [...]

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

May 21, 2008, 12:50:07 PM5/21/08

to

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

May 21, 2008, 12:52:38 PM5/21/08

to

Woops, make that "ends in 2,3,7 or 8. Perfect squares can end in 9

(e.g. 3^2).

-John

May 21, 2008, 12:53:37 PM5/21/08

to

Tom Anderson wrote:

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

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

May 21, 2008, 12:54:15 PM5/21/08

to

On May 21, 10:50 am, john <johnmortal.for...@gmail.com> wrote:

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

May 21, 2008, 1:39:59 PM5/21/08

to

john wrote:

> [...] 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.

> [...] 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. ;-)

May 21, 2008, 1:58:39 PM5/21/08

to

On Wed, 21 May 2008, john wrote:

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

May 21, 2008, 5:49:30 PM5/21/08

to

On Wed, 21 May 2008 11:57:32 +0100, j1mb0jay <j1mb...@uni.ac.uk>

wrote, quoted or indirectly quoted someone who said :

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

May 21, 2008, 6:48:40 PM5/21/08

to

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.

May 21, 2008, 7:16:28 PM5/21/08

to

j1mb0jay wrote:

> 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

> 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

> 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

May 22, 2008, 6:44:24 AM5/22/08

to

On Wed, 21 May 2008 21:49:30 +0000, Roedy Green wrote:

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

May 22, 2008, 7:23:42 AM5/22/08

to

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

May 23, 2008, 4:45:54 AM5/23/08

to

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.

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?

>

May 23, 2008, 6:25:03 AM5/23/08

to

"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

May 23, 2008, 9:53:10 AM5/23/08

to

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

May 23, 2008, 11:08:14 AM5/23/08

to

Thank you will try it out !!

Regards j1mb0jay

May 24, 2008, 11:46:53 PM5/24/08

to

j1mb0jay wrote:

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

> {

> 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

Jul 10, 2018, 7:26:50 AM7/10/18

to

JDK 9 has now Hacker sqrt():

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

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

Jul 12, 2018, 7:38:23 AM7/12/18

to

Some empirical data, the JDK 9 implementation

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.

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.

Jul 12, 2018, 9:12:18 AM7/12/18

to

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu