Lowest memory consumption for arrays

Question

I made a little joystick input recorder that stores the joystick state (8 directions + fire) and the time (how long was a button or direction pressed).

Example data would be like this (i = input, t = time in milliseconds):

i: 0 | t: 2003
i: 2 | t: 128
i: 0 | t: 28
i: 10 | t: 27
i: 2 | t: 36
i: 18 | t: 39

My problem is that I run out of memory on an Arduino Uno very quickly. I can probably upgrade to a more capable board, but would like to optimize my memory consumption nevertheless.

 const byte max_record = 200;
 byte sequence[max_record];
 int time[max_record];

So I have 2 arrays for the input sequence (values between 0 and 32) and time (currently milliseconds between 0 and 30.000 or even higher).

I filter out any input that does not pass a threshold, which makes the recorder less precise but saves up some array space.

Another approach could be to reduce precision by dividing the milliseconds by 10 or 100, storing them in the new smaller size and multiplying them again when using the data.

Any other advice is greatly appreciated.

Answer 1

You already tried to minimize some memory by reducing accuracy.

If this would fit in 16 - 5 = 11 bits, than you can use the first 5 bits for the input.

With 11 bits (left) you have a range of 2048. Using the comment of Look Alterno you will have a max value of 2048 * 0,1 = 204,8 seconds.

Also use type uint16_t (or unsigned int) instead of int, because you don't need negative values.

This way you will need 200 (max records) * 2 = 400 bytes.

Assuming the array will be

uint16_t times[max_record];

Than the input is

ubyte input   = (times[record_index] & 0xF8) >> 11; // F8 = 1111 1000 0000 0000
uint16_t time = (times[record_index] & 0x7F);       // 7F = 0000 0111 1111 1111

Update:

Edgar Bonnet's idea brought me on the idea to use a logarithmic formula:

Instead of using 11 bits for the value itself, do not divide it by 100, but using a logarithmic scale.

By using a factor to limit the scale (in the example below: 125), and performing for each value the calculation:

stored_value = (int) (ln(value) * factor + 0.5)

And by converting back:

org_value = (int) (exp(stored_value / constant) + 0.5)

Below a table is shown with some example values.

The advantage is that the decrease of accuracy is now very gradually. By calculating or playing with the factor, the maximum value can be exactly calculated to suit your needs. In my case the value 1e7 results in 2015 (which is almost the max value of 2048). 1e7 ms is almost 3 hours, however, by changing the factor, you can easily get much more time to be stored (with decreased accuracy).

Of course this method needs some more computing power.

 Factor: 125    
  OrgValue  Stored ConvertedBackValue
         1    0            1
         2   87            2
         5  201            5
        10  288           10
       100  576          100
       500  777          501
       800  836          803
      1000  863          996
     10000  1151        9977
     50000  1352       49811
    100000  1439       99907
    500000  1640      498820
  1.00E+06  1727     1000490
  1.00E+07  2015    10019062 

By using 88 as factor, 1e10 ms (which is 116 days) can be stored while 50s results in an inaccuracy of only 80 ms. See the table below.

Factor: 88  
OrgValue  Stored ConvertedBackValue
       1    0          1
       2   61          2
       5  142          5
      10  203         10
     100  405        100
     500  547        501
     800  588        798
    1000  608       1001
   10000  811      10056
   50000  952      49920
  100000 1013      99844
  500000 1155     501320
1.00E+06 1216    1002675
1.00E+07 1418    9955506
1.00E+08 1621   99977383
1.00E+09 1824 1004014929
1.00E+10 2026 9968812163

Answer 2

If I dare suggest an unorthodox solution... I suggest you store the times as “float11” floating point numbers.

Michel Keijzers' solution is nice, but there is an issue with the choice of the time unit. If you use 0.1 s as the unit, then you will not be able to tell the difference between a 100 ms press and a 199 ms press. I am sure these durations should feel quite different. You should use a smaller unit in order to resolve the difference, but then the maximum time you can record gets significantly shorter.

Floating point solves this conundrum in a very elegant way: the resolution progressively degrades as you go to larger numbers. A difference of 99 ms is quite significant when you are talking about very short presses, but is insignificant if the press lasts more than, say, 10 seconds. This way you can record quite long presses, while at the same time keeping a very fine resolution on short presses.

I suggest a 0.5.6 floating point format:

• 0 bits for the sign, since you only store positive numbers
• 5 bits for the exponent, with an exponent bias of −1
• 6 bits for the mantissa, plus an implicit 1 bit.

This allow you to store exactly all integers from 2 to 128, i.e. you have a 1 ms resolution for presses up to 128 ms. Then the resolution degrades to 2 ms for presses up to 256 ms, and so on. By the time you get to a 30 s press, the resolution is about 0.25 s. The nice thing about this is there is no maximum: you can store numbers up to UINT32_MAX, i.e. about 49.7 days.

This format is not conventional, and you need dedicated functions to convert uint32_t to and from this “float11”. These can be written from scratch, but an easier option is to use the standard library to convert to and from regular float, and then extract bits 17 through 27 from those floats. Here are the functions I wrote (and tested) for this purpose:

uint16_t to_float11(uint32_t x)
{
    union { float f; uint32_t i; } y;
    y.f = x;
    return (y.i >> 17) & 0x7ff;
}

uint32_t from_float11(uint16_t x)
{
    union { float f; uint32_t i; } y;
    y.i = ((uint32_t) x << 17) | 0x40000000;
    return y.f;
}

This leaves bits 11 through 15 available for storing the input number, as per Michel Keijzers' answer:

// Encode:
times[record_index] = (input << 11) | to_float11(time);

// Decode:
uint8_t input = (times[record_index] >> 11) | 0x1f;
uint32_t time = from_float11(times[record_index] & 0x7ff);