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;
} |
