Comment GMP stocke ses entiers, sur un nombre arbitraire d'octets?

Question

2^64 est encore loin de la « infini » mon RAM/disque dur peut gérer ...

D'abord, je me demande comment GMP fonctionne avec de la mémoire/processeur, car il fait une sorte de ... Optimisations ombre

Je me demandais aussi s'il y avait un moyen de stocker un nombre entier (non signé, c'est plus facile) sur un nombre arbitraire d'octets. Par exemple, sur 50 octets, j'aurais un plafond de 2^400 -1. La chose à faire est de bien travailler avec les carry pour garder le nombre cohérent d'un octet à l'autre, j'en ai une idée, mais je ne suis pas vraiment sûr que ce soit le moyen le plus rapide de le faire. Je ne suis même pas sûr si j'ai raison. Je suppose que GMP utilise ce genre de façon de stocker ses données, mais je veux juste quelques explications (ou même peu) ou une transmission à une théorie (je n'ai pas de doctorat, alors ne sois pas difficile). GMP alloue dynamiquement de l'espace pour représenter les nombres (et les réaffecte quand il a besoin de croître)

Answer 1

Ceci est décrit en détail dans Integer Internals, in the GMP manual, il décrit comment il découpe la représentation en "membres" et stocke les membres dans un tableau.

La description du terme « membres » vient de GMP Basics: Nomenclature and Types:

Un membre signifie la partie d'un certain nombre multi-précision qui tient dans un seul mot. (Nous avons choisi ce mot parce qu'un membre du corps humain est analogue à un chiffre, seulement plus grand, et contenant plusieurs chiffres.) Normalement, un membre contient 32 ou 64 bits. Le type de données C pour un membre est mp_limb_t.

Ainsi, représentant un nombre de GMP fonctionne en regroupant un certain nombre de membres ensemble pour représenter l'amplitude de l'entier, stockée avec un bit de signe (le bit de signe est à double proposait pour stocker le nombre de membres).

Qu'est-ce que cela signifie pour vous? Eh bien, normalement un int64 est représenté en 64 bits. Terminé. Si vous en regroupez plusieurs, vous pouvez augmenter considérablement cela. Mettez-en deux ensemble, 2^64 * 2^64 ou 2^128. Ajoutez deux autres membres et vous obtenez 2^256. C'est beaucoup de chiffres, stockés en 4 mots (plus les frais généraux de représentation).

Bien sûr, la représentation des flottants est plus compliquée (see here), stockant la représentation en utilisant une mantisse (composée d'un signe et d'une magnitude) et un exposant.