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