java - Karasuba算法的效率

Question

我试图构建我自己版本的 RSA 密码。
问题之一是找到一种快速有效的方法来将两个数字相乘。我自己对 BigInteger 代码的理解不足以计算其方法 multiply() 的时间复杂度，而评论说复杂度为 O(n²) 。我决定找到Karatsuba算法的代码并测试它。
结果……很奇怪。

几乎每次，普通乘法算法的效果都比Karatsuba更好，无论两个数字的位数或变量limitOfBitsForKaratsubaEfficiency(即位数)理论上来说，这两个数字必须让Karatsuba变得更有效率)。

现在，我研究了算法和实际实现:唐叶应该在理论上和实践上都获胜。有人知道为什么测试偏向于通用乘法算法吗？

<小时/>

我使用的代码如下。我只调整了两行代码:limitOfBitsForKaratsubaEfficiency 和 int N = Integer.parseInt("100000");

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

    // cutoff to brute force
    int N = Math.max(x.bitLength(), y.bitLength());
    if (N <= limitOfBitsForKaratsubaEfficiency)     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 x1 = x.shiftRight(N);
    BigInteger x0 = x.subtract(x1.shiftLeft(N));
    BigInteger y1 = y.shiftRight(N);
    BigInteger y0 = y.subtract(y1.shiftLeft(N));

    // compute sub-expressions
    BigInteger ac    = karatsuba(x0, y0);
    BigInteger bd    = karatsuba(x1, y1);
    BigInteger abcd  = karatsuba(x0.add(x1), y0.add(y1));

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


public static void main(String[] args) {
    long start, stopKara, stopNorma;
    Random random = new Random();
    int N = Integer.parseInt("100000");
    BigInteger a,b,c,d;

    for(int i=0 ; i<15 ; i++)
        {
        a = new BigInteger(N, random);
        b = new BigInteger(N, random);
        System.out.printf("The numbers to be multiplied are: \n\t %s \n\t %s\n", a.toString(), b.toString());

        start = System.nanoTime(); 
        c = karatsuba(a, b);
        stopKara = System.nanoTime();
        stopKara = stopKara - start;
        System.out.printf("The karatsuba algorithm has computed %d milliseconds.\n", stopKara);

        start = System.nanoTime(); 
        d = a.multiply(b);
        stopNorma = System.nanoTime();
        stopNorma = stopNorma - start;
        System.out.printf("The common multiplication algorithm has computed %d milliseconds.\n", stopNorma);

        if(c.equals(d)) System.out.println("The two products are equals.");
        else                System.out.println("The two products are NOT equals: the karatsuba method does not works!");
        System.out.printf("The difference Time(Karatsuba)-Time(normalAlgorithm) is: \t %d", stopKara - stopNorma);

        System.out.printf("\n\n\n");
        }
}
    static BigInteger TWO = BigInteger.valueOf(2);
    static BigInteger ONE = BigInteger.ONE;
    static int limitOfBitsForKaratsubaEfficiency = 640;

<小时/>

编辑:我找到了 BigInteger.multiply() 使用的两种方法。我绝对不是位对位运算方面的专家，但是两个 for-cicle 让我认为复杂度是 O(n²)。唐叶应该是 O(n ^1.585 )。

  /** Multiply x[0:len-1] by y, and write the len least
   * significant words of the product to dest[0:len-1].
   * Return the most significant word of the product.
   * All values are treated as if they were unsigned
   * (i.e. masked with 0xffffffffL).
   * OK if dest==x (not sure if this is guaranteed for mpn_mul_1).
   * This function is basically the same as gmp's mpn_mul_1.
   */
  public static int mul_1 (int[] dest, int[] x, int len, int y)
  {
    long yword = (long) y & 0xffffffffL;
    long carry = 0;
    for (int j = 0;  j < len; j++)
      {
        carry += ((long) x[j] & 0xffffffffL) * yword;
        dest[j] = (int) carry;
        carry >>>= 32;
      }
    return (int) carry;
  }

  /**
   * Multiply x[0:xlen-1] and y[0:ylen-1], and
   * write the result to dest[0:xlen+ylen-1].
   * The destination has to have space for xlen+ylen words,
   * even if the result might be one limb smaller.
   * This function requires that xlen >= ylen.
   * The destination must be distinct from either input operands.
   * All operands are unsigned.
   * This function is basically the same gmp's mpn_mul. */
  public static void mul (int[] dest,
              int[] x, int xlen,
              int[] y, int ylen)
  {
    dest[xlen] = MPN.mul_1 (dest, x, xlen, y[0]);

    for (int i = 1;  i < ylen; i++)
      {
    long yword = (long) y[i] & 0xffffffffL;
    long carry = 0;
    for (int j = 0;  j < xlen; j++)
      {
        carry += ((long) x[j] & 0xffffffffL) * yword
          + ((long) dest[i+j] & 0xffffffffL);
        dest[i+j] = (int) carry;
        carry >>>= 32;
      }
    dest[i+xlen] = (int) carry;
      }
  }

Answer 1

根据https://en.wikipedia.org/wiki/Karatsuba_algorithm

“两个 n 位数字相乘的标准过程需要一些与 n^2\,! 或\Theta(n^2)\,! 成比例的初等运算”

因此，您可以期待相同的大 O，但是该实现将产生更多垃圾，并且在不访问原始底层数据的情况下可能会降低效率。