My Math Forum Compacting data into a 16-bit integer

 Computer Science Computer Science Forum

 August 31st, 2013, 11:29 PM #1 Newbie   Joined: Aug 2013 Posts: 3 Thanks: 0 Compacting data into a 16-bit integer I'm a working on a video game where we need to optimize the information we send as network packets. Right now we are using multiple 16 bit packets to send very small values of data which is very inefficient as we want to run as lean as we can over internet. We are not as strong with math as far as making algorithms as we would like. The idea is to take ... Data type 1: 1 to 640 Data type 2: 1 to 480 Data type 3: 1 to 64 ... and combine them into one 16 bit integer using an algorithm (with 65536 combinations). We want to have it where it can be decoded where we can pull three unique values of the different data types out of the one 16 bit integer. Does anyone have any ideas or solutions on how to do this? We would need a way to encode and decode it obviously and how to do this from a programmers standpoint without high-end equation notation. We're sure it's probably quite simple but we can't seem to wrap our heads around it enough and would greatly appreciate your help. Thank you very much for reading.
September 1st, 2013, 07:13 AM   #2
Senior Member

Joined: Mar 2012
From: Belgium

Posts: 654
Thanks: 11

Re: Compacting data into a 16-bit integer

Quote:
 Originally Posted by Dev Dorian The idea is to take ... Data type 1: 1 to 640 Data type 2: 1 to 480 Data type 3: 1 to 64 ... and combine them into one 16 bit integer using an algorithm (with 65536 combinations). We want to have it where it can be decoded where we can pull three unique values of the different data types out of the one 16 bit integer.
There is something wrong with what you want to do. you want to store 3 different numbers in one number and afterwards be able to pull those numbers out again. with the values you gave us we will be able to extract 300 (=640*480*64/65536) different numbers from the same number so that's not really good.
Your data types should get smaller or your integer must get bigger then 16 bit integer

 September 1st, 2013, 12:51 PM #3 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Compacting data into a 16-bit integer You need more than 24 bits to store that much information, 16 bits won't do it. Possible ways out include: Use more bits[/*:m:3qna6jwq] Reduce the sizes of the information you need to store[/*:m:3qna6jwq] Reduce the fidelity of the data (so maybe you wouldn't be able to distinguish 220 and 222)[/*:m:3qna6jwq] Make data retrieval probabilistic, so you might get wrong answers sometimes[/*:m:3qna6jwq] If your data is sparse, use a lookup table and auxiliary memory[/*:m:3qna6jwq]
 September 1st, 2013, 04:51 PM #4 Newbie   Joined: Aug 2013 Posts: 3 Thanks: 0 Re: Compacting data into a 16-bit integer Unfortunately, the worst case we are looking for is just using the two data types and we cannot condense their fidelity as they are coordinates. If they were under 256 it would be as simple as converting both data types to binary, shifting their bits into the 16 bit places and converting back to decimal (which unfortunately we have to do with the software we are using). Example: [color=#BF0000]Data type 1 (0 -255 range): 125 Decimal, (01111101 Binary)[/color] [color=#0000FF]Data type 2 (0 - 255 range): 54 Decimal, (00110110 Binary)[/color] Shuffling the data type 1 bits into the 1st, 3rd, 5th, 7th, 9th, 11th, 13th and 15th digits of the 16-bit integer. Shuffling the data type 2 bits into the 2nd, 4th, 6th, 8th, 10th, 12th, 14th and 16th digit of the 16 bit integer. [color=#BF0000]0[/color] [color=#0000FF]0[/color] [color=#BF0000]1[/color] [color=#0000FF]0[/color] [color=#BF0000]1[/color] [color=#0000FF]1[/color] [color=#BF0000]1[/color] [color=#0000FF]1[/color] [color=#BF0000]1[/color] [color=#0000FF]0[/color] [color=#BF0000]1[/color] [color=#0000FF]1[/color] [color=#BF0000]0[/color] [color=#0000FF]1[/color] [color=#BF0000]1[/color] [color=#0000FF]0[/color] = 763 decimal I'm still confident though that with 65536 combinations of a 16 bit integer there is an algorithm to insert the two data types at 1 to 640 and 1 to 480 ... just might need a cytologist to figure it out. Thank you guys for the input thus far .
September 1st, 2013, 08:35 PM   #5
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Compacting data into a 16-bit integer

Quote:
 Originally Posted by Dev Dorian I'm still confident though that with 65536 combinations of a 16 bit integer there is an algorithm to insert the two data types at 1 to 640 and 1 to 480 ... just might need a cytologist to figure it out.
I have no idea what a cytologist could add here -- do computational biologists (etc.) know something we don't?

But in any case 16 bits is too small to fit the desired data, since 2^26 < 640 * 480.

September 1st, 2013, 10:13 PM   #6
Senior Member

Joined: Mar 2012
From: Belgium

Posts: 654
Thanks: 11

Re: Compacting data into a 16-bit integer

Quote:
 Originally Posted by CRGreathouse But in any case 16 bits is too small to fit the desired data, since 2^16 < 640 * 480.
(note the correction at 2^16 in my quote)

He is completely right. This job can't be done. I will try to illustrate this with an example.

Assume we have only 3 bits (8 combinations). And we want to store 2 data types.
Data type 1: 1-4
Data type 2: 1-3

Similarly this should not be possible since 2^3<3*4

We 'encode' the numbers with a function f(x,y) lets say.
Then we get 12 different 'encryptions'
f(1,1) f(1,2) f(1,3)
f(2,1) f(2,2) f(2,3)
f(3,1) f(3,2) f(3,3)
f(4,1) f(4,2) f(4,3)

In order to decrypt this we need all of those encryptions should be distinct.
Lets say f(1,3)=5 and that f(3,1)=5
This would mean that a computer gets in hes decryption function g(x) He gets two times g(5). He might be able to figure out that x=1 or 3 and y = 3 or 1
But he won't be able to find which one of those he has to use. That's why all the encryptions should be distinct.

Now let's take a look at the 3 bit binary system.

000
001
010
011
100
101
110
111

Let's say they are the solutions of our encryptions then we can do something like this.

000=f(1,1)
001=f(2,1)
010=f(3,1)
011=f(4,1)
100=f(1,2)
101=f(2,2)
110=f(3,2)
111=f(4,2)

Now where would you place f(1,3) f(2,3) f(3,3) and f(4,3) ? nowhere because there is no place left for all values to be distinct.
I hope you understood now why this is not possible. My example was with much lower numbers because I can't start writing 65536 combinations here right ? But it still works the same how big or how small your amount of digits get.

 September 1st, 2013, 11:25 PM #7 Newbie   Joined: Aug 2013 Posts: 3 Thanks: 0 Re: Compacting data into a 16-bit integer Ahhh, point taken. Thank you for taking the time to explain , that was a lot of work. We've decided to use the bit-shuffling idea I explained previously but use a 32 bit integer instead of 16 and convert the data types into 10 and 9 binary digits. And to be honest, that works on so many other levels that it was really easier to decide that than my convoluted idea. You're a scholar and a saint sir and your time is appreciated!

 Tags 16bit, compacting, data, integer

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post jimmy_neutron987 Algebra 5 February 18th, 2013 10:52 AM DataGeek Real Analysis 1 January 25th, 2013 03:04 PM lumpa Real Analysis 0 October 19th, 2012 08:07 AM ramyy Applied Math 1 June 29th, 2009 04:49 PM BigLRIP Advanced Statistics 1 May 18th, 2009 10:01 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top