Need fast solution for large lookup table

[Pacetech]

I've been using Forth since 93, learned on a New Micros HC11 board back in school and as much as I love it, there are a few shortcomings, but not many.

I really like the CASE statement in C, but there is no Forth word that does the same thing that I know of. So instead I would usually do it with a series of nested if thens.

Now I have a large lookup table and I need to map some numbers. I am reading an optical encoder which gives me a value between 0 and 1950. I need to take that number and lookup its output value.

For example lets say I have the following table
EncVal Display Val
0 0
176 1
396 2
617 3
1012 4
1431 5
1950 6

So I read the encoder and find the nearest display value.

In my tables, there is no equatable relationship between the values. And I tried curve fitting up to 10th order polynomial - no dice. Its just wacky numbers.

In my case I really have about 73 rows in the table, instead of the 7 shown. I need the fastest way to search the table for the nearest value. And I need to do it to 4 tables every 20 ms.

[RMDumse]

Many of the Forth community like the Eaker's case statement. It is a compiler tool that manufactures a structured IF-THEN result for you. I think you could find that in our appnotes, we had it for HC11. But I would not think of it for this application. Larger IF-THEN's are not memory or speed efficient.

Do you have the space for a 2K-word table? I would probably consider just compiling a table with the encoder outputs, and index into this large table to pull the resultant value. This approach would use alot of memory, but be very fast.

[Pacetech]

Originally posted by RMDumse
Many of the Forth community like the Eaker's case statement. It is a compiler tool that manufactures a structured IF-THEN result for you. I think you could find that in our appnotes, we had it for HC11. But I would not think of it for this application. Larger IF-THEN's are not memory or speed efficient.

Do you have the space for a 2K-word table? I would probably consider just compiling a table with the encoder outputs, and index into this large table to pull the resultant value. This approach would use alot of memory, but be very fast.

Good idea.

This one is currently running on an ISOPOD-X, but I may use an ISOPODV2 in my final application.

Using
AVAIL ." Available Data RAM = " . CR
PAVAIL ." Program RAM = " . CR
PFAVAIL ." Program Flash = " . CR
EEAVAIL ." Data Flash = " . CR

I get

Available Data RAM = 1448
Program RAM = 396
Program Flash = 8310
Data Flash = 2048

Am I missing some more FLASH? I thought the ISOPOD-X had:
32Kx16 Program Flash
32Kx16 Program Ram
64Kx16 Data Ram

[RMDumse]

The AVAIL words only show internal memory.

The 32K Flash includes the IsoMax(TM) kernel and then your added program.

Looks like you have enough room for the table in either the Data Flash or the Program Flash.

[ngkdc]

I'm using a case statement ... here's what it looks like:


( CASE STATEMENT DEFINITIONS START HERE )

: CASE-ZERO STOP ; EEWORD
: CASE-ONE RUN ; EEWORD
: CASE-TWO CLEAR ; EEWORD
: CASE-THREE RESTART ; EEWORD
: CASE-FOUR ." case statement 4 " ; EEWORD
: CASE-FIVE ." case statement 5 " ; EEWORD
: CASE-SIX ." case statement 6 " ; EEWORD
: CASE-SEVEN ." case statement 7 " ; EEWORD
: CASE-EIGHT ." case statement 8 " ; EEWORD
: CASE-NINE ." case statement 9 " ; EEWORD
: CASE-TEN ." case statement 10 " ; EEWORD
: CASE-ELEVEN ." case statement 11 " ; EEWORD
: CASE-TWELVE ." case statement 12 " ; EEWORD
: CASE-THIRTEEN ." case statement 13 " ; EEWORD
: CASE-FOURTEEN ." case statement 14 " ; EEWORD
: CASE-FIFTEEN ." case statement 15 " ; EEWORD
: CASE-SIXTEEN ." case statement 16 " ; EEWORD
: CASE-SEVENTEEN ." case statement 17 " ; EEWORD
: CASE-EIGHTEEN ." case statement 18 " ; EEWORD

:CASE NUMBR
CASE-ZERO ( 0 )
CASE-ONE ( 1 )
CASE-TWO ( 2 )
CASE-THREE ( 3 )
CASE-FOUR ( 4 )
CASE-FIVE ( 5 )
CASE-SIX ( 6 )
CASE-SEVEN ( 7 )
CASE-EIGHT ( 8 )
CASE-NINE ( 9 )
CASE-TEN ( 10 )
CASE-ELEVEN ( 11 )
CASE-TWELVE ( 12 )
CASE-THIRTEEN ( 13 )
CASE-FOURTEEN ( 14 )
CASE-FIFTEEN ( 15 )
CASE-SIXTEEN ( 16 )
CASE-SEVENTEEN ( 17 )
CASE-EIGHTEEN ( 18 ); EEWORD

( execute CASE statement
( 0 NUMBR
( 1 NUMBR
( ...
( 18 NUMBR



As used above, : CASE-ZERO STOP ; EEWORD
will execute the word "STOP" (defined ahead of this case statement) whenever 0 NUMBR is called. The bulk of the case statements only print the number entered ... early debugging that I left in afterwards ... didn't need all 18 cases after all.


The downfall here, is that if you need to enter all of the possible encoder values with their hardwired output required. If you have 70 possible encoder values, you'll of course need 70 case statements.

What encoder are you using, and what is the output code? You should be able to calculate your desired output directly from encoder values (though some codes, such as GRAY code are encoded to have no more than one bit change per step, as opposed to straight binary which can have multiple bit changes per step).


Randy gave me this way back in the beginning of my FORTH learning curve, and I'm trying to pass along some of what I've received.


Hope this helps,



Rick

[Pacetech]

Hmmm, this is somewhat confusing. It appears that any call of NUMBR will execute all the CASE-XXX words. There must be something missing??

I found a nice CASE? that works

http://forth.sourceforge.net/word/case-q/

: NIP SWAP DROP ; \ Need to add this FORTH word to ISOMAX

: CASE? ( x x -- true )
( x y -- x false )
OVER = DUP IF NIP THEN
;

and is used as follows

: GET-RESPONSE-LENGTH
E0 CASE? IF 04 EXIT THEN
E1 CASE? IF 06 EXIT THEN
E2 CASE? IF FF EXIT THEN
E4 CASE? IF FF EXIT THEN
E5 CASE? IF 04 EXIT THEN
E6 CASE? IF 06 EXIT THEN
E7 CASE? IF FF EXIT THEN
E9 CASE? IF 18 EXIT THEN
EA CASE? IF 18 EXIT THEN
EB CASE? IF 18 EXIT THEN
EC CASE? IF 10 EXIT THEN
EF CASE? IF 04 EXIT THEN
F0 CASE? IF 00 EXIT THEN
F1 CASE? IF 00 EXIT THEN
F3 CASE? IF 04 EXIT THEN
DROP 0
;

[ngkdc]

No, actually calling 3 NUMBR only executes the command in Case 3 ... in this case RESTART word is executed.

However, if you have a working Case statement you don't need to fuss with this one! :)


Regards,

Rick

[Pacetech]

OK, I guess I'm not seeing a definition for :CASE ( edited - found it in ISOMAX)

If you have it, please post it. I'll see if I can at least do a speed comparison between them.