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.

• user31481: Human reaction time is > 100ms, so by using byte instead of int you can register a max time of 25.5 seconds (storing time as 0.1 seconds), which is close to 30 seconds, as you wish
• neu-rah: put other data to flash is also an option, if you have not done it yet :D
• Majenko: What are you trying to achieve? It seems you may be thinking in the wrong direction.
• Esshahn: @LookAlterno good advice, although it is not so much about reacting only, but e.g. for repeated button presses (think playing Tekken). So I'm not sure yet how much precision reduction I can afford.
• user31481: @Esshahn. Test yourself how quick can you multi-press the button. Oh, Are you debouncing it?

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

• Esshahn: Some great hints here, thank you Michel, I will look into this approach!
• Michel Keijzers: I would not easy use it for desktop application programming, but for Arduino it is necessary sometimes
• Edgar Bonet: Note that a floating point representation is a decent piecewise linear approximation of the logarithm, and way cheaper to compute than the true logarithm.

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);

• Esshahn: Wow, thank you Edgar for sharing this totally fascinating approach. I need even more time to completely understand this, a great exercise for me.
• Esshahn: btw. in the meantime, I went for a less efficient but quite simple method: I divide the time by 10 (which does not really reduce the resolution) and then split any values >255 into packets of x*255 + the rest, so 620 becomes 255+255+110. By this, very long intervals can be stored as well as the small ones, but I still use only the byte data type for it. Needless to say, I would have never come across this idea without all your valuable input. Very appreciated!
• Michel Keijzers: Nice solution, upvoted!