Square Root Of java.math.BigInteger

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

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

 

[Jeremy Watts]

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.



/**
* 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);
}
}

 

[Jeremy Watts]

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

/**
* 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);
}
}

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

 

[Daniel Pitts]

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.

Done.

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

 

[j1mb0jay]

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.



/**
* 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);
}
}

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

Thank you will try it out !!

Regards j1mb0jay

 

[Arne Vajhøj]

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