My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
Dev Dorian is offline  
 
September 1st, 2013, 07:13 AM   #2
Senior Member
 
Joined: Mar 2012
From: Belgium

Posts: 653
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
gelatine1 is offline  
September 1st, 2013, 12:51 PM   #3
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 932

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]
CRGreathouse is offline  
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 .
Dev Dorian is offline  
September 1st, 2013, 08:35 PM   #5
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 932

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.
CRGreathouse is offline  
September 1st, 2013, 10:13 PM   #6
Senior Member
 
Joined: Mar 2012
From: Belgium

Posts: 653
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.
gelatine1 is offline  
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!
Dev Dorian is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
16bit, compacting, data, integer



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modelling Data Help! jimmy_neutron987 Algebra 5 February 18th, 2013 11:52 AM
Data Analysis DataGeek Real Analysis 1 January 25th, 2013 04:04 PM
Rolling 3 months YOY data to Monthly YOY data lumpa Real Analysis 0 October 19th, 2012 08:07 AM
FFT on sample data ramyy Applied Math 1 June 29th, 2009 04:49 PM
How to regress actual data towards projected data. BigLRIP Advanced Statistics 1 May 18th, 2009 10:01 AM





Copyright © 2017 My Math Forum. All rights reserved.