Problème — Multiplier de grands entiers (Karatsuba)

Problème — Multiplier de grands entiers (Karatsuba).

Pour multiplier deux entiers $x$ et $y$ de $n$ chiffres, la méthode de l'école effectue $n^2$ multiplications de chiffres. On écrit $x=a\times 10^k+b$ et $y=c\times 10^k+d$, avec $b,d<10^k$ et $k$ environ $n/2$.

• Vérifier que $xy=ac\times 10^{2k}+(ad+bc)\times 10^k+bd$, et que $ad+bc=(a+b)(c+d)-ac-bd$.
• En déduire une fonction récursive karatsuba(x, y) qui n'effectue que trois appels récursifs (le cas de base, pour un entier d'un seul chiffre, utilise *). La tester sur $1234\times 5678$.
• On note $M(n)$ le nombre de multiplications de chiffres pour deux nombres de $n$ chiffres, $n$ puissance de $2$, en admettant que $M(1)=1$ et $M(n)=3M(n/2)$. Calculer $M(1024)$ et comparer avec la méthode de l'école.