Efficiency of Karatsuba algorithm

Question

I was trying to build my own version of the RSA cypher.
One of the problem is to have a fast and effient way to multiply two numbers. I didn't understand the BigInteger code enought to calculate the time complexity of its method multiply() myself, while the reviews said the complexity was O(n²) . I decided to find the code for the Karatsuba algorithm and test it.
The results were... strange.

Pretty much every time the common multiplication algorithm works better than Karatsuba, regardless of the number of bits of the two numbers or the variable limitOfBitsForKaratsubaEfficiency (i.e. the number of bits the two numbers must have for the Karatsuba to be more efficient... in theory).

Now, I studied both the algorithm and the actual implementation: Karatsuba should win both in theory and in practice. Someone knows why the tests favors the common multiplication algorithm?

---

The code I used is below. I tweaked only two lines of code: limitOfBitsForKaratsubaEfficiency and 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;

---

EDIT: I found the two methods used by the BigInteger.multiply(). I'm definitely no expert in bit-to-bit operations, but the two for-cicles let me think that the complexity is O(n²). Karatsuba should be 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

According to https://en.wikipedia.org/wiki/Karatsuba_algorithm

"The standard procedure for multiplication of two n-digit numbers requires a number of elementary operations proportional to n^2\,!, or \Theta(n^2)\,! "

As such you can expect the same big-O, however the implementation will produce much more garbage and is likely to be less efficient without access to the raw underlying data.