BigInt memory usage

[Jay Norwood]

I haven't looked at the std implementation, but I liked this guy's package in c++ .  He uses strings to hold the data, but you choose how the string packs the digits, with one of the choices being base 256 for the most efficient storage.    It might be a nice fit for a D port.

http://www.hvks.com/Numerical/arbitrary_precision.html

bearophile Wrote:

> On a 32 bit system this program has allocates about 100 MB of RAM:
> 
> 
> import std.bigint;
> int main() {
>     static assert(BigInt.sizeof == 12);
>     auto data = new BigInt[2_000_000];
>     foreach (i; 0 .. data.length)
>         data[i] = BigInt("9223372036854775808123");
> 
>     int count;
>     foreach (i; 0 .. 2_000_000_000) { count++; }
>     return count;
> }
> 
> 
> 
> It means about 50 bytes/biginteger.
> 
> Every zero BigInt struct needs 12 bytes inside the 'data' array.
> 
> The represented numeral requires about 73 bits, this means 3 words (with lot of wasted space):
> 
> >>> l = 9223372036854775808123
> >>> from math import log
> >>> log(l, 2)
> 72.965784284662092
> 
> 
> Using so much memory allows to store less numbers, and makes them slower too (I have hit both problems). Do you know why D BigInts use so much memory?
> 
> Bye,
> bearophile