1 
import java.math.BigInteger;
import java.util.Random;

class Karatsuba {
private final static BigInteger ZERO = new BigInteger("0");

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

    // cutoff to brute force
    int N = Math.max(x.bitLength(), y.bitLength());
    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));
}


public static void main(String[] args) {
    long start, stop, elapsed;
    Random random = new Random();
    int N = Integer.parseInt(args[0]);
    BigInteger a = new BigInteger(N, random);
    BigInteger b = new BigInteger(N, random);

    start = System.currentTimeMillis(); 
    BigInteger c = karatsuba(a, b);
    stop = System.currentTimeMillis();
    StdOut.println(stop - start);

    start = System.currentTimeMillis(); 
    BigInteger d = a.multiply(b);
    stop = System.currentTimeMillis();
    StdOut.println(stop - start);

    StdOut.println((c.equals(d)));
}
}

n=位数

由于我们正在处理位级别的复杂性，因此每次加法都需要 O(n) 并且对于每个递归调用，至少有一个加法导致总数为 (n-2000)*n。我在这里做错了什么？

代码来自 - http://introcs.cs.princeton.edu/java/99crypto/Karatsuba.java.html

4

1 回答 1

2

因为只有 3 个递归调用而不是 4 个。参见幻灯片 5

BigInteger ac    = karatsuba(a, c);
BigInteger bd    = karatsuba(b, d);
BigInteger abcd  = karatsuba(a.add(b), c.add(d));
于 2016-12-24T14:18:22.823 回答