Discussion :

[TrexXx]

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

[Invité(e)]

Bonjour

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

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.

Quel est le problème ? compiliation, exécution ... ?

[TrexXx]

Ca compile mais à l'exécution ça plante et ça me renvoie une erreur.

[TrexXx]

J'ai vraiment besoin d'aide, si quelqu'un a une idée, je le remercie d'avance. (Le code compile et s'exécute comme il faut, mais le résultat renvoyé n'est pas le bon)

[Invité(e)]

Sans plus de code, cela va être dur...

Les fonctions dont le code n'est pas fournis fonctionnent elles correctement ? ie ont elles bien été testées une à une ?

• ajouterDebut()
• ajouterNombre()
• differenceNombre()
• multiplier10()
• multiplier()
• ...

Est normal que initialiserNombre() ne soit pas utilisé sur tout les Ptr_nombre ?

Peux tu débogger ? commence par faire la multiplication à la main (en supprimant la condition sur la taille) genre 25 * 10 et compare au résultat.

Poste un code minimal qui compile et reproduit le problème.