Replacing large lookup table with switch statement

Question

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.

Answer 1

2¹⁴ 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.

Answer 2

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 2¹⁴ 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.