Требуется помощь с программой для развлекательной игры

Question

Я работаю над проблемой факторизации, и для небольших чисел она работает хорошо.Я смог рассчитать факторы (получая ответы от Wolfram Alpha) для небольших чисел, например, на странице Википедии (5959).

Вместе со страницей Википедии я следовал это руководство .Еще раз, поскольку мои знания по математике довольно скудны, я не могу понять, что мне нужно делать дальше.

РЕДАКТИРОВАТЬ: Наконец-то работает!Я опубликую здесь рабочий код, как только он полностью заработает, чтобы другие в моем затруднительном положении могли извлечь из него урок.

Answer 1

Этот getIntSqrt() метод ... Я не знаю, нормально ли это, но выглядит ужасно (преобразовать BigInteger в String ??) Вы проверяли это?

Здесь (очевидно) лучший метод.

Answer 2

В вашем цикле:

// while b2 not square
while(!(isSqrt(b2, root))) {

Какова цель следующей инструкции?

    root = root.add(b2.divide(root)).divide(TWO);

Я думаю, что для проверки того, что b2 является квадратом, вместо этого вы должны попытаться вычислить квадратный корень (приведенная выше инструкция - всего лишь один шаг канонического алгоритма для вычисления квадратных корней) с помощью уже используемого метода есть:

    root = getIntSqrt(b2);

То же самое относится к этому коду:

// ??
final int bitLength = N.bitLength();
BigInteger root = BigInteger.ONE.shiftLeft(bitLength / 2);
root = root.add(b2.divide(root)).divide(TWO);

EDIT . Проблема в том, что вашему методу sqrt() требуется isSqrt(), который проверяет, является ли root приблизительным корнем n, тогда как цикл в fermat() нуждается в точной проверке. Я добавляю код, который, кажется, прошел ваш последний тест:

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

Answer 3

Ваша isSqrt() функция не подходит для того, что вы пытаетесь сделать.Вы хотите знать, точно ли n = root^2, но ваша функция IsSqrt() написана так, чтобы возвращать "true", если n просто лежит в интервале (root^2, (root+1)^2).

Я думаю, все, что вам нужно сделать, эточтобы проверить, что n равно root.pow(2).