11
$\begingroup$

On a computer I can have integers on arbitrary size thanks to GMP, so it's represented in base 2 in memory.

I'm wondering if it's possible in theory to use less memory if I store only prime factors and their exponent, I think it's worthless for most numbers, but I wonder if it works for a very small minority of numbers with large prime factors.

How can I prove me wrong ?

$\endgroup$
  • 2
    $\begingroup$ I think for some numbers this would definitely use less memory to store them that way. But finding this factorization is costly, and you would need to revert to the usual representation to perform a sum. $\endgroup$ – Joel Cohen Oct 12 '12 at 0:02
  • $\begingroup$ @Joel, for some certainly, but not at all on average. $\endgroup$ – Dan Brumleve Nov 17 '12 at 13:01
20
$\begingroup$

No, it is not possible. In general, there is no algorithm that compresses every $n$ bit string, or reduces the length of a random string of bits (in expectation).

Your algorithm may compress some numbers but then it will use more memory to store others. If your data is random, there is no benefit in using your compression scheme.

Actually the fact that no such compression scheme exists can be used to prove that there are infinitely many prime numbers — otherwise, if there were only finitely many prime numbers your compression scheme would be very efficient!

There are excellent lecture notes on Kolmogorov Complexity by Alexander Shen that discuss “incompressability”; in particular, Shen writes about your compression algorithm in Section 18.

$\endgroup$
  • 1
    $\begingroup$ "Actually the fact that no such compression scheme exists can be used to prove that there are infinitely many prime numbers — otherwise, if there were only finitely many prime numbers your compression scheme would be very efficient!" That is fantastic. $\endgroup$ – crf Nov 15 '12 at 6:51
  • $\begingroup$ Regarding: "Actually the fact that no such compression scheme exists can be used to prove that there are infinitely many prime numbers — otherwise, if there were only finitely many prime numbers your compression scheme would be very efficient!" That is fantastic. Response by hodonkain: That's why it's done in chunks. So the prime number will always have a maximum. $\endgroup$ – user49504 Nov 15 '12 at 10:22
  • $\begingroup$ This answer is okay but I think there is a more subtle and interesting aspect to the question when we consider the error bound. $\endgroup$ – Dan Brumleve Nov 17 '12 at 12:59
1
$\begingroup$

https://www.google.com/patents/US6373986

I've done this too. It is not that hard. The reason it works is because the primes become the character set for a language. Instead of base10 or base2 possible characters describing the result, you end up with prime**prime possible characters and the decompressor/program/language becomes the context in which it is interpreted. You end up with unique values WITHIN THAT SET of prime^prime possible values. While the character may be referenced by other sets or other 'languages', fundamentally as long as the value is not outside the maximum possible value for that set, every single value will uniquely represent some other final value. WITHIN that set. Not extending beyond a value of prime^prime.

$\endgroup$
-2
$\begingroup$

Something which sort of implies that the answer might be yes in some circumstances (I specialize in precision!) is that solving linear equations with large integer coefficients can be done by solving the system modulo a number of primes (or relatively prime values such as $2^n-1$ for appropriate $n$) and combining the results using the Chinese remainder theorem. You have to have enough moduli so the their product is larger than any of the results.

$\endgroup$
  • $\begingroup$ Surely in some circumstances but else what? $\endgroup$ – Dan Brumleve Nov 17 '12 at 13:00

protected by Zev Chonoles Aug 26 '16 at 18:33

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.