Salut tout le monde, pour un projet en informatique je dois concevoir une bibliothèque de gestion d'entiers de taille arbitraire. L'entier est représenté sous la forme d'une liste doublement chainée d'entier de taille inférieure à 10000.

Par exemple, un entier 45 6231 8903 sera représenté :
Pointeur->8903->6231->0045->NULL

Je bloque sur une fonction permettant de calcul le produit d'un grand entier N par un autre entier M. Bien sûr, je pourrais faire M fois l'opération N+N+...+N (j'ai déjà codé l'addition) mais ça n'est pas vraiment optimisé.

J'ai donc cherché sur google des algorithmes de multiplication et je suis tombé sur l'algorithme de Karatsuba qui m'a l'air d'être adapté à mon cas. Le problème, c'est que j'ai du mal à saisir le fonctionnement de l'algorithme et j'ai encore plus de mal à l'implémenter dans mon programme, donc ce serait sympa si quelqu'un pouvait me détailler le fonctionnement de l'algorithme

Qu'est ce que tu ne comprend pas dans cet algo ?

Si tu as deux nombres a et b stockés dans une seule case (donc compris entre 0 et 9999), pour multiplier, tu fait juste a*b (c'est pour ça qu'ils sont plus petit que 10000, car tu es sûr que le résultat peut tenir dans un entier, ensuite il faudra faire attention au retenue).

Maintenant, si tes nombres sont plus grand, tu applique recursivement l'algorithme de karatsuba sur la moitié de chaque nombre pour les multiplier :

fonction mult(a,b)
l1 <- taille(a) // le nombre de case de a
l2 <- taille(b) // le nombre de case de b
l <- max(l1,l2)
B <- 10000^(l/2)
a1 = a / B // on enleve les l/2 premières cases de a
b1 = b / B // on enleve les l/2 premières cases de b
a2 = a % B // modulo : on ne garde que les l/2 premières cases
b2 = b % B // modulo : on ne garde que les l/2 premières cases

// ici, il y a des appels récursifs à ta fonctions mult
z1 <- mult(a1,b1)
z3 <- mult(a2,b2)
z2 <- mult(a1+a2,b1+b2) - z1 - z3
// addition et soustraction se font avec des fonctions pour tes listes chaînées

r <- z1 * B * B + z2 * B + z3
renvoie r

À noter que tu n'a pas besoin de construire le nombre B, toutes les opérations avec sont juste des manipulation de tes listes chainé (tronquature, ou rajout de zéro au début).

Ok merci, je comprends mieux