BigInteger оптимизированное по времени умножение

Привет, я хочу, чтобы умножить 2 больших целого числа наиболее своевременно оптимизированным способом. Я в настоящее время использую алгоритм Карацубы. Может кто-нибудь предложить более оптимизированный способ или алгоритм сделать это.

Спасибо

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

        // cutoff to brute force
        int N = Math.max(x.bitLength(), y.bitLength());
        System.out.println(N);
        if (N <= 2000) return x.multiply(y);                // optimize this parameter

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

        // x = a + 2^N b,   y = c + 2^N d
        BigInteger b = x.shiftRight(N);
        BigInteger a = x.subtract(b.shiftLeft(N));
        BigInteger d = y.shiftRight(N);
        BigInteger c = y.subtract(d.shiftLeft(N));

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

        return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
    }
Источник

2 ответа

Решение

Версия BigInteger в jdk8 переключается между наивным алгоритмом, алгоритмом Toom-Cook и Карацубой в зависимости от размера ввода, чтобы получить отличную производительность.

Источник

Сложность и фактическая скорость - это очень разные вещи на практике из-за постоянных факторов, используемых в нотации O. Всегда есть точка, где сложность преобладает, но она вполне может быть вне диапазона (размера входного сигнала), с которым вы работаете. Детали реализации (уровень оптимизации) алгоритма также напрямую влияют на эти постоянные факторы.

Я предлагаю попробовать несколько разных алгоритмов, желательно из библиотеки, которую авторы уже потратили на оптимизацию, и на самом деле измерить и сравнить их скорости на ваших входах.

Что касается SPOJ, не забывайте о возможности того, что основная проблема лежит в другом месте (то есть не в скорости умножения больших целых чисел).

Источник
Другие вопросы по тегам