Unique number from two numbers [modified]
-
sorry, i did not mean to use f(x) + f(y) but f(x,y). my mistake. :( so what I want to know is if it is possible to convert 2 numbers into a single unique number so that instead of storing two numbers, I can store just one number. Then afterwards, while reading the stored data, I read one number and apply the inverse of f to get my two numbers x & y. say for eg. Z = 17*x^2 + y^2 for (x,y) = (3,4) Z = 17*9 + 16 = 169 to get x,y from 169, possible values will be x = [1,4,9]; equivalent y will then be = [153, 101, 16] since 16 is the only perfect square, so i get x=3, y=4. I was just wondering about this problem. It's not required in any practical application. So, you can assume that x,y belongs to a set of ALL POSITIVE INTEGERS only. or better 0<x<=y<10000 And order in which inputs are given does not matter. I hope I am clear now.
Yes, but the width of the result will be at least as much as the sum of the widths of the inputs (proof below). Which is why every way to do this will suck in practice. For example you could interleave the bits of the inputs, spreading x to the even bits of the result and y to the odd bits. Or you could (but this sucks) take the product of the x-th and y-th prime numbers. (this is not really a formal proof, but close) Proof that #f(x,y) >= #z+#y Let #x denote the size of x in bits. Assume f(x,y) is unique for every pair x,y and #f(x,y) < #z+#y Then 2^#f(x,y) < 2^(#z+#y) (where ^ denoted exponentiation) Since there are less possible outcomes than there are inputs, at least one output must correspond to multiple inputs. f(x,y) is not unique for at least one pair x,y so the assumption must be false. Therefore #f(x,y) >= #x+#y Instead of bits you could use any other base, just replace the 2 later on.
modified on Saturday, May 15, 2010 11:33 AM
-
sorry, i did not mean to use f(x) + f(y) but f(x,y). my mistake. :( so what I want to know is if it is possible to convert 2 numbers into a single unique number so that instead of storing two numbers, I can store just one number. Then afterwards, while reading the stored data, I read one number and apply the inverse of f to get my two numbers x & y. say for eg. Z = 17*x^2 + y^2 for (x,y) = (3,4) Z = 17*9 + 16 = 169 to get x,y from 169, possible values will be x = [1,4,9]; equivalent y will then be = [153, 101, 16] since 16 is the only perfect square, so i get x=3, y=4. I was just wondering about this problem. It's not required in any practical application. So, you can assume that x,y belongs to a set of ALL POSITIVE INTEGERS only. or better 0<x<=y<10000 And order in which inputs are given does not matter. I hope I am clear now.
No. Both numbers carry an amount of "information", and you need memory ("bits") to store it; as long as there are no restrictions to the values (one number can have a value in some range, and the other can also have an arbitrary value in some range), you need a number of bits to store that information, no matter what reversible transformations you apply; and turning two numbers in one is just a transformation, not necessarily a reversible one. Therefore, assuming a domain of [0, max-1] then
z = x * max + yis as good as it gets. BTW: having one or a few examples of something that seems to provide a valid approach, in general is inconclusive. :)Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
-
No. Both numbers carry an amount of "information", and you need memory ("bits") to store it; as long as there are no restrictions to the values (one number can have a value in some range, and the other can also have an arbitrary value in some range), you need a number of bits to store that information, no matter what reversible transformations you apply; and turning two numbers in one is just a transformation, not necessarily a reversible one. Therefore, assuming a domain of [0, max-1] then
z = x * max + yis as good as it gets. BTW: having one or a few examples of something that seems to provide a valid approach, in general is inconclusive. :)Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
-
But then the answer is yes, right? You can turn two numbers into one in a unique way.. It's just usually useless since you're still using at least as many bits as the input used to be
right, the answer is "yes; and probably no for all practical purposes" BTW: I wonder why, this kind of questions pops up a couple of times each year. Often someone convinces himself he can compress two bytes into one, which is unlikely as if that worked well, one could recurse and stuff the world into a single bit. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
-
No. Both numbers carry an amount of "information", and you need memory ("bits") to store it; as long as there are no restrictions to the values (one number can have a value in some range, and the other can also have an arbitrary value in some range), you need a number of bits to store that information, no matter what reversible transformations you apply; and turning two numbers in one is just a transformation, not necessarily a reversible one. Therefore, assuming a domain of [0, max-1] then
z = x * max + yis as good as it gets. BTW: having one or a few examples of something that seems to provide a valid approach, in general is inconclusive. :)Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
Does that mean that if my range is two 32 bit integers, then I can store them in a 64 bit integer like this //say +ve integeres only. unsigned long long l; unsigned int a = SomeValue; unsigned int b = SomeValue; l = a | (b<<32) and store this l. Then while retrieving, a = l & 0xFFFFFFFF b = (l>>32) & 0xFFFFFFFF That's cool! thinking in terms of bits and informations helps :)
-
Does that mean that if my range is two 32 bit integers, then I can store them in a 64 bit integer like this //say +ve integeres only. unsigned long long l; unsigned int a = SomeValue; unsigned int b = SomeValue; l = a | (b<<32) and store this l. Then while retrieving, a = l & 0xFFFFFFFF b = (l>>32) & 0xFFFFFFFF That's cool! thinking in terms of bits and informations helps :)
-
right, the answer is "yes; and probably no for all practical purposes" BTW: I wonder why, this kind of questions pops up a couple of times each year. Often someone convinces himself he can compress two bytes into one, which is unlikely as if that worked well, one could recurse and stuff the world into a single bit. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
yes, sometimes all we want is to avoid using pair or map and use only an array. Why this question is so common is probably that this kind of situation occurs commonly. For me, it was just that I was solving a common grid problem in which every cell visited has to be marked and I wondered if I can just store a single no. in array to quickly check if that cell is already visited. Just like that as I said before :) Thanks for your answer btw.
Luc Pattyn wrote:
one could recurse and stuff the world into a single bit.
:laugh: funny. i have no such intentions. for me two 16 bit integers [screensize < 65536] into one 32 bit integer is cool enough.
-
yes, sometimes all we want is to avoid using pair or map and use only an array. Why this question is so common is probably that this kind of situation occurs commonly. For me, it was just that I was solving a common grid problem in which every cell visited has to be marked and I wondered if I can just store a single no. in array to quickly check if that cell is already visited. Just like that as I said before :) Thanks for your answer btw.
Luc Pattyn wrote:
one could recurse and stuff the world into a single bit.
:laugh: funny. i have no such intentions. for me two 16 bit integers [screensize < 65536] into one 32 bit integer is cool enough.
-
yes, sometimes all we want is to avoid using pair or map and use only an array. Why this question is so common is probably that this kind of situation occurs commonly. For me, it was just that I was solving a common grid problem in which every cell visited has to be marked and I wondered if I can just store a single no. in array to quickly check if that cell is already visited. Just like that as I said before :) Thanks for your answer btw.
Luc Pattyn wrote:
one could recurse and stuff the world into a single bit.
:laugh: funny. i have no such intentions. for me two 16 bit integers [screensize < 65536] into one 32 bit integer is cool enough.
in graphic or board oriented applications, I often find it useful to use a one-dimensional array rather than a 2D one. That is how a lot of chess games are handled BTW. It saves a lot of code in move generation and the like. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
-
Does that mean that if my range is two 32 bit integers, then I can store them in a 64 bit integer like this //say +ve integeres only. unsigned long long l; unsigned int a = SomeValue; unsigned int b = SomeValue; l = a | (b<<32) and store this l. Then while retrieving, a = l & 0xFFFFFFFF b = (l>>32) & 0xFFFFFFFF That's cool! thinking in terms of bits and informations helps :)
Windows does that itself, it often stores both x and y coordinates in "lParam", the good old 32-bit parameter in Windows messages. Two remarks; 1. If your x and y values are within [ -2^15, 2^15), you could do with a 32-bit signed integer, so no need for "long long". Similar for unsigned. 2. If your app is graphics oriented, you may want to use signed variables; you then must be careful about sign propagation effects in right shifts! :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
-
sorry, i did not mean to use f(x) + f(y) but f(x,y). my mistake. :( so what I want to know is if it is possible to convert 2 numbers into a single unique number so that instead of storing two numbers, I can store just one number. Then afterwards, while reading the stored data, I read one number and apply the inverse of f to get my two numbers x & y. say for eg. Z = 17*x^2 + y^2 for (x,y) = (3,4) Z = 17*9 + 16 = 169 to get x,y from 169, possible values will be x = [1,4,9]; equivalent y will then be = [153, 101, 16] since 16 is the only perfect square, so i get x=3, y=4. I was just wondering about this problem. It's not required in any practical application. So, you can assume that x,y belongs to a set of ALL POSITIVE INTEGERS only. or better 0<x<=y<10000 And order in which inputs are given does not matter. I hope I am clear now.
Oh yes you can. We invented the square root of
-1some time ago just for this... :-DIf the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
Oh yes you can. We invented the square root of
-1some time ago just for this... :-DIf the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]Pallini, help plz plz plz.. it's urgent urgent urgent. my program outputs garbage whenever I try to get the sqrt of -1 using squareroot function in Cmath moreover, plz explain why it's a unique value for every x,y. i feel it's value does not change with change in x & y. :^) Thanks for your inputs btw. :)
-
Pallini, help plz plz plz.. it's urgent urgent urgent. my program outputs garbage whenever I try to get the sqrt of -1 using squareroot function in Cmath moreover, plz explain why it's a unique value for every x,y. i feel it's value does not change with change in x & y. :^) Thanks for your inputs btw. :)
lol Just another way to say: "if you need a pair then use a pair" :-D
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
Does that mean that if my range is two 32 bit integers, then I can store them in a 64 bit integer like this //say +ve integeres only. unsigned long long l; unsigned int a = SomeValue; unsigned int b = SomeValue; l = a | (b<<32) and store this l. Then while retrieving, a = l & 0xFFFFFFFF b = (l>>32) & 0xFFFFFFFF That's cool! thinking in terms of bits and informations helps :)
theCPkid wrote:
Then while retrieving, a = l & 0xFFFFFFFF b = (l>>32) & 0xFFFFFFFF
I would remove the antiaesthetic
& 0xFFFFFFFFstuff. :)If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]