Storing a lookup table in EEPROM and looking it up!

Archiver

I would like to store a lookup table in the BS2 EEPROM, which is easy to do.
I want to find the index of a value in the table which is nearest to a vlue
in a variable. What is a good algorithm to use with the BS2?

For example, if the table looks like this:

Index, Value
0, 0
1, 1
2, 2
3, 5
4, 10
5, 20
6, 100

A variable "x" contains the number 8. Looking that up, the algorithm should
return an index of 4, since 10 is the nearest number.

Thanks!
Steve

Archiver

Hi Steve,

If the list is short, like the example with 7 entries, then a
straight numeration would work...

'{$PBASIC 2.5}
' enter with variable X
do until Y>X
read idx,Y
idx=idx+1
loop
' come here with Y>X, idx the index of Y
' the previous value in the table is less than X
' if you want the one that is closest in absolute value, need to do more..
if idx>1 then
read idx-1,Z
if X-Z<Y-X then Y=Z
endif
' come here with the Y= value closest to X.

A short list like that can also easily be handled by a lookdown/lookup command:

lookdown X,>[noparse][[/noparse]0,1,2,5,10,20,100],idx
lookup idx, [noparse][[/noparse]0,1,2,5,10,20,100],Y

but for long tables that eats up a lot of memory, and it cannot be
used for tables that change at run time.

If the table of values is much longer, then a binary search in a DATA
table is the most efficient. You start in the middle of the table and
zero in on your value with a series of greater/less than decisions.
Say the table has 1024 entries, then you get your value with 10
decisions.

-- Tracy


>I would like to store a lookup table in the BS2 EEPROM, which is easy to do.
>I want to find the index of a value in the table which is nearest to a vlue
>in a variable. What is a good algorithm to use with the BS2?
>
>For example, if the table looks like this:
>
>Index, Value
>0, 0
>1, 1
>2, 2
>3, 5
>4, 10
>5, 20
>6, 100
>
>A variable "x" contains the number 8. Looking that up, the algorithm should
>return an index of 4, since 10 is the nearest number.
>
>Thanks!
>Steve