What's an efficient way of representing a big number (up to 100M digits) in a short format.
I'm thinking on possible solutions:
- logs
- factoriadic
- prime numbers base
Would like precision > 80-90%
Would any of that be computable in reasonable time?
For example 13123456! represents almost 100 million digits, but it happens to be the result of that factorial. What would be an aproximated approach for any pseudo-random number or how could I get a formula for general numbers like x = big_prime * n + modulo
It is not really clear what you mean by "precision > 80-90%" but I am assuming this means a precision of $\pm 10 \%$ or better.
If you know that the nearest integer to the logarithm to base $1.2$ of a number is $k$ then you know that number to a precision of about $\pm 10 \%$. This is because its actual logarithm to base $1.2$ could lie between $k-0.5$ and $k+0.5$. Since $1.2^{-0.5} \approx 0.9$ and $1.2^{0.5} \approx 1.1$, so we know that the actual number lies between $0.9\times 2^k$ and $1.1 \times 2^k$.
For example, if you know $k = \left [\log_{1.2} n \right ]= 30$ then you know $n$ lies between $1.2^{29.5} \approx 217$ and $1.2^{30.5} \approx 260$.
If $n$ itself has around $10^8$ digits then defining $k=\left [\log_{1.2}n \right ]$ will require around $12.6 \times 8 \approx 100$ digits. I don't see how you can do better than this if you really require a precision within $\pm 10 \%$, but perhaps I have misunderstood your question.