1 pièce(s) jointe(s)
Implémentation d'une division entre nombres entiers avec une précision arbitraire
Bonjour,
Je suis actuellement en 1ère année de classe préparatoire intégrée dans une école d'ingénieurs en nouvelles technologies. Notre professeur d'informatique, afin de comprendre l'aspect mémoire d'un système à microcontrôleur, nous a donné un projet lié à l'utilisation de pointeurs mémoire. Nous programmons en C++.
Ce projet a pour thème la cryptographie asymétrique et donc repose sur des calculs sur des nombres relativement longs (pouvant aller jusqu'à des milliers de bits sans problème). Pour pouvoir stocker sans trop de problèmes ces grands nombres (considérés comme positifs ou nuls et entiers), nous avons défini un type "lentier" (pour entier long) qui est en fait un pointeur vers une zone mémoire contenant des entiers non signés sur 32 bits. Chaque entier long sera constitué d'un tableau d'entiers sur 32 bits, et donc exprimé en base (232) (nombres pouvant aller de 0 à (232) - 1). La case d'indice 0 sera le poids faible (232)0 et la n-ième case sur laquelle est stocké l'entier long sera de poids (232)n.
Le "lentier" est défini de cette manière :
Code:
typedef unsigned long * lentier;
Le travail est réparti en différents groupes d'étudiants et le mien est chargé de l'interfaçage, c'est-à-dire convertir un grand nombre en base 10 saisi par l'utilisateur avec une chaîne de caractères en un "lentier", c'est à dire un pointeur vers un nombre en base (232) . Nous sommes également chargés de l'opération inverse (convertir un "lentier" en un nombre sous forme d'une chaîne de caractères affichable en base 10).
Cette opération inverse décrite précédemment consiste en fait en des divisions successives par 10 afin de récupérer le reste et de convertir le "lentier" sur un tableau d'entiers de 32 bits en un nombre en base 10. Je rencontre un problème dans mon travail : je suis chargé de programmer une fonction intermédiaire à cette fonction, la division d'un "lentier" par 10, qui retourne à la fois le quotient et le reste (en ayant précisé sur combien de cases mémoire pointe ce "lentier"). J'ai suivi un algorithme de division euclidienne en base quelconque que j'ai adapté à notre cas, et le programme que j'ai conçu en C ne semble pas retourner les bons résultats pour un "lentier" de taille supérieure à 2.
Je vous joins mon code commenté ainsi que l'algorithme de division euclidienne en base quelconque. Dans l'algorithme, le souci se trouve dans mon cas (je pense) à l'étape b) du 3. puisque dans mon cas le diviseur B est de taille inférieure à 2, et dans l'algorithme ce n'est pas le cas.. Mon adaptation à une taille inférieure n'est probablement pas bonne. Je vous laisse en juger par vous mêmes.
En espérant que vous puissiez m'éclaircir à ce sujet, merci d'avance.
Bien cordialement
nb : Cet algorithme fait appel à des fonctions de base codées par d'autres personnes, qui effectuent la multiplication, l'addition et la soustraction de 2 lentier (paramètres : lentier a, lentier b, taille du lentier a, taille du lentier b) que vous voyez apparaître dans le code sous les noms "mult_classique", "add_classique" et "sub_classique".
Code:
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
res_div div_10(lentier a, unsigned int n)
{
//======= LEXIQUE =======
lentier q = (lentier)calloc(n, sizeof(int));
unsigned long r;
unsigned long long op1;
unsigned long long op2;
lentier qit = (lentier)calloc(1, sizeof(int));
lentier brit = (lentier)calloc(n-1, sizeof(int));
lentier op_c;
lentier aux;
res_div res;
//======= ALGO ========
//1 géré avec le calloc
//2
while (a[n - 1] >= 10) //B*r^(n-t) correspond à 10*(2^32)^(n-1) soit un lentier de taille n avec des 0 partout sauf dans la case d'indice n-1 qui contient 10
{
q[n - 1]++;
a[n - 1] -= 10;
}
//3
for (unsigned int i = n - 1; i >= 1; i--)
{
//a
if (a[i] == 10)
{
q[i - 1] = 0xFFFFFFFF; //2^32-1
}
else
{
q[i - 1] = (((unsigned long long)a[i]<<32) + a[i - 1]) / 10; //(a[i]r + a[i-1])/10
}
//b
op1 = q[i - 1] * 10; //Q[i-t] * B[t-1]
op2 =((unsigned long long)a[i]<<32) + a[i - 1]; //A[i]r + A[i-1]
while (op1 > op2) //Comparaison des deux opérandes précédents de taille 2 (max)
{
q[i - 1]--;
op1 = q[i - 1] * 10;
}
//c
qit[0] = q[i - 1];
brit[i - 1] = 10; //Pour la division par 10, B*r^[i-t] = 10*(2^32)^(i-1) soit un lentier avec seulement 10 dans la case d'indice i-1 (sous le nom brit)
op_c = mult_classique(qit, brit, 1, n-1);
if (cmp_lentier(a, op_c, n) != -1) //Si A - Q[i-1]*Br^(i-1) > 0
{
aux = a; //pointeur auxiliaire vers a
a = sub_classique(a, op_c, n, n); //On peut effectuer la soustraction
if (i != n - 1) //Pas de libération pour la 1ère op sur A
{
delete[]aux;
}
}
//d
else //Sinon, A - Q[i-1]*Br^(i-1) <= 0
{
aux = a; //pointeur auxiliaire vers a
a = add_classique(a, brit, n, n-1); //Donc on effectue d'abord l'addition
delete[]aux;
aux = a;
a = sub_classique(a, op_c, n, n); //Puis la soustraction (un unsigned long ne supporte pas de nombres négatifs )
delete[]aux;
q[i - 1]--;
}
brit[i - 1] = 0; //On libère la case mise à 10 pour la prochaine boucle
delete[]op_c; //Libération du lentier pour la prochaine boucle
}
//libérations mémoire
delete[]qit;
delete[]brit;
//4
r = a[0];
//5
res.quotient = q;
res.reste = r;
return res;
} |
