Affichage de grands entiers
Bonjour à tous, voilà je développe depuis quelques temps une "classe" de grands entiers en C, c'est-à-dire un type opaque et des fonctions qui permettent de gérer ce type. Il s'agit d'entier d'une taille pratiquement infinie, avec les opérations arithmétique de bases etc.
J'ai de plus développer un algorithme (avec l'aide d'autres codes) qui permet de calculer de grands factoriels "rapidement" (genre factorielle de 500.000 en 40 secondes).
Mon problème vient de l'affichage de ces très très grands nombres. En effet, je stocke mes nombres dans des structures de ce genre :
Code:
1
2
3
4
5
6
| typedef struct _PSYInteger {
size_t capacity;
size_t length;
bool negative;
unsigned *datas;
} *PSYIntegerRef; |
Sous forme de nombre binaire en base 2^32 et en valeur absolu. Pour afficher mon nombre, je convertis celui-ci de la base 2^32 à la base 1 milliard pour pouvoir afficher 9 chiffres à la fois. Et pour cette conversion j'utilise la division du nombre par 1 milliard, le problème c'est que ça prend beaucoup de temps, la conversion en elle-même prend jusqu'à 11 minutes pour afficher le factoriel de 500.000...
Ce que j'aimerais savoir, c'est si quelqu'un a des optimisations à apporter, ou tout au moins des pistes pour accélérer cette conversion. Merci
Voici mon code de conversion en chaîne de caractères :
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
| char *PSYIntegerToChar(PSYIntegerRef integer)
{
char *result = NULL;
if(PSYIntegerIsNull(integer))
{
result = malloc(2);
strcpy(result, "0");
}
else
{
// Ici je crée une copie du nombre, car la boucle de division supprime ce nombre
PSYIntegerRef a = PSYIntegerCopy(integer);
// Je récupère sa taille et la double pour obtenir la taille d'une table de parties
// Chaque partie représente 9 chiffres du nombre final
size_t totalSize = integer->length * 2, partCount = 0;
unsigned *partTable = malloc(totalSize * sizeof(unsigned));
// C'est cette boucle qui prend beaucoup de temps
while(a->length > 1 || (a->length == 1 && a->datas[0] != 0))
{
// Je divise à chaque tour mon nombre par 1 milliard pour obtenir chacune de ses parties
partTable[partCount] = PSYIntegerSingleDigitDivide(a, 1000000000);
partCount++;
}
// Ici je transforme chaque partie en texte
char tempNumber[10] = "";
result = malloc(partCount * 9 + 1);
llong i = partCount - 1;
sprintf(tempNumber, "%u", partTable[i]);
// J'ai réécris strcpy() pour qu'elle me renvoie le caractère final de la chaîne copiée
char *last = PSYstrcpy(result, tempNumber);
i--;
for(i; i >= 0; i--)
{
// Ici j'utilisais strcat() mais comme j'ai toujours 9 chiffres, je convertis
// chaque partie et l'ajoute à la suite directement
sprintf(last, "%09u", partTable[i]);
last += 9;
}
free(partTable);
char *temp = NULL;
// Ça permet de supprimer les 0 qui sont devant le nombre
temp = strpbrk(result, "123456789");
size_t strSize;
if(temp != result)
{
printf("FUCK !\n");
char *tempResult = strdup(temp);
free(result);
result = tempResult;
}
strSize = strlen(result) + 1;
// Gestion des nombres négatifs, ça ne nous concerne pas ici
if(integer->negative)
{
strSize++;
temp = strdup(result);
result = realloc(result, strSize);
strcpy(result, "-");
strcat(result, temp);
free(temp);
}
// Je libère la copie
PSYIntegerFree(a);
}
return result;
} |
De plus, voici la division que j'utilise, ça correspond à la division d'un chiffre de mes grands nombres, en considérant qu'un chiffre est un unsigned int :
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
| unsigned PSYIntegerSingleDigitDivide(PSYIntegerRef integer, unsigned d)
{
if(d == 0)
{
printf("Error : ZERO DIVISION DUMBASS !\n");
return 0;
}
ullong r = 0;
size_t i = integer->length;
unsigned *datas = integer->datas;
while (i-- > 0)
{
r <<= 32;
r |= datas[i];
datas[i] = (unsigned)(r / d);
r %= d;
}
// Cette fonction permet de réduire l'attribut "length"
// pour que seul les chiffres différent de zéro devant le nombre soit pris en compte
PSYIntegerNormalize(integer);
// Je retourne le reste de la division
return (unsigned)r;
} |
Voilà, donc j'attends vos commentaires, conseils, suggestions, ou insultes au choix...
Merci beaucoup
