Discussion :

[PsychoH13]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

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
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 :

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

[PsychoH13]

Personne ? Même pas une petite suggestion??

[souviron34]

si

si tu veux faire un programme C portable (compatible avec tous les compilos) pas de déclarations au milieu du code (uniquement accepté par C99, et pas par tous les compilos supportant C99)..

donc pas de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
......
        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))
        {

Sinon pour ton pbe, connaît pas trop...

[PsychoH13]

En l'occurrence, je m'en fous un peu d'éviter du C99 pour qu'il soit portable parce que de toutes façons je suis obligé d'utiliser le C99 avec le type "long long".

[DaZumba]

Tu as regarde les bibliotheques existantes (bignum, GMP) ? Cela te donnera une piste, car je trouve ton systeme terriblement complique.
De plus, dans ta fonction de division, caster un unsigned long long en unsigned int me parait un peu perilleux. Egalement, si tu fais une bibliotheque, elle ne devrait pas envoyer des messages (qui devraient d'ailleurs etre sur stderr) mais renvoyer un code d'erreur. A l'utilisateur de prendre les mesures qui conviennent. Enfin, on n'insulte pas l'utilisateur.

[PsychoH13]

Euh l'insulte contre l'utilisateur n'a pas vocation à rester ici, et pour l'instant je préfère l'affichage en console directement pour déboguer plus rapidement.

[DaZumba]

je préfère l'affichage en console directement pour déboguer plus rapidement.

Alors tu reserves les problemes pour plus tard Car decider de ce que dois renvoyer PSYIntegerSingleDigitDivide() en cas de division par 0, ce n'est pas facile. Renvoyer 0 est une assez mauvaise solution...

[PsychoH13]

De toutes façons, ça n' apas vocation à rester en C... Quand j'aurais fini, si un jour j'ai fini , je passerai tout en Objective-C/Cocoa avec la gestion des exceptions pour les erreurs... Je pense qu'il y a déjà bien assez de bibliothèques de grands entiers en C .

[scr]

Pourquoi ne pas travailler en base 10 ou du moins une base multiple de 10 ?
Il me semble que cela permettrait d'obtenir chaque partie à afficher sans avoir à diviser le nombre complet ???

[PsychoH13]

Pourquoi ne pas travailler en base 10 ou du moins une base multiple de 10 ?
Il me semble que cela permettrait d'obtenir chaque partie à afficher sans avoir à diviser le nombre complet ???

Certes, certes, l'ennuie c'est que je veux aussi pouvoir éventuellement l'afficher dans d'autres bases, et que pour les calculs le fait d'utiliser la même base que l'ordinateur les facilite énormément...

[c-candide]

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).

Ce temps me semble honorable vu qu'avec la bibliothèque gmp, cela necessite environ 7 secondes (avec affichage dans un fichier du résultat) sur mon PC (sempron 1,3 GHz, 256 Mo ram). En deux mots, c'est quoi ton algorithme de calcul de factorielle ?

[acx01b]

salut

j'ai bien aimé l'idée de diviser le nombre par un milliard pour pouvoir ensuite utiliser l'opérateur % du processeur pour transformer le nombre en base 10 (par l'intermédiaire du sprintf), et c'est le genre de fonction qui peuvent être grandement optimisées par les proc 64 bits (au lieu de diviser par 1 milliard du divises par 1 milliard de milliard)
ça aurait plus élégant de recoder un sprintf (et plus rapide)

ta fonction d'affichage me semble quand même un peu compliquée (en nombre de lignes)

a+

[PsychoH13]

Ce temps me semble honorable vu qu'avec la bibliothèque gmp, cela necessite environ 7 secondes (avec affichage dans un fichier du résultat) sur mon PC (sempron 1,3 GHz, 256 Mo ram). En deux mots, c'est quoi ton algorithme de calcul de factorielle ?

Malheureusement... Le calcul du factoriel met 40 secondes, mais l'affichage de ce nombre est beaucoup plus long... 10 à 12 minutes environ, et encore ce 10 à 12 minutes ne concernent que la conversion du nombre en base 10.

salut

j'ai bien aimé l'idée de diviser le nombre par un milliard pour pouvoir ensuite utiliser l'opérateur % du processeur pour transformer le nombre en base 10 (par l'intermédiaire du sprintf), et c'est le genre de fonction qui peuvent être grandement optimisées par les proc 64 bits (au lieu de diviser par 1 milliard du divises par 1 milliard de milliard)
ça aurait plus élégant de recoder un sprintf (et plus rapide)

ta fonction d'affichage me semble quand même un peu compliquée (en nombre de lignes)

a+

J'avais pensé aussi à diviser le nombre par 10*000*000*000*000*000*000 (10 milliards de milliards) c'est-à-dire la plus grande puissance de 10 avec des entiers sur 64 bits... Le problème c'est que j'utilise ce type pour pouvoir contenir les subdivisions de mon nombre, alors il faudrait que je vérifie mes divisions pour voir si les 64 bits sont utilisés, mais à priori oui puisque à chaque tour de boucle je fais un "r <<= 32;" donc ça empiète forcément sur le reste des bits...

J'ai par ailleurs essayé d'étudier les réécritures des fonctions printf() de GMP, mais c'est encore plus compliqué que la mienne et je m'y perds complètement...



Mise à part ça, pour répondre à c-candide, mon calcul de factoriel utilise l'algorithme de swing, voici d'où il vient : http://www.luschny.de/math/factorial/index.html .
Il utilise un crible d'Ératosthène, et j'ai tout passé en C pur, avec, pour le crible, un type opaque servant d'itérateur, le crible étant une variable static, et pour économiser de la place j'ai fait un crible binaire, chaque entier est représenté par un bit, 1 s'il est premier, 0 s'il ne l'est pas :

PSYSieve.h :

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
#ifndef PSYSIEVE_H_
#define PSYSIEVE_H_
 
//***********************
// PSYSieve
//***********************
 
int PSYSieveCreateWithLimit(unsigned lim);
int PSYSieveSetLimit(unsigned lim);
size_t PSYSieveGetLimit(void);
void PSYSieveRelease(void);
void PSYSieveGeneratePrimes(void);
void PSYSieveRemoveMultiples(unsigned base);
unsigned PSYSieveNextPrime(unsigned currentPrime);
unsigned PSYSievePreviousPrime(unsigned currentPrime);
void PSYSievePrintPrimes(void);
size_t PSYSieveNumberOfPrimes(void);
size_t PSYSieveNumberOfPrimesBetween(unsigned start, unsigned end);
unsigned long long PSYSieveGetPrimorialBetween(unsigned start, unsigned end);
 
//***********************
// PSYSieveEnumerator
//***********************
 
typedef struct _PSYSieveEnumerator *PSYSieveEnumRef;
 
PSYSieveEnumRef PSYSieveEnumCreate(unsigned start, unsigned end);
void PSYSieveEnumFree(PSYSieveEnumRef enumerator);
void PSYSieveEnumRewind(PSYSieveEnumRef enumerator);
unsigned PSYSieveEnumGetMin(PSYSieveEnumRef enumerator);
unsigned PSYSieveEnumGetMax(PSYSieveEnumRef enumerator);
unsigned PSYSieveEnumGetFirstPrime(PSYSieveEnumRef enumerator);
unsigned PSYSieveEnumGetLastPrime(PSYSieveEnumRef enumerator);
unsigned PSYSieveEnumGetNextPrime(PSYSieveEnumRef enumerator);
unsigned PSYSieveEnumGetCurrentPrime(PSYSieveEnumRef enumerator);
int PSYSieveEnumEnded(PSYSieveEnumRef enumerator);
unsigned PSYSieveEnumGetNumberOfPrimes(PSYSieveEnumRef enumerator);
 
#endif

Et voici le code en lui-même, assez conséquent pour le peu qu'il a à faire :

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
typedef unsigned char uchar;
typedef struct _PSYSieve
{
    size_t capacity;
    unsigned char *primes;
    unsigned limit;
} PSYSieve;
 
static PSYSieve *sieve = NULL;
static int created = 0;
 
int PSYSieveCreateWithLimit(unsigned lim)
{
    if(created == 0)
        return PSYSieveSetLimit(lim);
 
    printf("\n- Error : Already Created -\n");
    return 0;
}
 
size_t PSYSieveGetLimit(void)
{
    return sieve->limit;
}
 
int PSYSieveSetLimit(unsigned lim)
{
    if(lim < 3)
        lim = 3;
 
    if(lim > 20000000)
        lim = 20000000;
 
    if(sieve == NULL)
    {
        sieve = malloc(sizeof(PSYSieve));
        sieve->capacity = 0;
        sieve->primes = NULL;
        created = 1;
    }
 
    if(sieve == NULL)
        return 0;
 
    sieve->limit = lim;
 
    if(sieve->primes == NULL)
    {
        sieve->capacity = lim / 8 + 1;
        sieve->primes = malloc(sieve->capacity);
 
        if(sieve->primes == NULL)
        {
            free(sieve);
            created = 0;
            return 0;
        }
    }
    else if(sieve->capacity != (lim / 8 + 1))
    {
        sieve->capacity = lim / 8 + 1;
        uchar * temp;
        temp = realloc(sieve->primes, sieve->capacity);
        if(temp != NULL)
            sieve->primes = temp;
        else
            return -1;
    }
 
    for(unsigned i = 0; i < sieve->capacity; i++)
        sieve->primes[i] = 0xFF;
 
    sieve->primes[0] &= ~0x03;
 
    PSYSieveGeneratePrimes();
 
    return 1;
}
 
void PSYSieveRelease(void)
{
    if (sieve != NULL)
    {
        if(sieve->primes != NULL)
            free(sieve->primes);
 
        free(sieve);
        created = 0;
    }
    else
        printf("\n- Error : Nothing was previously Created -\n");
}
 
void PSYSieveGeneratePrimes(void)
{
    unsigned currPrime = 2;
 
    while((currPrime * currPrime) <= sieve->limit)
    {
        PSYSieveRemoveMultiples(currPrime);
        currPrime = PSYSieveNextPrime(currPrime);
    }
}
 
unsigned PSYSieveNextPrime(unsigned currentPrime)
{
    unsigned i;
 
    for(i = currentPrime + 1; i <= sieve->limit; i++)
    {
        size_t bloc = i / 8;
        size_t bit = i % 8;
        if(sieve->primes[bloc] & (0x01 << bit))
            break;
    }
 
    return i;
}
 
unsigned PSYSievePreviousPrime(unsigned currentPrime)
{
    unsigned i;
    for(i = currentPrime - 1; i > 2; i--)
    {
        size_t bloc = i / 8;
        size_t bit = i % 8;
        if(sieve->primes[bloc] & (0x01 << bit))
            break;
    }
 
    return i;
}
 
void PSYSieveRemoveMultiples(unsigned base)
{
    unsigned i;
    for(i = base + base; i <= sieve->limit; i += base)
    {
        size_t bloc = i / 8;
        size_t bit = i % 8;
        sieve->primes[bloc] &= ~(0x01 << bit);
    }
}
 
void PSYSievePrintPrimes(void)
{
    for(unsigned i = 0, j = 0; i <= sieve->limit; i++)
    {
        size_t bloc = i / 8;
        size_t bit = i % 8;
        if(sieve->primes[bloc] & (0x01 << bit))
        {
            if(j != 0 && j % 10 == 0)
                printf("\n");
            j++;
            printf("%u, ", i);
        }
    }
 
    printf("\n");
}
 
size_t PSYSieveNumberOfPrimes(void)
{
    unsigned temp = 0;
    for(unsigned i = 0; i <= sieve->limit; i++)
    {
        size_t bloc = i / 8;
        size_t bit = i % 8;
        if(sieve->primes[bloc] & (0x01 << bit))
            temp++;
    }
 
    return temp;
}
 
size_t PSYSieveNumberOfPrimesBetween(unsigned start, unsigned end)
{
    unsigned temp = 0;
 
    if(end > sieve->limit)
        end = sieve->limit;
 
    if(start > end)
        start = end;
 
    for(unsigned i = start; i <= end; i++)
    {
        size_t bloc = i / 8;
        size_t bit = i % 8;
        if(sieve->primes[bloc] & (0x01 << bit))
            temp++;
    }
 
    return temp;
}
 
unsigned long long PSYSieveGetPrimorialBetween(unsigned start, unsigned end)
{
    unsigned long long temp = 1;
 
    if(end > sieve->limit)
        end = sieve->limit;
 
    if(start > end)
        start = end;
 
    for(unsigned i = start; i <= end; i++)
    {
        size_t bloc = i / 8;
        size_t bit = i % 8;
        if(sieve->primes[bloc] & (0x01 << bit))
            temp *= i;
    }
 
    return temp;
}
 
//***********************
// PSYSieveEnumerator
//***********************
 
typedef struct _PSYSieveEnumerator
{
    unsigned firstPrime;
    unsigned lastPrime;
    unsigned min;
    unsigned max;
    unsigned current;
    _Bool started;
} PSYSieveEnumerator;
 
PSYSieveEnumRef PSYSieveEnumCreate(unsigned start, unsigned end)
{
    PSYSieveEnumRef new = malloc(sizeof(PSYSieveEnumerator));
    if(new != NULL)
    {
        new->min = start;
        new->max = end;
        new->firstPrime = PSYSieveNextPrime(start - 1);
        new->lastPrime = PSYSievePreviousPrime(end + 1);
 
        new->current = new->firstPrime;
        new->started = false;
    }
 
    return new;
}
 
void PSYSieveEnumFree(PSYSieveEnumRef enumerator)
{
    free(enumerator);
}
 
void PSYSieveEnumRewind(PSYSieveEnumRef enumerator)
{
    enumerator->started = false;
    enumerator->current = enumerator->firstPrime;
}
 
unsigned PSYSieveEnumGetMin(PSYSieveEnumRef enumerator)
{
    return enumerator->min;
}
 
unsigned PSYSieveEnumGetMax(PSYSieveEnumRef enumerator)
{
    return enumerator->max;
}
 
unsigned PSYSieveEnumGetFirstPrime(PSYSieveEnumRef enumerator)
{
    return enumerator->firstPrime;
}
 
unsigned PSYSieveEnumGetLastPrime(PSYSieveEnumRef enumerator)
{
    return enumerator->lastPrime;
}
 
unsigned PSYSieveEnumGetNextPrime(PSYSieveEnumRef enumerator)
{
    if(!enumerator->started)
        enumerator->started = true;
    else
        enumerator->current = PSYSieveNextPrime(enumerator->current);
 
    return enumerator->current;
}
 
unsigned PSYSieveEnumGetCurrentPrime(PSYSieveEnumRef enumerator)
{
    return enumerator->current;
}
 
int PSYSieveEnumEnded(PSYSieveEnumRef enumerator)
{
    return enumerator->current == enumerator->lastPrime;
}
 
unsigned PSYSieveEnumGetNumberOfPrimes(PSYSieveEnumRef enumerator)
{
    return PSYSieveNumberOfPrimesBetween(enumerator->min, enumerator->max);
}

EDIT :

J'ai oublié l'algorithme de calcul du factoriel en lui-même :

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
PSYIntegerRef PSYIntegerFactorial(unsigned n)
{
    PSYIntegerRef result;
    if(n < 20)
    {
        result = PSYIntegerCreateInt(1);
        if(n > 1)
        {
            PSYIntegerRef temp = PSYIntegerCreateUnsignedInt(2);
            for(int i = 2; i <= n; i++)
            {
                PSYIntegerMultiplyBy(result, temp);
                PSYIntegerIncrement(temp);
            }
            PSYIntegerFree(temp);
        }
    }
    else
    {
        PSYSieveSetLimit(n);
        result = PSYIntegerRecFactorial(n);
        PSYIntegerScaleBinary(result, n - PSYIntegerBitCount(n));
    }
 
    PSYIntegerNormalize(result);
 
    return result;
}
 
PSYIntegerRef PSYIntegerRecFactorial(unsigned n)
{
    PSYIntegerRef result;
    if(n < 2)
        result = PSYIntegerCreateUnsignedChar(1);
    else
    {
        result = PSYIntegerRecFactorial(n/2);
        PSYIntegerSquare(result);
 
        PSYIntegerRef swing = PSYIntegerSwing(n);
 
        PSYIntegerMultiplyBy(result, swing);
 
        PSYIntegerFree(swing);
    }
 
    return result;
}
 
static int PSYIntegerBitCount(unsigned valeur)
{
    int count = 0;
    while(valeur != 0)
    {
        count += valeur & 0x1;
        valeur >>= 1;
    }
 
    return count;
}
 
static void PSYIntegerScaleBinary(PSYIntegerRef integer, unsigned scale)
{
    PSYIntegerRef temp = PSYIntegerCreateUnsignedLong(10);
 
    PSYIntegerLeftSwitchBy(temp, scale);
 
    PSYIntegerMultiplyBy(integer, temp);
    PSYIntegerFree(temp);
}
 
static PSYIntegerRef PSYIntegerSwing(unsigned n)
{
    PSYIntegerRef result;
    if(n < 33)
        result = PSYIntegerCreateUnsignedInt(smallOddSwing[n]);
    else
    {
        unsigned rootN = (unsigned)floor(sqrt(n));
        PSYSieveEnumRef Penum0 = PSYSieveEnumCreate(3, rootN);
        PSYSieveEnumRef Penum1 = PSYSieveEnumCreate(rootN + 1, n / 3);
        unsigned piN = PSYSieveEnumGetNumberOfPrimes(Penum0) + PSYSieveEnumGetNumberOfPrimes(Penum1);
 
        unsigned *primeList = malloc(sizeof(unsigned) * piN);
        unsigned count = 0;
 
 
 
        while(!PSYSieveEnumEnded(Penum0))
        {
            int q = n, p = 1;
            unsigned prime = PSYSieveEnumGetNextPrime(Penum0);
 
            while ((q /= prime) > 0)
                if((q & 1) == 1)
                    p *= prime;
 
            if(p > 1)
            {
                primeList[count] = p;
                count++;
            }
        }
 
        while(!PSYSieveEnumEnded(Penum1))
        {
            unsigned prime = PSYSieveEnumGetNextPrime(Penum1);
 
            if(((n / prime) & 1) == 1)
            {
                primeList[count] = prime;
                count++;
            }
        }
 
        result = PSYIntegerCreateUnsignedLong(PSYSieveGetPrimorialBetween(n / 2 + 1, n));
 
        PSYIntegerMultiplyByDigitList(result, primeList, count);
    }
 
    return result;
}

[scr]

ca parrait bizarre qu'il faille plus de temps pour afficher le resultat que pour effectuer le calcul en lui même.

n'y a t'il pas de problème avec la fonction PSYIntegerNormalize() ?

sinon tu peux peut être gagner quelques pouillemes en remplacant datas[i] par un pointeur dans la fonction PSYIntegerSingleDigitDivide

[PsychoH13]

Non PSYIntegerNormalize() est très rapide, elle consiste juste à réduire l'attribut "length" de l'entier pour ne pas compter les chiffres égaux à zéro à gauche du nombre. Donc il commence à la fin du nombre et doit faire 3 ou 4 itération maximum.

Le problème vient bel et bien de PSYIntegerSingleDigitDivide(), car on doit circuler dans tout le nombre pour pouvoir le diviser entièrement, le problème c'est qu'on le fait de très nombreuses fois puisqu'il faut par la même occasion diviser la totalité du nombre pour le convertir.

Donc une boucle dans une boucle ça fait fffff...

[scr]

Non PSYIntegerNormalize() est très rapide, elle consiste juste à réduire l'attribut "length" de l'entier pour ne pas compter les chiffres égaux à zéro à gauche du nombre. Donc il commence à la fin du nombre et doit faire 3 ou 4 itération maximum.

Pas de realloc ?
Si j'ai bien compris tes valeurs de poid le plus fort sont bien situées en fin de tableau ?

Le problème vient bel et bien de PSYIntegerSingleDigitDivide(), car on doit circuler dans tout le nombre pour pouvoir le diviser entièrement, le problème c'est qu'on le fait de très nombreuses fois puisqu'il faut par la même occasion diviser la totalité du nombre pour le convertir.

Donc une boucle dans une boucle ça fait fffff...

Certes, certes ...
Mais il me semble que c'est le même principe que pour le calcul du factoriel.
La multiplication est remplacée par une division mais dans le cas du factoriel, ta premiere boucle tourne sur un nombre plus important d'occurence que dans le cas de l'affichage.

[PsychoH13]

Pas de realloc ?

Non pas de realloc()
Si des cases sont en trop elles sont conservées mais pas comptées par l'attribut length, elles restent en revanche comptées par l'attribut capacity.

Voilà ma normalisation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
void PSYIntegerNormalize(PSYIntegerRef integer)
{
    while(integer->length > 0 && integer->datas[integer->length - 1] == 0)
        integer->length--;
 
    if(integer->length == 0)
    {
        integer->length = 1;
        integer->negative = false;
    }
}

Si j'ai bien compris tes valeurs de poid le plus fort sont bien situées en fin de tableau ?

Exactement.

Certes, certes ...
Mais il me semble que c'est le même principe que pour le calcul du factoriel.
La multiplication est remplacée par une division mais dans le cas du factoriel, ta premiere boucle tourne sur un nombre plus important d'occurence que dans le cas de l'affichage.

Le calcul du factoriel est basé sur le même principe mais le nombre d'itération est largement diminué.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

result = PSYIntegerRecFactorial(n/2);

Comme on le voit à cet appel qui est fait dans la fonction PSYIntegerRecFactorial() (algorithme récursif), on a donc à chaque itération un nombre 2 fois plus petit à traiter.

[scr]

Ok je comprend mieux
Mais je peux malheureusement rien pour toi
Peut être poser ta question sur le forum algorithme