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

[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

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

[foetus]

@Iradrille Effectivement cela rajoute plus de "multiplications"

Parce que si on passe par des tableaux de unsigned char on peut faire les opérations de base avec des boucles.
[Pour les opérations comme le cos, log, etc... je ne sais pas par contre: peut être des développements de Lagrange ou autre joyeusetés mathématiques ]

Ton exemple n'est pas pertinent: prends un exemple style 1745698234 * 94267185624

Ton exemple 12 -> |1|2| et 7 -> |7|
|1|2|
* |7|
-----

0) Taille du résultat = "un truc sûrement simple du style [nombre de chiffres de op1 + nombre de dizaines de op2 + 1]"
1) 2*7 -> 4 retenue 1
2) 7*1 + retenue
3) Retenue 0 -> Rien à faire

|0|8|4|

Et niveau optimisation des opérations de base, j'avais lu sur Internet que c'était impossible:

• On ne sait pas grouper les opérations.
• On peut sauvegarder certains résultats intermédiaires. Mais il faut savoir lesquels, comment les stocker et quand les réutiliser
• Certains avaient utilisé les maths pour optimiser mais en définitive c'était plus lent

[Iradrille]

Ton exemple n'est pas pertinent: prends un exemple style 1745698234 * 94267185624

Je ne vois pas comment prendre de plus grands nombres rend un exemple pertinent ou non, mais soit.

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
// 1 745 698 234 = 110 1000 0000 1101 0011 1101 1011 1010
// 94 267 185 624 = 1 0101 1111 0010 1100 0011 0001 1001 1101 1000
 
result = 0;
result1 = ((110 1000 0000 1101 0011 1101 1011 1010) * (0)) << 0
result += result1
result2 = ((110 1000 0000 1101 0011 1101 1011 1010) * (0)) << 1
result += result2
result3 = ((110 1000 0000 1101 0011 1101 1011 1010) * (0)) << 2
result += result3
result4 = ((110 1000 0000 1101 0011 1101 1011 1010) * (1)) << 3
result += result4
result5 = ((110 1000 0000 1101 0011 1101 1011 1010) * (1)) << 4
result += result5
....

Quelques soient les nombres, la technique reste la même. Et c'est le même algo qu'une multiplication en base 10 (oui, oui, celui qu'on apprend au CE1 ou CE2).

Mais il y à deux problèmes majeurs à travailler en base 10 : une mauvaise utilisation de la mémoire, utiliser 8 bits par chiffre (cad. 8 bits pour représenter 10 valeurs), alors qu'on peut représenter 256 valeurs avec 8 bits.
Exemple : 94267185624
en base 10, taille = log10(94267185624) = 11 octets (88 bits + 1 bit de signe)
en base 2, taille = log2(94267185624) = 35 bits + 1 bit de signe

Et des problèmes d'optimisations : un CPU fonctionne en base 2, il sera bien plus simple d'optimiser des calculs en base 2, qu'en base 10, sans compter les problèmes qui peuvent arriver avec une plus grande utilisation de mémoire : plus de cache miss, etc...

Niveau optimisation, même sans parler de vectorisation, en base 2 on peut facilement faire des opérations sur 32 bits d'un coup (voir 64 bits pour les additions), alors qu'en base 10 il faudra faire chaque chiffre 1 par 1.
2^32 > 10^9. En base 10 il faudra faire 9 opérations là ou en base 2 on n'en fera qu'une.

Même si il semble y avoir moins d'étapes en base 10, les calculs seront plus long.

[foetus]

Je ne vois pas comment prendre de plus grands nombres rend un exemple pertinent ou non, mais soit.

Code :

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

1
2
// 1 745 698 234 = 110 1000 0000 1101 0011 1101 1011 1010
// 94 267 185 624 = 1 0101 1111 0010 1100 0011 0001 1001 1101 1000

Si c'est pertinent parce que tu ne peux pas coder:

Code :

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

1
2
3
 
long long op1_1 = (94267185624LL * 1745698234LL);
long long op1_2 = 101011111001011000011000110011101100;

Quelques soient les nombres, la technique reste la même. Et c'est le même algo qu'une multiplication en base 10 (oui, oui, celui qu'on apprend au CE1 ou CE2).

Mais il y à deux problèmes majeurs à travailler en base 10 : une mauvaise utilisation de la mémoire, utiliser 8 bits par chiffre (cad. 8 bits pour représenter 10 valeurs), alors qu'on peut représenter 256 valeurs avec 8 bits.
Exemple : 94267185624
en base 10, taille = log10(94267185624) = 11 octets (88 bits + 1 bit de signe)
en base 2, taille = log2(94267185624) = 35 bits + 1 bit de signe

Et des problèmes d'optimisations : un CPU fonctionne en base 2, il sera bien plus simple d'optimiser des calculs en base 2, qu'en base 10, sans compter les problèmes qui peuvent arriver avec une plus grande utilisation de mémoire : plus de cache miss, etc...

Niveau optimisation, même sans parler de vectorisation, en base 2 on peut facilement faire des opérations sur 32 bits d'un coup (voir 64 bits pour les additions), alors qu'en base 10 il faudra faire chaque chiffre 1 par 1.
2^32 > 10^9. En base 10 il faudra faire 9 opérations là ou en base 2 on n'en fera qu'une.

Même si il semble y avoir moins d'étapes en base 10, les calculs seront plus long.

Tout cela on est d'accord mais dans ton code comment tu fais "result += result1"?

Parce qu'avec un std::bitset, tu n'as que des opérations logiques.
Page de ce type

Code :

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

1
2
3
4
5
6
 
XXX result = 0; // XXX -> n'importe quel type
std::bitset<35> result1( std::string("101011111001011000011000110011101100") );
 
result1 <<= 2; // Okay
result += result1; // Not Okay

Édit: Donc en gros, pour utiliser une solution avec le type std::bitset et il faut d'abord faire l'addition pour ensuite faire la multiplication
La solution tableau d'unsigned char est plus facile d'accès

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

[Iradrille]

Tout cela on est d'accord mais dans ton code comment tu fais "result += result1"?

On parlait de multiplication, je partais du principe que l'addition était donc fonctionnelle.
Niveau code, peut être quelque chose du genre

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
struct big_int {
	bool sign;
	std::vector<uint32_t> data;
};
 
big_int operator+(const big_int& lhs, const big_int& rhs) {
	big_int result;
 
	int s = std::max(lhs.data.size(), rhs.data.size());
	++s;
	bool carry = false;
	for(int i=0; i<s; ++i) {
		uint64_t a = (i >= lhs.data.size()) ? 0ull: lhs.data[i];
		uint64_t b = (i >= rhs.data.size()) ? 0ull: rhs.data[i];
 
		uint64_t add = a + b + (carry ? 1ull: 0ull);
 
		carry = add > 0xFFFFFFFF;
		result.data.push_back((uint32_t)(add & 0xFFFFFFFF));
	}
 
	// TODO sign
	return result;
}

(Pas testé, aucune idée de si ça marche avec des nombres négatifs)

[white_tentacle]

(Pas testé, aucune idée de si ça marche avec des nombres négatifs)

Il te manque aussi la gestion du cas où tu as une retenue à la fin. Mais sinon, oui, c’est l’idée.

[foetus]

Intéressant , mais du coup si on revient à mon nombre 94267185624

en base 10, taille = log10(94267185624) = 11 octets (88 bits + 1 bit de signe)
en base 2, taille = log2(94267185624) = 35 bits + 1 bit de signe

Il te faudra alors, pour le stocker, 8 octets (64bits) + 1 signe.
Et les opérations se font sur 64bits, mais potentiellement le CPU devrait aimé.

[Iradrille]

@white_tentacle: c'est pris en compte avec le "++s" (mais il y à un risque d'insérer un 0 inutile dans le vector). Enfin ça reste plus de l'algo que du code utilisable de toute façon.

@foetus: oui, le nombre utilisera 8 octets ici, plus la taille d'un vector + le bit de signe (+ l'alignement), ça peut être amélioré.
Mais sur de très grands nombres l'espace perdu sera minime par rapport à la taille du nombre. Pour réduire cet espace perdu on peu utiliser des entiers sur 8 ou 16 bits (à la place de 32 comme ici), au prix de calculs plus lents.