so....
I have a lookup array of 255 integer values
I am reading an ADC input and this is where I'm scratching my head:
how to find the values between which the ADC readin falls?
Sure I could use a 'for' loop to do that but is there a more clever way of going about?
there are different algorithm for this, it depends if the look up values are all over the place or sorted in ascending/descending order for example.
if they are sorted you can use a Dichotomic search for example.
you could also use alternate look-up organization such as b-tree if you want to maximize access time versus memory usage
Some code somewhere is going to have to do the hard work.
You could use a FOR look and work through the array from start to finish and break when you get to the one that is next higher than your test value.
Perhaps you could test for greater or less than the middle value and start at the top or bottom of the array accordingly.
Another option is to start by testing the value in the middle. If it is too high then try the value half-way between the middle and bottom. etc etc. That should get you to the result with fewer tests. Whether, on average, it uses fewer MCU cycles is another matter.
...R
Robin2:
Another option is to start by testing the value in the middle. If it is too high then try the value half-way between the middle and bottom. etc etc. That should get you to the result with fewer tests. Whether, on average, it uses fewer MCU cycles is another matter.
that works if data is in ascending order
Clever way is not to use LUT, but solve equation and calculate a new value for each adc sample by fast & efficient code.
curious if you can find my equation and show me fast and efficient code for this 
J-M-L, Robin2
thank you for your suggestions. I will look into those and see what works best in my case.
The absolute simplest way is if you can map your input values to a run of contiguous integers and just use them as the index into the look-up table.
Delta_G:
The absolute simplest way is if you can map your input values to a run of contiguous integers and just use them as the index into the look-up table.
I thought of that... but would that not mean a bigger lookup table.
input is 0-1023
current lookup table is 255 values
also as I mention in my OP, my aim is to return the 2 values between which the ADC value lie if it not equal to any.
I think there is a lot confusion here.
sherzaad:
also as I mention in my OP, my aim is to return the 2 values between which the ADC value lie if it not equal to any.
Sometimes you want to return two values, other times only one value. You mention when the switch will occur, but how are you handling sometimes getting one value and other times getting two?
This also means the lookup table must be descending or ascending only.
The confusion continues...
sherzaad:
current lookup table is 255 values
How do you only have one set of 255 values? There must be an input value and an output value which means at least 2x 255 values. One of the value must be the return result and the other value the ADC value. It appears your thinking is to make a an array of a structure (or two synchronized arrays) where one aspect is the ADC value and the other the return value. Either way you need 510 values and requires looping until the entry is found that exceeds or equal the input value. At which point you know the return result(s).
To skip the looping, use the input value as the array index and just hand populate the 1024 values of the array.
If a PROGMEM expert can jump in here to confirm or deny they ability to have the array placed in program memory instead of RAM will be of great usefulness.
adwsystems:
The confusion continues…
How do you only have one set of 255 values? There must be an input value and an output value which means at least 2x 255 values.
Not really if the data is sorted, then the index in the array is one of the value. it’s implicit.
say we have only 5 entries and the data is
0 100 300 900 1023
if the reading is 200, then I think OP wants to get that this value is between index 1 and 2
sherzaad:
I thought of that... but would that not mean a bigger lookup table.input is 0-1023
Yes it would.
So what?
J-M-L:
curious if you can find my equation and show me fast and efficient code for this
That depends on how accurately the equation needs to match the data.
J-M-L:
that works if data is in ascending order
Why wouldn't it be?
FantomT:
Clever way is not to use LUT, but solve equation and calculate a new value for each adc sample by fast & efficient code.
Look-up tables are often used because they are fast. I would not assume that applying an equation is faster.
...R
sherzaad:
I thought of that... but would that not mean a bigger lookup table.input is 0-1023
current lookup table is 255 values
also as I mention in my OP, my aim is to return the 2 values between which the ADC value lie if it not equal to any.
Why would you need a larger table? If you have 1023 input values to map to 255 output values then you just divide by four to get the index. 0 through 3 all map to the same result and 4 through 7 all map to the same value etc.
If you want the one that lies one above or one below then just add one or subtract one from said index.
J-M-L:
Not really if the data is sorted, then the index in the array is one of the value. it's implicit.say we have only 5 entries and the data is
0 100 300 900 1023if the reading is
200, then I think OP wants to get that this value is between index 1 and 2
That is correct in this case, my return values would be 100 and 300.
If it reading was 900, then I return value would be 900 and 900
Delta_G:
Why would you need a larger table? If you have 1023 input values to map to 255 output values then you just divide by four to get the index. 0 through 3 all map to the same result and 4 through 7 all map to the same value etc.If you want the one that lies one above or one below then just add one or subtract one from said index.
Interesting concept. I'll have to try it out to see if that actually works reliably for me
tried out this code; seems to be doing alright on a small sample.
void BinarySearch(uint8_t *arr, uint8_t size, uint8_t value, uint8_t *result) {
uint8_t mid, low = 0, high = size - 1;
while (low <= high) {
mid = (low + high) / 2;
if (*(arr + mid) > value) {
high = mid - 1;
*(result + 1) = *(arr + mid);
}
else if (*(arr + mid) < value) {
low = mid + 1;
*result = *(arr + mid);
}
else {
*result = *(arr + mid);
*(result + 1) = *(arr + mid);
break;
}
}
}
void setup() {
// put your setup code here, to run once:
uint8_t arr[10] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
uint8_t result[2];
uint8_t z = 25;
Serial.begin(115200);
BinarySearch(arr, 10, z, result);
Serial.print("result0 = ");
Serial.println(result[0],DEC);
Serial.print("result1 = ");
Serial.println(result[1],DEC);
}
void loop() {
// put your main code here, to run repeatedly:
}
next step the actual data set! 