-3

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

Cristo
  • 95
  • 1
    With precision of $90~%$, do you mean that the first digit has to be correct? Then you just have to write the number something like $$ x \approx 5 \times 10^{10^{10^{100000}}} $$ as an example. – Matti P. Jan 24 '20 at 13:20
  • base $10^{10000000}$ duh –  Jan 24 '20 at 14:24
  • 1
    Even a $99.9$% precision is no problem, we only need the first few digits and the number of digits. If you mean compressing a huge (random) number to a significant shorter string with which we can recover all the digits - this is not possible in general, we cannot even compress to a string with length $0.99$ of the original length in general. – Peter Jan 24 '20 at 14:26
  • 1
    @MattiP. The question is not about numbers this huge. For numbers with this magnitude, we will have problems to determine the number of digits which would be necessary to reach the desired precision. But I agree the main point that the question is trivial , if it is meant this way. – Peter Jan 24 '20 at 14:30
  • fromdigits(vector(100000,i,i),2^31-1) returns a value with near a million digits –  Jan 24 '20 at 14:30
  • i edited with clarification. – Cristo Jan 24 '20 at 21:58
  • With precision I mean the percentage of numbers that would be correct after applying the formula or whatever to get the 100M digits. Yes, it would be understood as loosy compression. – Cristo Jan 24 '20 at 22:00

1 Answers1

1

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.

gandalf61
  • 15,326