# Data structures used for variable length integers

I've just had a thought about multiple precision number (i.e. variable length integers). The naive way to represent numbers is to use an array sized in such a way that the number of required bits can be stored. Example say we dispose of words of size $L$ and we want to store $N \leq 1$ bits, then we need an array of size $$n = \left\lfloor \frac{N+L-1}{L} \right\rfloor$$ Assuming the representation base is $2$, it means that

$$x = \sum_{j=0}^{N-1} x_j 2^{j} = \sum_{j=0}^{n-1}y_j2^{jL}$$

However I see many problems with this representation, from the storage point of view I can make the following example. Say there are two indices $0 \leq j_0 < j_1 \leq N-1$ such that $x_j = 0$ for each $j \in \left\{0,\ldots,j_0-1,j_1 + 1,\ldots, N-1 \right\}$. If $j_1 - j_0+1$ is much less than $N$ many of the $y$ variables would be actually $0$, namely not used which means sparsed. However I observe that under such hypothesis

$$x = \sum_{j=0}^{N-1} x_j 2^{j} = 2^{j_0} \sum_{j=0}^{j_1-j_0} x_{j+j_0}2^j$$

Which implies that naming $m = \left\lfloor \frac{j_1-j_0+L}{L} \right\rfloor$ I would have to use $m$ words instead of $n$, and given my hypothesis I would have $m$ much less than $n$. In conclusion in that specific case I could use a pair $(j_0,\vec{y})$ (offset plus vector) to represent my number. I can generalize this approach probrably to obtain something which is very compact. I don't know about general algorithms, but I can see there's at least the memory benefit.

Are there studies about best ways to represent large numbers in a computer? I'm not aware of such studies and I would like to find out if there are any.

• I think this is similar to floating point number. – aaaaajack Feb 8 '17 at 12:07
• Except that you keep a list (or something else) instead of a single number. – user8469759 Feb 8 '17 at 12:28