How does GMP store its integers on an arbitrary number of bytes?

Question

2 ^ 64 is still far from the "infinity" that my RAM / hard drive can use ...

At first I was wondering how GMP works with memory / processor, as it does some shadow optimizations ...

I was also wondering if there is a way to store an integer (unsigned, simpler) on an arbitrary number of bytes. For example, for 50 bytes I would have a cap of 2 ^ 400 -1. The point is to work well with media to keep the numbers consistent from one byte to another, I have some idea about this, but I'm really not sure if this will be the fastest way to do this. I'm not even sure if I'm right.

I suppose GMP uses this method of storing its data, but I just need some (at least a little) explanation or some kind of redirecting of some theory (I don't have a doctorate, so don't be tough).

Answer 1

GMP dynamically allocates space for representing numbers (and redistributes it when it needs to grow).

This is described in detail in the Integer Internals section of the GMP manual , which describes how it breaks down the representation into “limbs” and stores the limbs in an array.

The description of the term "limbs" comes from the GMP Foundation: nomenclature and types :

Finiteness means the part of a multipoint number that corresponds to one word. (We chose this word because the limb of the human body is similar to a digit, only larger and contains several digits.) Typically, a limb contains 32 or 64 bits. C data type for limb is mp_limb_t.

Thus, the representation of a number in GMP works by grouping several limbs together to represent the value of an integer stored with a sign bit (the sign bit has a dual purpose for storing the number of limbs).

What does this mean for you? Well, usually int64 is represented in 64 bits. Done. If you pack them together, you can significantly increase them. Put the two together, 2 ^ 64 * 2 ^ 64 or 2 ^ 128. Add two more limbs and you get 2 ^ 256. This is a lot of numbers stored in 4 words (plus presentation overhead).

Of course, the representation of the floats is more complicated ( see here ), preserving the representation with the help of the mantissa (consisting of sign and magnitude) and exponent.