Bonjour à tous,
J'essaie d'implémenter l'algorithme de Karatsuba, mais (bien sûr !) ça ne marche pas !

Donc voila l'algo en question :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
Ptr_nombre multiplierKaratsuba(Ptr_nombre nombre1, Ptr_nombre nombre2)
{
    Ptr_nombre resultat, nombre1_1, nombre1_2, nombre2_1, nombre2_2;
    Ptr_nombre X, Y, Z, sommeX, sommeY;
    Ptr_element ptrNb1 = nombre1->fin, ptrNb2 = nombre2->fin;
    int i = 0, taille = (max(nombre1->taille, nombre2->taille)) / 2;
 
    if (nombre1->taille <= 100 && nombre2->taille <= 100)
    {
        resultat = multiplier(nombre1, nombre2);
    }
    else
    {
        nombre1_1 = initialiserNombre();
        nombre1_2 = initialiserNombre();
        nombre2_1 = initialiserNombre();
        nombre2_2 = initialiserNombre();
 
        for (i = 0; i < taille; i++)
        {
            if (ptrNb1 != NULL)
            {
                ajouterDebut(&nombre1_2, ptrNb1->chiffre);
                ptrNb1 = ptrNb1->precedent;
            }
 
            if (ptrNb2 != NULL)
            {
                ajouterDebut(&nombre2_2, ptrNb2->chiffre);
                ptrNb2 = ptrNb2->precedent;
            }
        }
 
        while (ptrNb1 != NULL)
        {
            ajouterDebut(&nombre1_1, ptrNb1->chiffre);
            ptrNb1 = ptrNb1->precedent;
        }
 
        if (nombre1_1->debut == NULL)
        {
            ajouterDebut(&nombre1_1, 0);
        }
 
        while (ptrNb2 != NULL)
        {
            ajouterDebut(&nombre2_1, ptrNb2->chiffre);
            ptrNb2 = ptrNb2->precedent;
        }
 
        if (nombre2_1->debut == NULL)
        {
            ajouterDebut(&nombre2_1, 0);
        }
 
        sommeX = ajouterNombre(nombre1_1, nombre1_2);
        sommeY = ajouterNombre(nombre2_1, nombre2_2);
        X = multiplierKaratsuba(nombre1_1, nombre2_1);
        Y = multiplierKaratsuba(nombre1_2, nombre2_2);
        Z = multiplierKaratsuba(sommeX, sommeY);
        Z = differenceNombre(Z, X);
        Z = differenceNombre(Z, Y);
 
        multiplier10(&X, 2*taille);
        multiplier10(&Z, taille);
 
        resultat = ajouterNombre(X, Y);
        resultat = ajouterNombre(resultat, Z);
    }
 
    return resultat;
}
Petites précisions :
Mais nombres sont stockés sous formes de liste chainées. Donc dans un premier temps, je découpe chaque nombre en deux sous paries, et ensuite j'effectue les opérations nécessaires sur ceux ci.

Si quelqu'un voit ce qu'il manque, merci de m'aider