Bitcoin Forum

This message was too old and has been purged

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?

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

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 (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

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

ruby, just kidding  ;D

This message was too old and has been purged

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

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.

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

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

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:

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

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.

This message was too old and has been purged

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.

Good point! lol  Seems like the only way would be if the dataset follows certain patterns and not literally ANY possible
integer.

Hi all,

While I agree that it _probably_ can't be done, part of me entertains that it possibly can be done.  To me this seems like a basic compression problem.  At first blush, I contemplated using variable length codes organized according to a frequency distribution of the data taken to bits at a time.  This would basically have been huffman encoding where upon evaluating the bit patterns 00,01,10,11 the variable length codes would have looked like 0, 11, 100, 101.  Thus the most frequent bit pattern would be coded as 0, the next most frequent bit pattern 11, and the least frequent bit patterns either 100, or 101.

Unfortunately, this had a best case scenario of 50% compression+the overhead of the frequency table required to map the 2 bit tokens to their variable length equivalents.

The most promising approach in my opinion is dictionary based compression which I believe is the basis of Lempel-Ziv compression.  There however the compression is ultimately limited by the size of the dictionary.

All case however revolve around identifying patterns that allow you to shrink the communicated sample space such that you are counting patterns of data as opposed to individual data items.

MP

There is already a minimal-sized dictionary of the first 2^128 integers: the first 2^128 integers.

Compression feels like it should work because in everyday use, it usually does -- but that's because files generally have patterns, which can be taken advantage of. Compression cannot reduce space taken for some inputs without increasing space taken for others -- it can reduce the minimum required space, but cannot reduce the maximum without restricting the domain.

People have already posted multiple proofs that this cannot be done. The gist is this: there are 2^128 possible sets of 4 integers. If you "compressed" them into 2^64 possible compressed versions, you cannot have a compressed version for every input.

I doubt this is possible. If someone can make it then he/she can sell it for much more.
He is asking for a perfect lose-less compression method which is a holy grail.
Imagine you can do that, you will be able to make 10TB fit in as little as 2 unsigned integers.
The request here is basically a guaranteed 50% or more lose-less compression.
(a philosopher's stone is a better analogy)

Yes, I get your point but you are correct in that compression does "feel" right.  We're ultimately talking storage.  One might say that 11111111 as characters occupies more storage than 255 stored as characters, which is more than FF when stored as characters, yet when stored as bits it occupies less space than all of these.

The function 3x+2y= 14, describes an infinite number of points.  So I don't think it's necessarily about finding ways to represent 4 numbers using 2, but finding for *each* of the 4 numbers a way to represent them using 2 numbers that can be reversed.  When first contemplating the problem I imagined a spiral

R= a+b*theta

Imagine all of the possible integers in question evenly spaced along the spiral as it wraps around.

Every number along the spiral could be reached using just two numbers: a radius and theta.

Perhaps in the end there wouldn't be much savings because of the resolution you'd need to express tiny angles,  but as a thought exercise, it seemed reasonable.

MP

A radius and theta specify INFINITE points. You save as much space as the information you throw away.

You are literally trying to prove that a certain set of integers is a strict subset of itself.

Well, even if the orig challenge is ultimately not possible, at least it spurred a good discussion.  :-D

Here is how to store 2 integers in 1, taken off a site. It's programmed in C.
It can be modified to store 4 as 2. Only problem is that we have to assume that integers are less then 65535.


Another solution:
Let's say I have a function that takes an X and Y coordinate, and returns a longint representing that Point's linear value. I tend to call this linearization of 2d data:
Forgive me if I'm paranoid about order of operations, sometimes other operations are greedier than <<, causing things to shift further than they should.

Why does this work? When might it fail? It's convenient that integers tend to be exactly half the size of longints. What we're doing is casting x to a long, shifting it left until it sits entirely to the left of y, and then doing a union operation (OR) to combine the bits of both.

Let's pretend they're 4-bit numbers being combined into an 8-bit number:
Meanwhile, the reverse:
This sort of approach came into being a long time ago, in environments that needed to squeeze every bit out of their storage or transmission space. If you're not on an embedded system or immediately packing this data for transmission over a network, the practicality of this whole procedure starts to break down really rapidly:

It's way too much work just for boxing a return value that almost always immediately needs to be unboxed and read by the caller. That's kind of like digging a hole and then filling it in.
It greatly reduces your code readability. "What type is returned?" Uh... an int.. and another int... in a long.
It can introduce hard-to-trace bugs down the line. For instance, if you use unsigned types and ignore the sign extension, then later on migrate to a platform that causes those types to go two's complement. If you save off the longint, and try to read it later in another part of your code, you might hit an off-by-one error on the bitshift and spend an hour debugging your function only to find out it's the parameter that's wrong.
If it's so bad, what are the alternatives?

This is why people were asking you about your language. Ideally, if you're in something like C or C++, it'd be best to say
Otherwise, in HLLs like Java, you might wind up with an inner class to achieve the same functionality:

public class Example { public class Point { public int x; public int y; public Point(int x, int y) { this.x=x; this.y=y; } }
In this case, getPosition returns an Example.Point - if you keep using Point often, promote it to a full class of its own. In fact, java.awt has several Point classes already, including Point and Point.Float

Finally, many modern languages now have syntactic sugar for either boxing multiple values into tuples or directly returning multiple values from a function. This is kind of a last resort. In my experience, any time you pretend that data isn't what it is, you wind up with problems down the line. But if your method absolutely must return two numbers that really aren't part of the same data at all, tuples or arrays are the way to go.

The reference for the c++ stdlib tuple can be found at http://www.cplusplus.com/reference/std/tuple/

This message was too old and has been purged

That's because the radius and theta are analogue values. You cannot store every one of those infinite points digitally, even if you use a radius and theta. I'm not ready to commit to saying that this bounty is impossible, but it's beginning to feel like it.

My point is that unless the data stream consists of the entire sample space/list of all possible values, (which in this case, it doesn't) you will never need to be able to store all of those infinite points digitally.  If given 4 numbers, you can identify or create a relationship between those numbers, then you can potentially transmit the relationship as opposed to the data.  In some cases this may be far less data to store or transmit.

For instance, if both sides or rather the encoder and decoder "understood" that the data consisted only of powers of 2, then you could send the data element 256 as 8, a reduction from 9 bits to just 4 (8 bits handles values 0-$FF, $100 is 9 bits, likewise 3 bits handles values 0-$7, 4 bits is required to express the number 8  ). To E-K's point concerning compression, I would propose that this is exactly a compression problem because although your numbers can be in the range of 0-2^32-1, you're only using 4 numbers from that set.  If perfect knowledge existed between encoder and decoder (which of course it doesn't), then you could ultimately express each number using 2 bits: 00, 01, 10, 11

Anyway, I got the spiral idea contemplating nature, spirals, and fractals.  I understand your point about analog vs digital addressing but this problem doesn't have to be solved in terms of ones and zeros.  We can use analogs such as any positive value is 1 and any negative value is 0, or any value greater than or equal to 0.5 is 1 and any value less than 0.5 is 0.  The attribute about the spiral that I like is that the further way from the center you get, the greater the distance between targets which means that you can be "closer" to a target with less resolution in your coordinate system.

I'm not willing to say that this will work, I'm just wondering if we can get around some of the well established limitations by looking at the problem differently and checking to see whether the limitations involved MUST apply to our case.

MP

The set of possible inputs has 2^128 values. You're trying to find a way to map them one-to-one into 2^64 "compressed" representations. This is obviously impossible, so you're trying things that are complicated enough that you can't see why they won't work.

Also, note that neither rxd2's proof by contradiction nor 12648430's reductio ad absurdum depend in any way on the actual method you use to compress the data.  You're trying to fit 40 pounds of manure in a 20 pound sack, failing, and going "Hmm, but what if I filled it with a hose from below..."

This message was too old and has been purged

Each branch takes one bit, so you would need (surprise) 128 bits to specify the final leaf.  (Not an actual surprise :))

I understand the point about the folly of trying to use 2^32 things to represent 2^64 things.  I get that, however the point I come to is that we're not looking for a way to express 2^64 things using 2^32 things.  We are looking for a way to express 4 out of 2^64 things.  If you had a data stream that consisted of 2^64 unique symbols, I agree that there is no way to express that stream using less than 2^64 symbols...

BUT

We have a box of 2^64 symbols, and we are looking for a way to describe 4 of them as independently of the box they came from as we can.  If we can do that, then we ultimately only need 4 symbols.

0 1 2 3 4 5 6 7 8 9 A B C D E F

16 is the size of our box, we select 1, 5, 9 and D.  If we predetermine between the encoder and the decoder that 4x+1 is the magic incantation, then we can "compress" a 4 bit code into a 3 bit code  It doesn't matter that the box holds 16 symbols in total.  What matters is the relationship that is "understood" between encoder and decoder.

Yes, EK has given us numbers that can range from 0 to 2^32-1, but we only have to "store" 4 of them and if he gives us a different 4, we can identify a different relationship.  So I'm not disputing anyone's proof, I just currently remain unconvinced that the proofs presented necessarily describe and apply to *this* problem.

Mind you, that doesn't mean that I have an answer for this challenge... but it does mean that I'll probably have to programmatically explore some ideas before I convince myself that it can't be done.

MP

Your time would be better spent studying basic math. Failing to find an implementation isn't going to teach you any of the things you're missing here.

This message was too old and has been purged

No need to be insulting, I would wager that most here have studied "basic" math.  The fact remains that compression is used and works everyday.  Math is a tool, this is a challenge.  We don't have to compress every number in existence, we only need to find the best way to compress 4.  If they happen to be 4 identical numbers, then the problem is trivial.  The only thing that is ultimately required is to either find or create an exploitable relationship between the numbers.

Perhaps your time would be better spent studying basic history, because history is just as "full" of things that _got_ done as it is of people who made proclamations about what couldn't be done.  Even if *I* can't do it, it still doesn't mean that it can't be done.

Btw, in my first attempt, I already using a modified huffman encoding scheme figured out how to consistently represent 128 bits in about 85.

0, 11, 100, 101

MP

MP, I agree. The mathmeticians are focused on "proofs", but they assume that the proof is correct, which may not
be the case if someone erred creating & checking that proof. And the proof may not apply to this particular situation.

They said we could never land on the moon, but we did!  :-D

Keep thinking outside the box.