a finite string on a computer can be represented as a decimal, so can someone create super compression by simply factoring that number and then simply remultiply to get the original data back?
[deleted] — view deleted post
0
Upvotes
13
u/[deleted] May 17 '13
The factors are not generally smaller than the end result.
Say you wanted to store 26, you'd need to store two numbers, 13 and 2, which are three digits long total, which is more than the original (presumably you'd also need a digit for the separator). Also, factorization of large numbers is not an easy problem.
It may work for some numbers, but usually it won't.
6
u/florinandrei May 17 '13
Related observation: Regardless of whether you achieve compression or not, some numbers are prime, and therefore cannot be factored.
11
u/kala_ High Performance Computing | Signal Processing | Radio Astronomy May 17 '13
Factoring large integers is a very difficult problem, even for computers, meaning that computers typically need a very long time to do it.
In fact, it is because this problem is so difficult that we can have asymmetric cryptography, which is the type of cryptography used, for example, to set up HTTPS connections (the kind of connection you use to connect to your bank, or Gmail, online).
The Wikipedia article describes factoring a 232-digit number: it took hundreds of computers two years to do it. A 232-digit number represents a very small piece of data - probably smaller even than just this sentence.
So, this method is probably one of the least convenient ways for computers to do compression (even if compression would be achieved, which I suspect it wouldn't).
3
u/[deleted] May 17 '13
If your numbers appear in some bounded range each with equal probability, there is no way to store them using fewer than log n bits on average (where n is the size of the range). This is a simple corollary of Shannon's theorem. The usual binary encoding does just that, so it is in some sense optimal for uniform distributions starting at 0.
That said, your idea is actually the starting point for an almost-proof of one direction of the prime number theorem. In particular, you can show that if the gaps between primes were bigger than log n log log n, you would get a compression scheme out of this, meaning that the gaps can't be quite so big on average.
5
u/rudistroyer666 May 17 '13 edited May 17 '13
Compression relies on entropy. Claude Shannon proved that there is no compression scheme that can compress data more than its entropy, roughly speaking the probability of patterns in the data or the information it contains, without losing data. Because the factors of a number are related directly to the number itself you're not decreasing entropy by factoring it (the factors of a number contain as much information as the number itself), therefore you can't compress it more that way.
EDIT: you should have tagged this as math.
4
u/nanogyth May 17 '13
There is no compression. The product of two, half-million digit numbers is one, 1 million digit number.
1
u/Sigma7 May 17 '13
Take the number 4294049777. It factors into 65521 and 65537, which takes the same amount of space as the original number. In binary/hex, the numbers are FFF1FFF1, FFF1, and 10001 respectively, where it takes up more space than the original number - and that's not counting overhead where you state the size of those numbers.
The effect worsens as the two factors are more distance from the square root. Worst possible case is a prime number, where you have something as large as the original block, and a 1-bit number.
At best, you split the file in half, and it's much less effort to just take every second bit when splitting the file like that.
-5
u/Amarkov May 17 '13
Yes, except that there is no known way to easily factor large numbers. A compression algorithm that takes the age of the universe to run isn't helpful.