Karatsuba sur des tableaux de chiffres

Le programme complet est KaratsubaTableaux.java. Avec $h=\lceil n/2\rceil$, on coupe $x=x_1\cdot 10^h+x_0$ (les $h$ premiers chiffres du tableau forment $x_0$) et l'on calcule trois produits récursifs. Deux précautions sont nécessaires.

• On retire les zéros de tête avant chaque appel : sinon les tableaux ne raccourcissent pas.
• La somme $x_1+x_0$ a jusqu'à $h+1$ chiffres. Pour $n\le 3$, $h+1$ n'est pas inférieur à $n$ et la récursivité ne descendrait plus : la base doit couvrir au moins $n\le 3$.

static int[] karatsuba0(int[] x, int[] y) { int n = Math.max(x.length, y.length);
    if (n <= Math.max(seuil, 3)) return produitEcole(x, y);  // base
    int h = (n + 1) / 2;
    int[] x0 = Arrays.copyOfRange(x, 0, Math.min(h, x.length)),
          x1 = h < x.length ? Arrays.copyOfRange(x, h, x.length) : new int[] {0};
    int[] y0 = Arrays.copyOfRange(y, 0, Math.min(h, y.length)),
          y1 = h < y.length ? Arrays.copyOfRange(y, h, y.length) : new int[] {0};
    int[] a = karatsuba0(sansZeros(x1), sansZeros(y1));       // x1.y1
    int[] c = karatsuba0(sansZeros(x0), sansZeros(y0));       // x0.y0
    int[] b = karatsuba0(sansZeros(plus(x1, x0)), sansZeros(plus(y1, y0)));
    moinsEnPlace(b, a); moinsEnPlace(b, c);                  // b = x1.y0 + x0.y1
    int[] p = new int[x.length + y.length + 2];
    ajouterDecale(p, c, 0);                                  // + x0.y0
    ajouterDecale(p, b, h);                                  // + b.10^h
    ajouterDecale(p, a, 2 * h);                              // + x1.y1.10^(2h)
    return p;
}

Les fonctions auxiliaires (plus, moinsEnPlace, ajouterDecale, sansZeros) sont en $\Theta (n)$ et sont données dans le programme. Vérification puis mesures :

200 produits verifies avec BigInteger : true
n= 1000  ecole     2,5 ms  karatsuba(seuil 1)     2,9 ms  karatsuba(seuil 32)    0,7 ms  egaux=true
n= 2000  ecole    10,1 ms  karatsuba(seuil 1)     8,7 ms  karatsuba(seuil 32)    2,2 ms  egaux=true
n= 4000  ecole    40,7 ms  karatsuba(seuil 1)    25,6 ms  karatsuba(seuil 32)    6,7 ms  egaux=true
n= 8000  ecole   167,6 ms  karatsuba(seuil 1)    76,1 ms  karatsuba(seuil 32)   21,0 ms  egaux=true

Quand $n$ double, la méthode de l'école est multipliée par environ $4$ ($n^2$), Karatsuba par environ $3$ ($n^{{\log }_{2}3}$). Sans seuil, Karatsuba ne l'emporte qu'à partir de $2000$ chiffres environ : les nombreux petits appels coûtent cher. Avec un seuil de $32$ chiffres, il est plus rapide dès $1000$ chiffres, et huit fois plus rapide à $8000$. Les mesures dépendent de la machine ; leur évolution quand $n$ double, non.