Exercice 1 : Karatsuba

[isakkar]

int karatsuba(int x, int y, int n) {
if(x==0 || y==0)
return 0;
if(x==1)
return y;
if(y==1)
return x;
int k = n >> 1;
int a = x >> k;
int b = x-(a<<k);
int c = y >> 1;
int d = y-(c<<k);
int ac = karatsuba(a,c,k);
int bd = karatsuba(b,d,k);
return (ac<<n) + bd + ((ac+bd-karatsuba(a-b,c-d,k)) << k);
}

[fortierq]

J'obtiens 58 au lieu de 42 avec karatsuba(6, 7, 4) : code sur repl.it

[isakkar]

En effet, on dirait que ça marche juste pour les nombres à 4 bits exactement (de 8 à 15)

[fortierq]

Le problème est que a - b et c - d peuvent être négatifs (un nombre négatif est représenté en complément à 2 et non pas en base 2). Il y avait aussi shifts (>>) qui ne marchaient pas si le nombre n'a pas exactement $n$ bits.
Voici une correction