Require help with program for edutainment game
I am working on a factorisation problem and for small numbers it is working well. I've been able to calculate the factors (getting the answers from Wolfram Alpha) for small numbe开发者_运维百科rs, like the one on the Wikipedia page (5959).
Along with the Wikipedia page I have been following this guide. Once again, as my Math knowledge is pretty poor I cannot follow what I need to do next.
EDIT: It finally works! I'll post the working code up here once I've got it fully working so that others in my predicament can learn from it.
That getIntSqrt()
method... I don't know if it's ok, but it looks awful (convert the BigInteger to String ??) Have you checked it?
Here is a (apparently) better method.
In your loop:
// while b2 not square
while(!(isSqrt(b2, root))) {
what is the purpose of the following instruction?
root = root.add(b2.divide(root)).divide(TWO);
I think that in order to check that b2
is a square, you should instead try to compute the square root (the above instruction is just one step of the canonical algorithm to compute square roots), with the method you already have:
root = getIntSqrt(b2);
The same observation applies to this code:
// ??
final int bitLength = N.bitLength();
BigInteger root = BigInteger.ONE.shiftLeft(bitLength / 2);
root = root.add(b2.divide(root)).divide(TWO);
EDIT. The problem is that your sqrt()
method needs an isSqrt()
that checks whether root
is an approximate root of n
, whereas the loop in fermat()
needs an exact check.
I append some code that seems to pass your last test:
import java.math.BigInteger;
public class Fermat {
private BigInteger a, b, N;
private static final BigInteger TWO = BigInteger.valueOf(2);
private static boolean isApproximateSqrt(BigInteger n, BigInteger root) {
final BigInteger lowerBound = root.pow(2);
final BigInteger upperBound = root.add(BigInteger.ONE).pow(2);
return lowerBound.compareTo(n) <= 0
&& n.compareTo(upperBound) < 0;
}
private static BigInteger intSqrt(BigInteger n) {
if (n.signum() >= 0) {
final int bitLength = n.bitLength();
BigInteger root = BigInteger.ONE.shiftLeft(bitLength / 2);
while ( ! isApproximateSqrt(n, root) ) {
root = root.add(n.divide(root)).divide(TWO);
}
return root;
} else {
throw new ArithmeticException("square root of negative number");
}
}
private void init() {
a = intSqrt(N); // a <- ceil(sqrt(N))
BigInteger b2, root;
do {
a = a.add(BigInteger.ONE); // a <- a + 1
b2 = (a.multiply(a)).subtract(N); // b2 <- (a * a) - N
root = intSqrt(b2);
} while( root.pow(2).compareTo(b2) != 0 ); // while b2 not exact sqrt
b = root;
}
public void print() {
BigInteger a2 = a.pow(2);
BigInteger b2 = b.pow(2);
BigInteger squareDifference = a2.subtract(b2);
System.out.println("A: " + a + "\nB: " + b);
System.out.println("A^2: " + a2 + "\nB^2: " + b2);
System.out.println("N: " + N);
if(squareDifference.compareTo(N) != 0) {
System.out.println("Something is wrong....");
}
}
public Fermat(BigInteger aNumber) {
N = aNumber;
init();
}
public static void main(String[] args) {
Fermat f = new Fermat(new BigInteger("90283"));
f.print();
}
}
Your isSqrt()
function isn't correct for what you're trying to do. You want to
know if n = root^2
exactly, but your IsSqrt()
function is written to return "true" if
n
merely lies in the interval (root^2, (root+1)^2)
.
I think all you need to do is to check that n
equals root.pow(2)
.
精彩评论