Advertisement Jump to content
Sign in to follow this  
lomateron

Read and write numbers in a bit array

This topic is 1854 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This problem if solved will have huge effects
The problem is this:
*I need to store 4 numbers from 0 to 1000000 in a 128 bit array.
*the default value of the array is whatever value you want
*When writing a value to the array I can know the value I am writing but I can't know the values that are already in the array, for example I start and I write number 2 then I have to write number 7 I cannot know that there is already the number 2 in the array
* when writing a number I can't know that this number was the first,second,third,fourth number being written
*when writing I can +,-,* the value I am writing with the value that already is in the array, the three operations are done in the same way it's done on unsigned int
*then after writing I have to be able to read the 4 numbers

Share this post


Link to post
Share on other sites
Advertisement

Can you know that, taking your example, when you are writing number 7, you know this is the second number you are writing in the array? If so, something like "old number + new number * 2^(32 * index)" treating your array as a 128-bit integer (or four 32-bit integers, really). Then reading back the four numbers is easy.

 

If not, can you be more explicit? Perhaps with a more detailed example? What does "array" mean, is it an array of 128 bits, or a 128-bit unsigned integer, or something else..? Is this a real problem you are encountering, or is it just an academic exercise?

Share this post


Link to post
Share on other sites
Sorry forgot about that, I can't know that the number I am writing is the first, second,third,fourth one.
Yes a 128 bit array so you can create your own way of representing numbers
Every post you see from me here is independent work

Share this post


Link to post
Share on other sites
The first solution I tough was using prime numbers
1=0
2=1
3=2
5=3
7=4
...
...

Then I set the default value of the array to 1, then as I write numbers I first translate them to its prime number and then multiply it with the value that is already in the array
So in the end the value of the array will be a number with unic prime factors
The problem with this solution is that the numbers I want to save go from 1 to 1000000 so 1million transformed into a prime number and then multiplied by other prime numbers will result in a number that will be very slow to transform back into its factors

Share this post


Link to post
Share on other sites

The first solution I tough was using prime numbers
1=0
2=1
3=2
5=3
7=4
...
...

Then I set the default value of the array to 1, then as I write numbers I first translate them to its prime number and then multiply it with the value that is already in the array
So in the end the value of the array will be a number with unic prime factors
The problem with this solution is that the numbers I want to save go from 1 to 1000000 so 1million transformed into a prime number and then multiplied by other prime numbers will result in a number that will be very slow to transform back into its factors

 

So I take it order is not important? For numbers in your range (0 to 10000000) it will not be "very slow" as in "infeasible", but yes it would take a few milliseconds to factor back the integer into its prime factors. And it doesn't scale well at all.

 

On the other hand, if I understand your problem, why can't you just do this?

old value * 2^32 + new value

That works, right? You are only multiplying the old value with a constant, and then adding the new number to it, as per your requirements, and that way every new element gets its very own 32 bits to exist in. Decoding is very easy, just do the reverse operation: take the lower 32 bits, then shift right 32 bits, until you get zero. You even get to keep the order.

Share this post


Link to post
Share on other sites
So the thing is with this way( the solution I just showed) of storing numbers you could save a lot of space, let's see how much:
Damn, I can't make the chart(the AC adapter of my pc just passed away)
The chart will be a 3dimentional graph
One axis will be the number of variables to save, another axis will be the range of the variables and the last axis will be the memory it uses
The only bad thing is that this way of saving numbers don't save the order of the numbers
Can someone do it?(I am in a mobile phone)

Share this post


Link to post
Share on other sites

So the thing is with this way( the solution I just showed) of storing numbers you could save a lot of space, let's see how much:
Damn, I can't make the chart(the AC adapter of my pc just passed away)
The chart will be a 3dimentional graph
One axis will be the number of variables to save, another axis will be the range of the variables and the last axis will be the memory it uses
Can someone do it?(I am in a mobile phone)

 

Firstly, you won't save any memory (in a purely information-theoretical sense) by encoding information into prime factors. People have had the idea before, but it doesn't work - you will still be using the same amount of space to store the product, and decoding such numbers is quite expensive (it seems like it would be a space-time tradeoff, but it isn't). The proof is easy: if it took less space, you would not be able to decode them without loss of information, since that would necessarily mean that at least two sets of numbers, when stored using your scheme, would come out to the same output. Since we know from the properties of primes that this can't happen, the scheme is lossless, and hence no memory is saved. It would be like trying to "encode" a 32-bit integer into a 31-bit one. It works "most of the time", but ultimately it must fail.

 

However I assume you're referring to shaving off some space from e.g. storing numbers from 1 to 100 in a byte, so that there are 157 unused values which wastes space. In your case, the numbers go from 0 to 1000000, and the "naive" method takes 128 bits. Actually, you can get it down to 80 bits with very little effort, by storing the integers on 20 bits, the largest power-of-two integer range which can hold one million and one different values (we'll call this the naive method from now on). Sadly, that still doesn't net you much - because primes grow at a logarithmic rate, your product is still going to be so large that storing it directly always takes up more space than the equivalent naive method. You could, of course, precompute a table which maps all products of 4 primes smaller than the one-millionth prime, to a single natural integer (which would be optimal), and that would save you anywhere from zero to n bits (where n is the number of variables saved) - in your example, you would save around 0.27 bits - but the bad news is: generating such a table is typically infeasible, and storing it is infeasible as well. So you might save a few bits of memory in the space-time tradeoff you suggest, for your specific range of values, but at a very high computational and/or spatial cost. It is in general not a viable compression technique.

 

Aren't we going off-topic though? What is the actual topic of the thread? tongue.png

Share this post


Link to post
Share on other sites
old value * 2^32 + new value

That is a good solution but I really don't know if I can do it to solve the real problem I have because the 128 bit is cut into four 32bit float(I lied just to see more solutions), more exactly
I am using directx 10 and a 2D texture of four 32 bit floats, and when rendering to it I am using the blending operations, and as I described I need to save 4(maybe if it can be done 5) numbers in one pixel, I render individual vertices to random pixels of the texture and every vertice just puts one number to the pixel it's pointing. So various vertices could end writing to the same pixel and I want to save those different values rendered by the vertices(if I save five values and there are six vertices pointing to the same pixel I can forget one value, the order of the values doesn't matters)
I have already solved this problem using 4 draws with stencil test but I just keep thinking if this is possible to solve just by using one draw call

Share this post


Link to post
Share on other sites

If your limit is 1000000, then you can fit that in 20 bits, so you should be able to store 6 values in 128 bits

 

So (in principle) old_value * 2^20 + new_value

 

Just wanted to throw that out there, don't have time to try to figure out how to split that into 4 floats, but it should be possible... (don't know how much of a performance thief it would be though)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!