Topic: This message was too old and has been purged - page 2. (Read 2345 times)

Since apparently GZA and RJD2's explanations of why this is impossible were a bit obtuse for you, here's an additional way to look at it: If you have a way to store any 4 integers into 2 integers, why not do it again? Take 8 integers, put them into 4, put those 4 into 2. Take 16 integers, put them into 8, into 4, into 2... etc. If you can store 4 integers in 2, you can store any even number of integers in 2 integers. You could compress the entire internet into a number less than 18446744073709551616.

This message was too old and has been purged

No you don't, lol. You have 64 bits of storage space. If order doesn't matter, the data to store is an unordered set with repetitions and thus has n-choose-k possibilities, with k=4 and n=2^32+4-1 (multiset coefficient for choosing 4 out of 2^32 possibilities) -- that's more than 2^123. It would take 124 bits to store that many possibilities.

I think I might have a solution but this matters. Where's the OP? We need this question answered (and several others maybe).

You can't fit 256 bits of data into a 128 bit space without losing some precision or assuming something about the data. For instance, if every other bit of the data was static, the integers could be interleaved with a constant or two to maintain the static data. Or, if you don't mind using 32-bit integers as data, you can fit 4 of them into the same space as 64-bit integers, since 32*4 = 64*2 = 128.

In C++ (though you might need a static cast or two to make the compiler happy):

To create the 64-bit array from the 32-bit one:

To restore the array to 4 32-bit integers, use:

As others have said, it is not possible to represent 4 integers using 2 integers, unless there is a known pattern or relationship in the original set (i.e. equally spaced, fit a known function, etc).  I assume the original integers are random numbers.



But AWESOMO does exist:  http://youtu.be/vW-05IZsric

Along the lines of gzaloprgm, here is a detailed mathematical proof of why this is impossible. Note: this proof is valid even if you allow any extra temporary storage, any amount of constants, any extra function and any amount of CPU cycles. In fact, let's take it a step further and prove that not only such a program is impossible, but also no supercomputer/quantum computer/AWESOM-O can do it either.

I am assuming that the problem is: provide a machine (let's call it AWESOMO) that takes as input two 64-bits integers and outputs four 64-bits integers, such that for any array y consisting of four 64-bits integers, there exists an input x of two 64-bits integers such that AWESOMO outputs y when the input is x, i.e. AWESOMO(x) = y.

First let's count how many 4-integers arrays are possible. Each element of the array can be any of the 64-bit integers. So, there are 2^64 = 18446744073709551616 possibilities for each element. Taken together, the number of ways to choose four 64-bits integers is n = (2^64)^4, which is between 10^77 and 10^78. Now, how many ways do we have to choose 2 integers? A similar reasoning gives m = (2^64)^2, which is between 10^38 and 10^39.

Now let's prove that AWESOMO cannot exist. By contradiction. So, assume that AWESOMO exists. Recall (from Wikipedia) that the pigeonhole principle states that "if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item". This is not difficult to see why this is true.

Restating our problem, for each possible output y of AWESOMO, there must exist some input x such that AWESOMO(x)=y. Thus, let's try to associate each possible output (item) to an input (the pigeonhole). Well then, since there are more items (arrays of four 64-bits integers) than pigeonholes (arrays of two 64-bits integers), by the pigeonhole principle, there must exists one pigeonhole, i.e. an array of two 64-bits integers that we will call x1, that is associated to at least two items, i.e. two arrays of four 64-bits integers y1 and y2. In other words, these two outputs y1 and y2 are associated to the input x1. Then what should be the value of AWESOMO(x1)? Either AWESOMO can only return a single value and then AWESOMO(x1) is either y1 or y2, or AWESOMO is allowed to be ambiguous and returns both y1 and y2 when the input is x1. The latter is not possible given our definition of the problem (AWESOMO must output a single 4-integers array). The former contradicts that all possible outputs are covered. This is our contradiction.

--

1rxd2Ts2hRXv6WWpxWyYEmNE9fhVczV1F

Hi,
I think you should clarify a bit  the problem:
1. Do you need to keep the same order of the numbers ? e.g. f(1,2,3,4) and f(4,3,2,1) should be considered different ?
2. Are there limitations of integers ? i.e. any integer from -2^31-1 to 2^31 ? Or only natural numbers ?

Without some sort of limitations the solution is impossible, as all the compression algorithm knows...

Nick

In the OP you said,


Does this mean you want to store 4 32-bit integers as 2 64-bit integers? Or are all the integers 32-bit and you just mentioned 64-bit as something that we can use along the way.

Hey, if these are X and Y = Key... can't you derive X and Y from the key and just store the keys? Or do you actually
need one of either X or Y?  (just thinking out loud here...)

This message was too old and has been purged

ruby, just kidding 

This message was too old and has been purged

The problem is going back from 2 integers to 4... Unless you want a "lossy compression", it is impossible.

Unless the input numbers have a mathematical property, it's imposible to generalize to every integer... Pigeonhole principle means that there would be inputs that map onto the same output.

If some were able to do it, then you would be able to compress any data into half its size, and by repeating the process you would end up with just one integer. Good luck...

This message was too old and has been purged

http://stackoverflow.com/questions/919612/mapping-two-integers-to-one-in-a-unique-and-deterministic-way

This message was too old and has been purged

Are you just looking to reduce storage space? Why not apply the same algorithm to all 4 values?

This may be too simple, but a first start at what I hope to hit...


[3, 6, 9, 12]

can be stored as : 3060912, 2

where the second number is how many spaces the first ones take up. If less than 2 are there, there is a leading 0.

(too simple, I know).


What is the max size of each of the original integers in bits?

This message was too old and has been purged