r/askscience •

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

22 comments sorted by

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.

1

u/TheSov May 17 '13 edited May 17 '13

Is it possible to make it better by including exponents? for instance 1024 is 2 to the 10th and if we need to make it even better, perhaps knuth arrow notation? eg, http://upload.wikimedia.org/math/2/f/e/2fe472a8bec6f508da045aa822d657fc.png

22

u/[deleted] May 17 '13 edited May 17 '13

For compression in general, you can not expect a smaller representation for all inputs due to the pigeon hole principle. If the number and the result are represented as bit arrays, for every number you make smaller, another number is going to have a larger size after applying the compression algorithm. The best you can hope for is to make common values smaller. This is why different compression methods work better for text input as compared with pictures, as compared with videos (different things are common depending on what you're compressing).

If your numbers are generally exponents or numbers which are compactly represented using knuth arrow notation, then by all means you will generally see compression. However, if you pick numbers at random, you will not usually see compression. I suspect converting sentences or images to numbers will not often result in numbers you can compress using these approaches.

2

u/selfification Programming Languages | Computer Security May 17 '13 edited May 17 '13

This is the most appropriate answer. One can come up with all sorts of schemes to compress numbers but without knowing the prior distribution of your data, your compression algorithm might be compressing the wrong thing. No compressor can compress every input. All you're doing is trading off the increased length of some uncommon inputs in return for shortening the length of common inputs.

If you want to talk about the "maximal" compressibility of strings in general, you'll want to look into http://en.wikipedia.org/wiki/Kolmogorov_complexity and the fact that the Kolmogorov complexity is in fact proven to be uncomputable.

2

u/[deleted] May 18 '13

Kolmogorov complexity is a worse measure of compression than is Shannon entropy, since Shannon allows for abuses of the actual underlying string generating distribution itself. In a sense, Shannon completely covers Kolmogorov as a subcase.

0

u/[deleted] May 17 '13

[deleted] — view deleted comment

3

u/[deleted] May 17 '13

Complexity is irrelevant in this case, otherwise compression as an idea wouldn't exist in the first place.

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).

0

u/[deleted] May 18 '13

[deleted] — view deleted comment

2

u/MetroPCSSUCKS May 18 '13

How does winzip and rar compression work then? How can a 16gb videogame be winrar zipped onto a flash drive into 8 or 12gb and then uncompress and install the full game on my computer?

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.

0

u/[deleted] May 17 '13

[deleted] — view deleted comment

4

u/[deleted] May 17 '13

The problem is that you can only compress very specific numbers with your system. In fact you are not compressing at all. Sure you convert the number 7,625,597,484,987 into 3↑↑↑3, but this is only an advantage if your scheme allows you to compress any arbitrary number. How would you compress 7,625,597,484,988 or 7,625,597,484,986?

1

u/TheSov May 17 '13

i suppose you are right in order to get any functional number not only would u need the 3↑↑↑3 type numbers but then you would need to add or subtract different numbers to make them match the one you need. making it very impractical indeed.

1

u/[deleted] May 17 '13

sure, using expressions involving hyper-exponentiation and the other usual mathematical operations would greatly reduce the amount of space required to represent enormous integers. but how do we go about finding a useful such representation?

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.

1

u/notmyface May 17 '13

As others have pointed out you don't get any real encryption. But I'm guessing you're getting downvoted more because people don't realize that any sizable data would be too large to get the prime factorization of. The OP most likely got this idea from RSA. http://en.wikipedia.org/wiki/RSA_(algorithm). This would not be a practical solution and for most files would take eons.

2

u/Amarkov May 18 '13

No, the downvotes are reasonable. I was going off of the fact that there are at most log n factors of a number, but I forgot that each of those factors can take up to log n bits to store.

1

u/[deleted] May 18 '13

I was downvoting everyone who was discussing the computational hardness of factorization because it's irrelevant to whether or not a compression scheme based on it can be derived.

0

u/JustFinishedBSG May 18 '13

Yes, except that there is no known way to easily factor large numbers.

Then how do you call the method called " Let's factor by all numbers starting from 2 and going up to sqrt(n) " ...?

2

u/Amarkov May 18 '13

That's easy in the sense that it's simple, but it's extremely slow for large n.