Efficient way to store a fixed range float

Question

I'm heaving an (big) array of floats, each float takes 4 bytes.

Is there a way, given the fact that my floats are ranged between 0 and 255, to store each float in less than 4 bytes?

I can do any amount of computation on the whole array.

I'm using C.

Answer 1

The absolute range of your data doesn't really matter that much, it's the amount of precision you need. If you can get away with e.g. 6 digits of precision, then you only need as much storage as would be required to store the integers from 1-1000000, and that's 20 bits. So, supposing this, what you can do is:

1) Shift your data so that the smallest element has value 0. I.e. subtract a single value from every element. Record this shift.

2) Scale (multiply) your data by a number just large enough so that after truncation to an integer, you will not lose any precision you need.

3) Now this might be tricky unless you can pack your data into convenient 8- or 16-bit units--pack the data into successive unsigned integers. Each one of your data values needs 20 bits in this example, so value 1 takes up the first 20 bits of integer 1, value 2 takes up the remaining 12 bits of integer 1 and the first 8 bits of integer 2, and so on. In this hypothetical case you end up saving ~40%.

4) Now, 'decrypting'. Unpack the values (you have saved the # of bits in each one), un-scale, and un-shift.

So, this will do it, and might be faster and more compact than standard compression algorithms, as they aren't allowed to make assumptions about how much precision you need, but you are.

Answer 2

How much precision do you need?

You can store each float in 2 bytes by representing it as an unsigned short (ranges from 0 to 65,535) and dividing all values by 2^8 when you need the actual value. This is essentially the same as using a fixed point format instead of floating point.

Your precision is limited to 1.0 / (2^8) = 0.00390625 when you do this, however.

Answer 3

For example you could store integers (floats with .0) on one byte, but the other float need more bytes.

You could also use fixed-point if you don't worry about precision...