How to search for value in large list of values

Question

I have a resistance output in my program. Now I want to convert that to temperature. So for that I have a list of resistance vales and it's corresponding temperature and that list has 400 values. I am programming it in Embedded C for my AVR microcontroller.

I was thinking of making a function with for loop but the number of values are very large so it is not a good idea.

I expect that if I give resistance to be 70 ohms then that function or program should check in that list for the temperature at 70 ohms.

`400` is a *small* number, so I would go with the naive linear search. — Eugene Sh., Jul 16 '19 at 18:10
Use an array, not a list. Sort it. Use `bsearch()` if you're lazy or write your own binary search code if this is for a class. — Shawn, Jul 16 '19 at 18:10
I guess you've connected a PT100 sensor. Is it linear? If that's the case, you could use a linear interpolation just by knowing the largest and smallest values and instead of doing a lookup, you can calculate the value. — Pablo, Jul 16 '19 at 18:28

score 2 · Answer 1 · answered Jul 16 '19 at 18:34

I would take the 400 data points you have, drop them into excel/program of your choice, and generate a regression function (likely linear, if it's resistance to temperature).

If you're worried about speed, AVR's sometimes have pipelines for L/S, MUL, and ADD, so it could potentially be faster to calculate it than look it up.

score 1 · Answer 2 · answered Jul 16 '19 at 18:12

1

The best way to do that would probably be with a dictionary, but C does not natively have a dictionary so you would need to implement one yourself. Maybe look here: Quick Way to Implement Dictionary in C

400 is not a lot, however, so even iterating over it should be fine.

answered Jul 16 '19 at 18:12

Zachary Oldham

838
1
5
21

1

Yes, 400 is such a small number that a simple binary search of an array would be faster than calculating the hash function for a dictionary. And use less memory. – Lee Daniel Crocker Jul 16 '19 at 18:20

score 1 · Accepted Answer · answered Jul 16 '19 at 18:23

So you are using a lookup table to convert resistance to temperature. You have a table with 400 entries. You could use a nearest-neighbor algorithm, where you just write a for-loop and look for the table entry with the closest resistance value to the measured resistance, then report the temperature stored in that table entry.

However, you can do much better. If you sort the lookup table by resistance you can use linear interpolation to provide a much more accurate conversion. This means you find the two entries the measured resistance falls between. Then you interpolate (use arithmetic to compute a temperature proportionally between the table entries) between these entries in order to get a more accurate temperature conversion.

Here is an example of linear interpolation in How to build a lookup table in C (SDCC compiler) with linear interpolation.

score 1 · Answer 4 · answered Jul 16 '19 at 18:34

Tables with equidistant x-values are often used in embedded systems.

If your present resistance values (x) for your table are not equidistant, use your desktop computer to calculate/interpolate the temperature values (y) for equidistant resistance values.

Then you can use a simple array of temperature values and calculate the index from the resistance.

Example table, assuming you have a resistance range from 80 to 110 and a corresponding temperature range from 0 to 100.

resistance temperature (corresponding table index)
80         0           0
82         1           1
84         2           2
86         4           3
88         7           4
...        ...
108        99          29
110        100         30

Then you can use an array like this

int temp_table[] = { 0, 1, 2, 4, 7, /* ... */ 99, 100 };

and calculate the temperature like this:

const int rmin = 80;
const int rmax = 110;
int r; /* assuming this is the measures resistance */
int temp;
int index;

if(r < rmin) {
   /* error min */
} else if(r > rmax) {
   /* error max */
} else {
   /* This calculates the table index for the highest resistance value 
      from the table not greater than r.   Check your resistance range
      and factor and divider to  make sure you don't get an overflow here. */
   index = ( (r - rmin) * (sizeof(temp_table) / sizeof(temp_table[0])) ) / (rmax - rmin);
   temp = temp_table(index);
}

If you have less table points, you might want to extend this simple table search with linear (or other) interpolation.

How to search for value in large list of values

4 Answers4