Karazuba (+number multiplication)

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

public class Karazuba {

    final static int THRESHOLD = 20;

    // should be of equal length
    static long[] mult(long[] f, long[] g) {
        if (f.length <= THRESHOLD)
            return multStupid(f, g);
        int d = (f.length + 1) >> 1;
        long[] f1 = Arrays.copyOf(f, d);
        long[] f2 = Arrays.copyOfRange(f, d, f.length);
        long[] g1 = Arrays.copyOf(g, d);
        long[] g2 = Arrays.copyOfRange(g, d, g.length);
        long[] f1_g1 = mult(f1, g1);
        long[] f2_g2 = mult(f2, g2);
        long[] f1_g2_f2_g1 = sub_from(sub_from(mult(sum(f1, f2), sum(g1, g2)), f1_g1), f2_g2);
        long[] ret = new long[f.length + g.length - 1];
        for (int i = 0; i < f1_g1.length; i++)
            ret[i] += f1_g1[i];
        for (int i = 0, shift = d << 1; i < f2_g2.length; i++)
            ret[i + shift] += f2_g2[i];
        for (int i = 0, shift = d; i < f1_g2_f2_g1.length; i++)
            ret[i + shift] += f1_g2_f2_g1[i];
        return ret;
    }

    static long[] sum(long[] f1, long[] f2) {
        for (int i = 0; i < f2.length; i++)
            f1[i] += f2[i];
        return f1;
    }

    static long[] sub_from(long[] f1, long[] f2) {
        if (f2.length > f1.length)
            throw new AssertionError();
        for (int i = 0; i < f2.length; i++) {
            f1[i] -= f2[i];
        }
        return f1;
    }

    static long[] multStupid(long[] f, long[] g) {
        long[] ret = new long[f.length + g.length - 1];
        for (int i = 0; i < f.length; i++) {
            for (int j = 0; j < g.length; j++) {
                ret[i + j] += f[i] * g[j];
            }
        }
        return ret;
    }

    // multiplying numbers
    final static int D = 7;

    static char[] multNumbers(char[] a, char[] b) {
        if (a.length != b.length)
            throw new AssertionError();
        final int[] pow10 = new int[D];
        pow10[0] = 1;
        for (int i = 1; i < D; i++)
            pow10[i] = pow10[i - 1] * 10;
        long[] f = new long[(a.length + D - 1) / D];
        long[] g = new long[(b.length + D - 1) / D];
        for (int i = 0; i < a.length; i++)
            f[i / D] += (a[a.length - i - 1] - '0') * pow10[i % D];
        for (int i = 0; i < b.length; i++)
            g[i / D] += (b[b.length - i - 1] - '0') * pow10[i % D];
        long[] fg = mult(f, g);
        return normalize(fg);
    }

    static char[] normalize(long[] fg) {
        char[] ab = new char[fg.length * D + 20];
        int pos = 0;
        long x = 0;
        for (int i = 0; i < fg.length; i++) {
            x += fg[i];
            for (int j = 0; j < D; j++) {
                ab[pos++] = (char) ((x % 10) + '0');
                x /= 10;
            }
        }
        while (x > 0) {
            ab[pos++] = (char) ((x % 10) + '0');
            x /= 10;
        }
        int len;
        for (len = ab.length; len > 1 && (ab[len - 1] == 0 || ab[len - 1] == '0'); len--)
            ;
        ab = Arrays.copyOf(ab, len);
        for (int i = 0; 2 * i < ab.length; i++) {
            char tmp = ab[i];
            ab[i] = ab[ab.length - 1 - i];
            ab[ab.length - 1 - i] = tmp;
        }
        return ab;
    }

    // testing

    static boolean areEqual(long[] f1, long[] f2) {
        if (f1.length != f2.length)
            return false;
        for (int i = 0; i < f1.length; i++) {
            if (f1[i] != f2[i])
                return false;
        }
        return true;
    }

    static Random rand = new Random();

    static void stressTest() {
        for (int iter = 0;; iter++) {
            singleTest(5000 + rand.nextInt(5000));
            System.err.println("Test " + iter + " passed");
        }
    }

    static void singleTest(int n) {
        long[] f = new long[n];
        long[] g = new long[n];
        for (int i = 0; i < n; i++) {
            f[i] = rand.nextInt(10);
            g[i] = rand.nextInt(10);
        }
        if (!areEqual(mult(f, g), multStupid(f, g)))
            throw new AssertionError();
    }

    static void maxTest() {
        int N = 100000;
        long[] f = new long[N];
        for (int i = 0; i < N; i++)
            f[i] = 1;
        long start_time = System.currentTimeMillis();
        mult(f, f);
        long end_time = System.currentTimeMillis();
        System.err.println("Time consumed: " + (end_time - start_time) + "ms");
    }

    static void numbersMaxTest() {
        int N = 500000;
        char[] a = new char[N];
        for (int i = 0; i < N; i++)
            a[i] = '1';
        long start_time = System.currentTimeMillis();
        multNumbers(a, a);
        long end_time = System.currentTimeMillis();
        System.err.println("Time consumed: " + (end_time - start_time) + "ms");
    }

    static void numbersSingleTest(int n) {
        char[] a = new char[n];
        char[] b = new char[n];
        for (int i = 0; i < n; i++) {
            a[i] = (char) (rand.nextInt(10) + '0');
            b[i] = (char) (rand.nextInt(10) + '0');
        }
        String w = new String(multNumbers(a, b));
        BigInteger ab = new BigInteger(new String(a)).multiply(new BigInteger(new String(b)));
        if (!w.equals(ab.toString()))
            throw new AssertionError();
    }

    static void numbersStressTest() {
        for (int iter = 0; iter < 100; iter++) {
            numbersSingleTest(5000);
            System.err.println("Test " + iter + " passed");
        }
    }
}