java/numeric/KaratsubaMultiply.java

package numeric;

import java.util.Arrays;

// https://en.wikipedia.org/wiki/Karatsuba_algorithm
public class KaratsubaMultiply {
    public static int[] karatsubaMultiply(int[] a, int[] b) {
        if (a.length < b.length)
            a = Arrays.copyOf(a, b.length);
        if (a.length > b.length)
            b = Arrays.copyOf(b, a.length);
        int n = a.length;
        int[] res = new int[n + n];
        if (n <= 10) {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++) res[i + j] = res[i + j] + a[i] * b[j];
        } else {
            int k = n >> 1;
            int[] a1 = Arrays.copyOfRange(a, 0, k);
            int[] a2 = Arrays.copyOfRange(a, k, n);
            int[] b1 = Arrays.copyOfRange(b, 0, k);
            int[] b2 = Arrays.copyOfRange(b, k, n);

            int[] a1b1 = karatsubaMultiply(a1, b1);
            int[] a2b2 = karatsubaMultiply(a2, b2);

            for (int i = 0; i < k; i++) a2[i] = a2[i] + a1[i];
            for (int i = 0; i < k; i++) b2[i] = b2[i] + b1[i];

            int[] r = karatsubaMultiply(a2, b2);
            for (int i = 0; i < a1b1.length; i++) r[i] = r[i] - a1b1[i];
            for (int i = 0; i < a2b2.length; i++) r[i] = r[i] - a2b2[i];

            System.arraycopy(r, 0, res, k, r.length);

            for (int i = 0; i < a1b1.length; i++) res[i] = res[i] + a1b1[i];
            for (int i = 0; i < a2b2.length; i++) res[i + n] = res[i + n] + a2b2[i];
        }
        return res;
    }

    // Usage example
    public static void main(String[] args) {
        // (3*x^2+2*x+1) * (4*x+3) = 12*x^3 + 17*x^2 + 10*x + 3
        System.out.println(
            Arrays.equals(new int[] {3, 10, 17, 12, 0, 0}, karatsubaMultiply(new int[] {1, 2, 3}, new int[] {3, 4})));
    }
}