Discussion :

[marcelin88]

Bonsoir,

J'ai un exercice à faire et j'aimerai le faire de la manière la plus adaptée.
Les int et long long int ayant une limite, il s'agit de créer une classe en utilisant de la mémoire alloué dynamiquement pour représenter et utiliser de très grands entiers (la seule limite sera donc la puissance de l'ordinateur).

Comment feriez vous? Je pense à utiliser des strings, mais j'aimerai connaître votre opinion.

[Bousk]

Salut,

la string est de loin le pire des choix possibles

Perso j'opterais pour des tableaux de long long, et une réimplémentation de tous les opérateurs

[marcelin88]

Intéressant.
C'est à dire en mettant un chiffre par case?
42: t[0]=2, t[1]=4

[Bousk]

Intéressant.
C'est à dire en mettant un chiffre par case?
42: t[0]=2, t[1]=4

Non
Chaque partie du tableau représente une partie du nombre réel

Par exemple, tu choisis le unsigned char comme brique de base, ses valeurs seront 0-255
pour représenter 256 tu auras 255 dans une première case, 1 dans une seconde
après faut aussi prévoir un bit de signe

puis implémenter toutes les opérations

[foetus]

Dans le cadre d’une implémentation réelle, oui. Dans le cadre d’un exercice, pas forcément (si par string on entend « tableau de caractères + longueur). Ça permet d’avoir une visualisation plus « habituelle » des données, et donc aide à comprendre ce qu’il se passe.

Non avec une chaine de caractères ce n'est pas facile:

1. En C++, on a l'impression que c'est un tableau (à cause de l'opérateur []), mais la représentation mémoire peut être lourde. Par exemple en MFC (si je ne me trompe pas ), un string stockait un pointeur de char et un de wchar et utilisait l'un ou l'autre
2. Pour les opérations, à chaque chiffre tu as un décalage de '0' [caractère 0]: cela va devenir lourd
3. Tu peux stocker la valeur réelle, mais attention à l'utilisation parce que un type string n'est pas prévu pour stocker des chiffre/ nombres. Le caractère 9 ou 10 c'est le beeper

Non
Chaque partie du tableau représente une partie du nombre réel

Par exemple, tu choisis le unsigned char comme brique de base, ses valeurs seront 0-255
pour représenter 256 tu auras 255 dans une première case, 1 dans une seconde
après faut aussi prévoir un bit de signe

puis implémenter toutes les opérations

1. Si tu peux découper facilement un int ou un long en morceaux de 256, dans la vraie vie tu vas avoir en entrée soit une chaine de caractère soit un tableau, mais tous deux peuvent dépasser la capacité 4 octects: Bonne chance pour le découpage
2. 256, cela va être pénible parce que tu vas avoir à gérer les débordements: 255 + 1 = 0 et non pas 256
3. Comment tu vas faire la multiplication?

[white_tentacle]

1. Si tu peux découper facilement un int ou un long en morceaux de 256, dans la vraie vie tu vas avoir en entrée soit une chaine de caractère soit un tableau, mais tous deux peuvent dépasser la capacité 4 octects: Bonne chance pour le découpage
2. 256, cela va être pénible parce que tu vas avoir à gérer les débordements: 255 + 1 = 0 et non pas 256
3. Comment tu vas faire la multiplication?

En même temps, si tu n’es pas capable de répondre à ces problèmes là (qui soin loin d’être insurmontables, et sont le principal intérêt de l’exercice), tu ne réussiras jamais à implémenter une gestion de grands nombres correctes, quelqu’en soit la représentation interne.

Comme l’a dit Bousk, la représentation à base de tableau de « mettre ici le type le plus grand pour lequel on a des opérations de base performantes » sera vraisemblablement la meilleure implémentation en terme de rapidité et de compacité mémoire (quoique je me demande si on n’a pas intérêt à utiliser le type de taille inférieure, ce qui permet de faire les opérations dans le type de taille supérieure sans craindre un débordement). Une représentation à base de char décimaux ne pose à vrai dire ni plus ni moins de difficultés (modulo la possibilité d’avoir des valeurs qui n’ont aucun sens, mais ça ça se règle avec des invariants), si ce n’est qu’elle est plus lisible pour l’humain et moins efficace pour la machine.

[Iradrille]

Comment tu vas faire la multiplication?

C'est assez simple : une multiplication n'est rien d'autre qu'une suite d'additions.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// exemple pour 12*7
// 12 = 1 1 0 0
// 7 = 0 1 1 1
 
result = 0;
result1 = ((1 1 0 0) * (1)) << 0
result += result1
result2 = ((1 1 0 0) * (1)) << 1
result += result2
result3 = ((1 1 0 0) * (1)) << 2
result += result3
result4 = ((1 1 0 0) * (0)) << 3
result += result4

Ainsi il n'y à que des multiplication par 1 et 0.
On ne manipule jamais de grands nombres (les multiplication par 1 ou 0 ne sont pas faites).
Les décalages de bits ne sont pas fait non plus de manière "conventionnelle" (avec les opérateurs << ou >>), mais à la main, tout comme les additions qui agissent sur de grands nombres (qui sont faites par packet de 8/16/32/64/128/... bits), on utilise la carry comme entrée supplémentaire pour la prochaine addition.

Ce code n'est pas optimal, il faut compter le nombre de bits à 1 et réécrire la multiplication dans le bon sens : ici on aurait 7*12 car 12 possède moins de bits à 1 que 7.

Ça reste un algo hautement vectorisable, et si une instruction madd (a = b*c+d) est dispo c'est un bon cas d'utilisation.

[white_tentacle]

Salut,

la string est de loin le pire des choix possibles

Dans le cadre d’une implémentation réelle, oui. Dans le cadre d’un exercice, pas forcément (si par string on entend « tableau de caractères + longueur). Ça permet d’avoir une visualisation plus « habituelle » des données, et donc aide à comprendre ce qu’il se passe.

Perso j'opterais pour des tableaux de long long, et une réimplémentation de tous les opérateurs

yep.

[foetus]

Il y a des librairies pour cela: wiki

Comment cela se passe: avec des tableaux de unsigned char (parce qu'en C/ C++ c'est le plus petit)

Exemple: le nombre 2741369578 devient |2|7|4|1|3|6|9|5|7|8|

Pour gérer le signe, il faut passer par une classe

Ensuite c'est simple: multiplication, addition et division c'est comme à l'école
La soustraction c'est dès fois une addition.

Par contre, les calculs flinguent le CPU

[Jean-Marc.Bourguet]

Salut,

la string est de loin le pire des choix possibles

Pas sur, tout depend des criteres. Si l'appli a peu de calcul et beaucoup d'IO, il peut etre sense d'utiliser des string avec un chiffre decimal par caractere (et dans le codage utilise) comme representation.

Perso j'opterais pour des tableaux de long long,

La j'ai du mal a voir les criteres qui en font un bon choix. L'utilisation d'un type non signe dont on est capable de calculer un multiplication sans risque de depassement me semble un meilleur choix. La question ensuite est "est-ce qu'on prend tout l'intervalle ou bien on se limite a la plus grande puissance de 10 qui tient dedans" (et le choix n'est pas si simple, on passe facilement plus de 20% du temps a faire des conversions depuis ou vers du decimal, donc une representation pour laquelle c'est peu couteux est sensee, quitte a perdre un peu de memoire) .

En passant pour la division qui est l'operation la plus compliquee.