# Replacing large lookup table with switch statement

My arduino needs to take a 14-bit number and convert it to a 10-bit number. Can't use a formula for it since the data is quite random. So I created a lookup table with 2^14 elements, each containing a 10-bit value. But it's too big to fit on the arduino. So I thought of using a switch statement instead. Would this result in a significant speed decrease?

Say, for example, that the input value is 16383. How much longer would it take for the arduino to iterate through the 16384 cases compared to accessing index #16383 of an array?

EDIT: This code compiles fine and reports a program memory usage of 1000 bytes.

``````int xval;
int yval;

void setup() {
// put your setup code here, to run once:
}

void loop() {
xval = random(0,16383);
switch (xval) {
case 0:
yval = 0;
break;
case 1:
yval = 4;
break;
case 2:
yval = 4;
break;
case 3:
yval = -60;
...
case 16383:
yval = 1023;
break;
}
}
``````

However, I haven't tried if it really works so maybe the compiler is optimizing away too much.

EDIT 2: Added the line `Serial.println(yval);` so that I'm actually doing something with yval as Majenko commented. And now it doesn't compile :'( :'( :'(

So, I'll tackle my problem in some other way.

• If you don't have room for an array, what makes you think you'll be able to store the same (or more) data in the same space? Commented Mar 15, 2020 at 22:45
• So, if you don't have some kind of formula or algorithm, did you really written 16384 numbers by hand? Normally there is some kind of algorithm, that can also be implemented in the Arduino Commented Mar 15, 2020 at 22:58
• Haha no I didn't write them by hand but I've collected the data through an automated process. Commented Mar 15, 2020 at 23:08
• You say you cannot use a formular. So that means random in and random out? Ok no that case you simply could short the size. If not, you should be able to use a formular. Otherwise it does not make any sense at all. Could you explain more what exactly to try to achieve? What are those 14-bit numbers and how do they relate to the 10-bit output? Commented Mar 16, 2020 at 9:55
• You could store this table in some form of external storage. Something like EEPROM or an SD card. Commented Mar 16, 2020 at 16:20

214 is 16384 entries. Each entry takes 2 bytes. That's 32768 bytes. That's all the flash the ATMega328P has.

The most efficient storage will be an array in flash, and that will take 100% of it. Using a switch will take more space.

So in short: no. Just no. It won't work whatever you try. You need to come up with a radically different storage solution (external flash memory?) or use a larger chip.

As a side note, with "bit packing" you could reduce the storage to 20480 bytes, but doing a lookup of the data within that packed data (4 10-bit entries taking 5 bytes) will be slow to do since you have to work out exactly what combination of bits and bytes you need to reconstruct your 10-bit value.

• I might be able to compress the array in some way. There's a lot of duplicates in the array so the amount of unique values is a lot less than 16384. Commented Mar 15, 2020 at 23:07
• What is it you're doing that needs such a huge lookup table? Commented Mar 15, 2020 at 23:09
• In short, an adapter that reverses some value conversion that takes place in a software. Commented Mar 16, 2020 at 6:58
• How come Arduino compiles the code fine? I tested with the long switch statement of 16384 cases and it says it uses only 1000 bytes. I'll edit my question to include this. Commented Mar 16, 2020 at 7:01
• If you're not actually doing anything with yval the compiler will optimise all that code out. Commented Mar 16, 2020 at 8:52

### Almost certainly not

Compilers often optimise switch statements using jump tables. However the entries in the jump table basically make up a lookup table with 214 entries! So you don't gain anything.

### Some ideas for compression

• You can use bit packing

If your numbers aren't 8 bits in size, you can pack them together. For example, if you have managed to code things in 6 byte chunks, you can squash 4 of these chunks into 3 bytes, to shrink a table by 25% (at the expense of some bit shifts when retrieving entries.)

• Take advantage of frequency of duplicates

You say you have duplicates. But how many "very common" duplicates are there?

If, say, 90% of your values come from a group of 15 possible values, then you can pack 2 entries per byte, each one represented by a value from 0-14. If one of the entries is 15, then that that value is an "exception" and is looked up by binary search in a second table.

This would result in a table of size 8KB plus the size of the other table (say 4KB when you pack the 14 bit index and 10 bit value into 3 bytes.)

If you instead have a set of 254 possible "common" values, then your main table would be more like 16KB. That might be doable.

• Is there any relation between input and output?

Maybe there is no formula, but there might be properties of the input that affect the properties of the output. (For example, maybe most input values 0-1024 have an output that is similar plus or minus 30.)

• Write a program to find patterns in your data

Don't just use your eyes. Write a script (Python?) to count the frequency of each output value, or compare inputs to outputs, or evaluate your suspicions about the data. Graph input vs output.