Ошибка Выполнение алгоритма karatsuba с BigInteger

Я пытаюсь реализовать алгоритм karatsuba с Java, подающим в суд на BigInteger, я выполнил все шаги, но я не получаю правильный результат, что заставляет меня сходить с ума.Ошибка Выполнение алгоритма karatsuba с BigInteger

Вот мой код:

public BigInteger karatsuba(BigInteger a, BigInteger b, int base) { 
    if (a.compareTo(BigInteger.TEN) == -1 || b.compareTo(BigInteger.TEN) == -1) { 
     return a.multiply(b); 
    } 

    /* calculates the size of the numbers */ 
    int tam = a.toString().length(); 
    int mitad = tam/2; 


    BigInteger a1 = (a.divide(BigInteger.valueOf((long) Math.pow(base, mitad)))); 
    BigInteger a0 = (a.remainder(BigInteger.valueOf((long) Math.pow(base, mitad)))); 

    BigInteger b1 = (b.divide(BigInteger.valueOf((long) Math.pow(base, mitad)))); 
    BigInteger b0 = (b.remainder(BigInteger.valueOf((long) Math.pow(base, mitad)))); 

    /* 3 calls made to numbers approximately half the size */ 
    BigInteger t1 = karatsuba(a1, b1, base); 
    BigInteger t2 = karatsuba(a0, b0, base); 
    BigInteger t3 = karatsuba(a1.add(a0), b1.add(b0), base); 

    BigInteger aux1 = (t1.multiply(BigInteger.valueOf((long)Math.pow(base, tam)))); 
    BigInteger aux2 = t1.subtract(t2); 
    BigInteger aux4 = aux2.subtract(t3); 
    BigInteger aux3 = aux4.multiply(BigInteger.valueOf((long) Math.pow(base,mitad)).add(t2)); 

    return aux1.add(aux3); 

}

Я тестировал код с помощью следующей записи: karatsuba(new BigInteger("1252",new BigInteger("532") , 10) в то время как правильный результат 666064, я получаю 2212864 !!!. и я отлаживался, было удивление, что когда поток выполнения поступает в оператор возврата, программа не останавливается, но она переходит к оператору BigInteger t2 = karatsuba(a0, b0, base);.

Так что я не знаю, что я делаю неправильно. Любая помощь будет очень оценена.

источник

2017-02-04 shadow

не JAVA-кодер, поэтому я могу ошибаться, но: 1. 'Math.pow (base, mitad)' является подозрительным, так как результатом является 'float', который, скорее всего, не соответствует результату. поэтому все уровни рекурсии должны быть вызваны до того, как окончательный возврат действительно вернется ... Поскольку я не использую большое целое число, я не уверен, что 'a.divide, a.remainder' действительно делает то, что вы хотите. Если это действительно деление и модуль, то это неверно, поскольку вам нужно разделить внутреннее представление bigint, а не само число, иначе вы бы использовали bigint '/,%' для bigint '*', который является безумием. – Spektre

Это, вероятно, не ваша проблема (поскольку 1252 и 532 находятся в диапазоне не больших целых чисел), но «Math.pow» вряд ли будет работать правильно для реальных больших целых чисел. Вероятно, это также не ваша проблема (поскольку вы тестируете с базовым значением 10), но 'a.toString(). Length()' вряд ли вычислит правильный размер, если 'base' равно 10. –

btw здесь [Быстрое вычисление квадратов бигнума] (http://stackoverflow.com/q/18465326/2521214) вы можете найти в конце свою реализацию арбнума Карацубы в C++ (arbnum - произвольный мантисса-плавающий, чтобы вы могли игнорировать материал экспоненты для bigints) – Spektre

Вот Karatsuba algorithm implementation из Принстонского университета «Введение в программирование на Java» курса:

public static BigInteger karatsuba(BigInteger x, BigInteger y) { 

    // cutoff to brute force 
    int n = Math.max(x.bitLength(), y.bitLength()); 
    if (n <= 10) return x.multiply(y); 

    // number of bits divided by 2, rounded up 
    n = (n/2) + (n % 2); 

    final BigInteger b = x.shiftRight(n); 
    final BigInteger a = x.subtract(b.shiftLeft(n)); 
    final BigInteger d = y.shiftRight(n); 
    final BigInteger c = y.subtract(d.shiftLeft(n)); 

    // compute sub-expressions 
    final BigInteger ac = karatsuba(a, c); 
    final BigInteger bd = karatsuba(b, d); 
    final BigInteger abcd = karatsuba(a.add(b), c.add(d)); 

    return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(n)).add(bd.shiftLeft(2 * n)); 
    }

Я думаю, вы можете смело использовать его.

источник

2017-03-11 09:46:36 Nolequen

Ошибка Выполнение алгоритма karatsuba с BigInteger

ответ

Смежные вопросы