Binary search on a lookup table for
Archiver
Posts: 46,084
I've posted a question about this previously, but I've changed my program a
bit and now have a new question.
This is on a BS2. I have a lookup table of 199 words, sorted in ascending
order. I have a value that I want to look up in this table. However, this
value may not have an exact match in the table - I want to find the nearest
match, and if there are two adjacent entries that the value is right
between, I don't care which entry is returned. Now, I want the index of the
result, not the value at the location.
Right now, I use a very simple sequential search, which computes a
difference between my value and the table entry. I then keep going through
the table until the difference stops decreasing and starts increasing, then
abort the search.
Binary search would be better, but it's implementation is done with a
recursive function - impossible in the stamp. Does anyone have a pointer to
an implementation that is non-recursive, or to an algorithm that will suit
my needs and is easily implemented on the BS2?
Thanks,
Steve
bit and now have a new question.
This is on a BS2. I have a lookup table of 199 words, sorted in ascending
order. I have a value that I want to look up in this table. However, this
value may not have an exact match in the table - I want to find the nearest
match, and if there are two adjacent entries that the value is right
between, I don't care which entry is returned. Now, I want the index of the
result, not the value at the location.
Right now, I use a very simple sequential search, which computes a
difference between my value and the table entry. I then keep going through
the table until the difference stops decreasing and starts increasing, then
abort the search.
Binary search would be better, but it's implementation is done with a
recursive function - impossible in the stamp. Does anyone have a pointer to
an implementation that is non-recursive, or to an algorithm that will suit
my needs and is easily implemented on the BS2?
Thanks,
Steve
Comments
I do have binary search code, but I'll have to pull it out of a
program that was meant for a different purpose. It is Pbasically the
same algorithm that you find in a successive approximation ADC,
simple and fast.
-- Tracy
>I've posted a question about this previously, but I've changed my program a
>bit and now have a new question.
>
>This is on a BS2. I have a lookup table of 199 words, sorted in ascending
>order. I have a value that I want to look up in this table. However, this
>value may not have an exact match in the table - I want to find the nearest
>match, and if there are two adjacent entries that the value is right
>between, I don't care which entry is returned. Now, I want the index of the
>result, not the value at the location.
>
>Right now, I use a very simple sequential search, which computes a
>difference between my value and the table entry. I then keep going through
>the table until the difference stops decreasing and starts increasing, then
>abort the search.
>
>Binary search would be better, but it's implementation is done with a
>recursive function - impossible in the stamp. Does anyone have a pointer to
>an implementation that is non-recursive, or to an algorithm that will suit
>my needs and is easily implemented on the BS2?
>
>Thanks,
>Steve
operator, except that it searches a table of increasing numbers (word
values) in DATA eeprom. You enter a number at the keyboard, and the
program finds the numbers closest above and below it in the table.
This kind of thing is good for interpolation problems or search for
free memory. The binary algorithm finds the answer in N steps, given
a table with 2^N entries. E.g., a table with 1024 entries is resolved
in 10 steps. Algorithm is like a successive approximation ADC. Uses
a bunch of math tricks in place of IF-THEN or CASE statements.
'{$STAMP BS2}
'{$PBASIC 2.5}
' (c) 2001 Tracy Allen, http://www.emesystems.com
' like lookdown operator, except data in eeprom word table
' word values increasing in table.
' User enters a number. The routine finds the closest two values
' in the table such that wx < number < wy
' and the index pointer to the position of wx in the table
' Uses binary search algorithm for fast acquisition.
' Finds value in a 2^N table in N steps.
' number < smallest value in table returns smallest value
' number > largest value in table returns largest value
value VAR Word ' number entered by user
wx VAR Word ' comparison value from table
wy VAR Word ' binary increment (word for large table)
wz VAR Word ' index into table (word for large table)
sign VAR Bit ' selects up or down for next step in table
tablesize CON 22 ' just for example, 22 entries in DATA table
tablesize1 CON tablesize-1
table DATA Word 2,Word 5,Word 30,Word 35, Word 57, Word 77, Word 99
DATA Word 110, Word 125, Word 278
DATA Word 678, Word 777, Word 888, Word 999
DATA Word 1010, Word 1111, Word 2000, Word 3333
DATA Word 4000, Word 5555, Word 6000, Word 7777
DO
DEBUG CR,CR,"enter a number: "
DEBUGIN DEC5 value ' get user to input a number
index_check0:
wy=DCD NCD tablesize / 2 ' note A
wz=wy-1 ' first address to check, halfway point in the table
index_check1:
READ wz MAX tablesize1 * 2 + table, Word wx ' note B
IF wx=value THEN index_check8 ' note C
sign=wx/(value MIN 1) MAX 1 ' note D
wy=wy/2 ' note E
wz=-sign^wy+sign+wz ' note F
PAUSE 2
' DEBUG CR,DEC wz,TAB, DEC wy,TAB, DEC wx ,TAB,IBIN sign ' show
inner workings
IF wy THEN index_check1 ' note G
index_check8: ' note H
IF value>=wx THEN
READ wz+1 MAX tablesize1 * 2,Word wy
ELSE
wy=wx
READ wz MIN 1 -1 * 2,Word wx
ENDIf
DEBUG CR,">",TAB,DEC wz,TAB,DEC wx,TAB,DEC wy ' note I
LOOP
' note A: could use a constant here if tablesize is a constant
' =largest power of two less than tablesize
' tablesize does not have to be a power of two.
' note B: limit read to last table address, *2 because 2 bytes per word
' note C: speed up process if exact match is found
' note
' position in the table. "value min 1" avoids divide by zero.
' note E: wy is successively lower powers of two
' note F: add (sign=0) or subtract (sign=1) wy from wz
' -sign^wy+sign forms the conditional 2s complement of wy
' note G: continue until wy is reduced to zero
' note H: The IF-THEN-ELSE resolves wx<= value < wy
' wz is the index of wx
' note I: show index and table values below and above user value entered
I'm going to try to incorporate this into my stamp this evening.
Steve
Original Message
From: "Tracy Allen" <tracy@e...>
To: <basicstamps@yahoogroups.com>
Sent: Friday, June 27, 2003 9:52 AM
Subject: Re: [noparse][[/noparse]basicstamps] Binary search on a lookup table for "closest
value"
> Here's a demo program for binary search. It is like the lookdown
> operator, except that it searches a table of increasing numbers (word
> values) in DATA eeprom. You enter a number at the keyboard, and the
> program finds the numbers closest above and below it in the table.
> This kind of thing is good for interpolation problems or search for
> free memory. The binary algorithm finds the answer in N steps, given
> a table with 2^N entries. E.g., a table with 1024 entries is resolved
> in 10 steps. Algorithm is like a successive approximation ADC. Uses
> a bunch of math tricks in place of IF-THEN or CASE statements.
>
> '{$STAMP BS2}
> '{$PBASIC 2.5}
> ' (c) 2001 Tracy Allen, http://www.emesystems.com
> ' like lookdown operator, except data in eeprom word table
> ' word values increasing in table.
> ' User enters a number. The routine finds the closest two values
> ' in the table such that wx < number < wy
> ' and the index pointer to the position of wx in the table
> ' Uses binary search algorithm for fast acquisition.
> ' Finds value in a 2^N table in N steps.
> ' number < smallest value in table returns smallest value
> ' number > largest value in table returns largest value
>
> value VAR Word ' number entered by user
> wx VAR Word ' comparison value from table
> wy VAR Word ' binary increment (word for large table)
> wz VAR Word ' index into table (word for large table)
> sign VAR Bit ' selects up or down for next step in table
>
> tablesize CON 22 ' just for example, 22 entries in DATA table
> tablesize1 CON tablesize-1
>
> table DATA Word 2,Word 5,Word 30,Word 35, Word 57, Word 77, Word 99
> DATA Word 110, Word 125, Word 278
> DATA Word 678, Word 777, Word 888, Word 999
> DATA Word 1010, Word 1111, Word 2000, Word 3333
> DATA Word 4000, Word 5555, Word 6000, Word 7777
>
> DO
> DEBUG CR,CR,"enter a number: "
> DEBUGIN DEC5 value ' get user to input a number
>
> index_check0:
> wy=DCD NCD tablesize / 2 ' note A
> wz=wy-1 ' first address to check, halfway point in the
table
>
> index_check1:
> READ wz MAX tablesize1 * 2 + table, Word wx ' note B
> IF wx=value THEN index_check8 ' note C
> sign=wx/(value MIN 1) MAX 1 ' note D
> wy=wy/2 ' note E
> wz=-sign^wy+sign+wz ' note F
> PAUSE 2
> ' DEBUG CR,DEC wz,TAB, DEC wy,TAB, DEC wx ,TAB,IBIN sign ' show
> inner workings
> IF wy THEN index_check1 ' note G
> index_check8: ' note H
> IF value>=wx THEN
> READ wz+1 MAX tablesize1 * 2,Word wy
> ELSE
> wy=wx
> READ wz MIN 1 -1 * 2,Word wx
> ENDIf
> DEBUG CR,">",TAB,DEC wz,TAB,DEC wx,TAB,DEC wy ' note I
> LOOP
>
> ' note A: could use a constant here if tablesize is a constant
> ' =largest power of two less than tablesize
> ' tablesize does not have to be a power of two.
> ' note B: limit read to last table address, *2 because 2 bytes per word
> ' note C: speed up process if exact match is found
> ' note
> ' position in the table. "value min 1" avoids divide by zero.
> ' note E: wy is successively lower powers of two
> ' note F: add (sign=0) or subtract (sign=1) wy from wz
> ' -sign^wy+sign forms the conditional 2s complement of wy
> ' note G: continue until wy is reduced to zero
> ' note H: The IF-THEN-ELSE resolves wx<= value < wy
> ' wz is the index of wx
> ' note I: show index and table values below and above user value entered
>
>
>
>
> To UNSUBSCRIBE, just send mail to:
> basicstamps-unsubscribe@yahoogroups.com
> from the same email address that you subscribed. Text in the Subject and
Body of the message will be ignored.
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
I've started to implement this in my program, and it does work VERY fast
compared to my initial sequential search.
However, I noticed that "wz" changes in multiples of two. Let me explain:
I noticed that your program will work standalone. Upon initial inspection, I
thought that "wz" would always point to the upper or lower two of the
indexes found, but it does not. For example, the inputs 56, 57, and 76
always set wz at the end of the search to "4", even though the wx and wy
variable are updated to relfect the upper and lower "closest matches".
I then incorperated this into my program with this assumption. I then read
the values at that index, and that index minus 1, check which one is
actually closest, then return that index. However, with the behaviour I
talked about above, this doesn't work properly. Can you offer a suggestion
to correct this?
This will not be a production product, but if I do use your code in the
future with your permission, I will definately give you credit!
Thanks,
Steve Ziuchkovski
Original Message
From: "Tracy Allen" <tracy@e...>
To: <basicstamps@yahoogroups.com>
Sent: Friday, June 27, 2003 9:52 AM
Subject: Re: [noparse][[/noparse]basicstamps] Binary search on a lookup table for "closest
value"
> Here's a demo program for binary search. It is like the lookdown
> operator, except that it searches a table of increasing numbers (word
> values) in DATA eeprom. You enter a number at the keyboard, and the
> program finds the numbers closest above and below it in the table.
> This kind of thing is good for interpolation problems or search for
> free memory. The binary algorithm finds the answer in N steps, given
> a table with 2^N entries. E.g., a table with 1024 entries is resolved
> in 10 steps. Algorithm is like a successive approximation ADC. Uses
> a bunch of math tricks in place of IF-THEN or CASE statements.
>
> '{$STAMP BS2}
> '{$PBASIC 2.5}
> ' (c) 2001 Tracy Allen, http://www.emesystems.com
> ' like lookdown operator, except data in eeprom word table
> ' word values increasing in table.
> ' User enters a number. The routine finds the closest two values
> ' in the table such that wx < number < wy
> ' and the index pointer to the position of wx in the table
> ' Uses binary search algorithm for fast acquisition.
> ' Finds value in a 2^N table in N steps.
> ' number < smallest value in table returns smallest value
> ' number > largest value in table returns largest value
>
> value VAR Word ' number entered by user
> wx VAR Word ' comparison value from table
> wy VAR Word ' binary increment (word for large table)
> wz VAR Word ' index into table (word for large table)
> sign VAR Bit ' selects up or down for next step in table
>
> tablesize CON 22 ' just for example, 22 entries in DATA table
> tablesize1 CON tablesize-1
>
> table DATA Word 2,Word 5,Word 30,Word 35, Word 57, Word 77, Word 99
> DATA Word 110, Word 125, Word 278
> DATA Word 678, Word 777, Word 888, Word 999
> DATA Word 1010, Word 1111, Word 2000, Word 3333
> DATA Word 4000, Word 5555, Word 6000, Word 7777
>
> DO
> DEBUG CR,CR,"enter a number: "
> DEBUGIN DEC5 value ' get user to input a number
>
> index_check0:
> wy=DCD NCD tablesize / 2 ' note A
> wz=wy-1 ' first address to check, halfway point in the
table
>
> index_check1:
> READ wz MAX tablesize1 * 2 + table, Word wx ' note B
> IF wx=value THEN index_check8 ' note C
> sign=wx/(value MIN 1) MAX 1 ' note D
> wy=wy/2 ' note E
> wz=-sign^wy+sign+wz ' note F
> PAUSE 2
> ' DEBUG CR,DEC wz,TAB, DEC wy,TAB, DEC wx ,TAB,IBIN sign ' show
> inner workings
> IF wy THEN index_check1 ' note G
> index_check8: ' note H
> IF value>=wx THEN
> READ wz+1 MAX tablesize1 * 2,Word wy
> ELSE
> wy=wx
> READ wz MIN 1 -1 * 2,Word wx
> ENDIf
> DEBUG CR,">",TAB,DEC wz,TAB,DEC wx,TAB,DEC wy ' note I
> LOOP
>
> ' note A: could use a constant here if tablesize is a constant
> ' =largest power of two less than tablesize
> ' tablesize does not have to be a power of two.
> ' note B: limit read to last table address, *2 because 2 bytes per word
> ' note C: speed up process if exact match is found
> ' note
> ' position in the table. "value min 1" avoids divide by zero.
> ' note E: wy is successively lower powers of two
> ' note F: add (sign=0) or subtract (sign=1) wy from wz
> ' -sign^wy+sign forms the conditional 2s complement of wy
> ' note G: continue until wy is reduced to zero
> ' note H: The IF-THEN-ELSE resolves wx<= value < wy
> ' wz is the index of wx
> ' note I: show index and table values below and above user value entered
>
>
>
>
> To UNSUBSCRIBE, just send mail to:
> basicstamps-unsubscribe@yahoogroups.com
> from the same email address that you subscribed. Text in the Subject and
Body of the message will be ignored.
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
above and below the target value.
index_check8: ' note H
IF value>=wx THEN
READ wz+1 MAX tablesize1 * 2,Word wy
wz = wz MAX tablesize1 ' in case value is out of bounds
ELSE
wy=wx ' final value wx was greater than target value, swap
wz = wz MIN 1 - 1 ' adjust wz to next lower value (but not <0)
READ wz * 2,Word wx ' this is the value less than the target
ENDIf
DEBUG CR,">",TAB,DEC wz,TAB,DEC wx,TAB,DEC wy ' note I
LOOP
With this modification, wz always will point to the table entry that
is less than the target value.
It also operates smoothly if the value entered happens to lie outside
the bounds of the table, pointing to the lowest or highest table
element.
-- Tracy
>Tracy,
>
>I've started to implement this in my program, and it does work VERY fast
>compared to my initial sequential search.
>
>However, I noticed that "wz" changes in multiples of two. Let me explain:
>
>I noticed that your program will work standalone. Upon initial inspection, I
>thought that "wz" would always point to the upper or lower two of the
>indexes found, but it does not. For example, the inputs 56, 57, and 76
>always set wz at the end of the search to "4", even though the wx and wy
>variable are updated to relfect the upper and lower "closest matches".
>
>I then incorperated this into my program with this assumption. I then read
>the values at that index, and that index minus 1, check which one is
>actually closest, then return that index. However, with the behaviour I
>talked about above, this doesn't work properly. Can you offer a suggestion
>to correct this?
>
>This will not be a production product, but if I do use your code in the
>future with your permission, I will definately give you credit!
>
>Thanks,
>Steve Ziuchkovski
>
>
Original Message
>From: "Tracy Allen" <tracy@e...>
>To: <basicstamps@yahoogroups.com>
>Sent: Friday, June 27, 2003 9:52 AM
>Subject: Re: [noparse][[/noparse]basicstamps] Binary search on a lookup table for "closest
>value"
>
>
>> Here's a demo program for binary search. It is like the lookdown
>> operator, except that it searches a table of increasing numbers (word
>> values) in DATA eeprom. You enter a number at the keyboard, and the
>> program finds the numbers closest above and below it in the table.
>> This kind of thing is good for interpolation problems or search for
>> free memory. The binary algorithm finds the answer in N steps, given
>> a table with 2^N entries. E.g., a table with 1024 entries is resolved
>> in 10 steps. Algorithm is like a successive approximation ADC. Uses
>> a bunch of math tricks in place of IF-THEN or CASE statements.
>>
>> '{$STAMP BS2}
>> '{$PBASIC 2.5}
>> ' (c) 2001 Tracy Allen, http://www.emesystems.com
>> ' like lookdown operator, except data in eeprom word table
>> ' word values increasing in table.
> > ' User enters a number. The routine finds the closest two values
> > ' in the table such that wx < number < wy
> > ' and the index pointer to the position of wx in the table
>> ' Uses binary search algorithm for fast acquisition.
>> ' Finds value in a 2^N table in N steps.
>> ' number < smallest value in table returns smallest value
>> ' number > largest value in table returns largest value
>>
>> value VAR Word ' number entered by user
>> wx VAR Word ' comparison value from table
>> wy VAR Word ' binary increment (word for large table)
>> wz VAR Word ' index into table (word for large table)
>> sign VAR Bit ' selects up or down for next step in table
>>
>> tablesize CON 22 ' just for example, 22 entries in DATA table
>> tablesize1 CON tablesize-1
>>
>> table DATA Word 2,Word 5,Word 30,Word 35, Word 57, Word 77, Word 99
>> DATA Word 110, Word 125, Word 278
>> DATA Word 678, Word 777, Word 888, Word 999
>> DATA Word 1010, Word 1111, Word 2000, Word 3333
> > DATA Word 4000, Word 5555, Word 6000, Word 7777
>>
>> DO
>> DEBUG CR,CR,"enter a number: "
>> DEBUGIN DEC5 value ' get user to input a number
>>
>> index_check0:
>> wy=DCD NCD tablesize / 2 ' note A
>> wz=wy-1 ' first address to check, halfway point in the
>table
>>
>> index_check1:
>> READ wz MAX tablesize1 * 2 + table, Word wx ' note B
>> IF wx=value THEN index_check8 ' note C
>> sign=wx/(value MIN 1) MAX 1 ' note D
>> wy=wy/2 ' note E
>> wz=-sign^wy+sign+wz ' note F
>> PAUSE 2
>> ' DEBUG CR,DEC wz,TAB, DEC wy,TAB, DEC wx ,TAB,IBIN sign ' show
>> inner workings
>> IF wy THEN index_check1 ' note G
> > index_check8: ' note H
> > IF value>=wx THEN
> > READ wz+1 MAX tablesize1 * 2,Word wy
wz = wz MAX tablesize1 ' in case value is out of bounds
> > ELSE
> > wy=wx ' final value wx was greater than target value, swap
wz = wz MIN 1 - 1 ' adjust wz to next lower value (but not <0)
READ wz * 2,Word wx ' this is the value less than the target
> > ENDIf
> > DEBUG CR,">",TAB,DEC wz,TAB,DEC wx,TAB,DEC wy ' note I
> > LOOP
> > IF value>=wx THEN
>> READ wz+1 MAX tablesize1 * 2,Word wy
>> ELSE
>> wy=wx
>> READ wz MIN 1 -1 * 2,Word wx
>> ENDIf
>> DEBUG CR,">",TAB,DEC wz,TAB,DEC wx,TAB,DEC wy ' note I
>> LOOP
> >
>> ' note A: could use a constant here if tablesize is a constant
>> ' =largest power of two less than tablesize
>> ' tablesize does not have to be a power of two.
>> ' note B: limit read to last table address, *2 because 2 bytes per word
>> ' note C: speed up process if exact match is found
>> ' note
>> ' position in the table. "value min 1" avoids divide by zero.
>> ' note E: wy is successively lower powers of two
>> ' note F: add (sign=0) or subtract (sign=1) wy from wz
>> ' -sign^wy+sign forms the conditional 2s complement of wy
>> ' note G: continue until wy is reduced to zero
>> ' note H: The IF-THEN-ELSE resolves wx<= value < wy
>> ' wz is the index of wx
>> ' note I: show index and table values below and above user value entered
>>
>>
>>
>>
>> To UNSUBSCRIBE, just send mail to:
>> basicstamps-unsubscribe@yahoogroups.com
>> from the same email address that you subscribed. Text in the Subject and
>Body of the message will be ignored.
>>
>>
>> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>>
>
>
>To UNSUBSCRIBE, just send mail to:
> basicstamps-unsubscribe@yahoogroups.com
>from the same email address that you subscribed. Text in the
>Subject and Body of the message will be ignored.
>
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
This added to the last post does exactly what I wanted. Now my program works
great, and a lot faster!
Steve
Original Message
From: "Tracy Allen" <tracy@e...>
To: <basicstamps@yahoogroups.com>
Sent: Saturday, June 28, 2003 2:11 AM
Subject: Re: [noparse][[/noparse]basicstamps] Binary search on a lookup table for "closest
value"
> Modify the cleanup code that sorts out the two table entries closest
> above and below the target value.
>
> index_check8: ' note H
> IF value>=wx THEN
> READ wz+1 MAX tablesize1 * 2,Word wy
> wz = wz MAX tablesize1 ' in case value is out of bounds
> ELSE
> wy=wx ' final value wx was greater than target value, swap
> wz = wz MIN 1 - 1 ' adjust wz to next lower value (but not <0)
> READ wz * 2,Word wx ' this is the value less than the target
> ENDIf
> DEBUG CR,">",TAB,DEC wz,TAB,DEC wx,TAB,DEC wy ' note I
> LOOP
>
> With this modification, wz always will point to the table entry that
> is less than the target value.
>
> It also operates smoothly if the value entered happens to lie outside
> the bounds of the table, pointing to the lowest or highest table
> element.
>
> -- Tracy
>
>
>
> >Tracy,
> >
> >I've started to implement this in my program, and it does work VERY fast
> >compared to my initial sequential search.
> >
> >However, I noticed that "wz" changes in multiples of two. Let me explain:
> >
> >I noticed that your program will work standalone. Upon initial
inspection, I
> >thought that "wz" would always point to the upper or lower two of the
> >indexes found, but it does not. For example, the inputs 56, 57, and 76
> >always set wz at the end of the search to "4", even though the wx and wy
> >variable are updated to relfect the upper and lower "closest matches".
> >
> >I then incorperated this into my program with this assumption. I then
read
> >the values at that index, and that index minus 1, check which one is
> >actually closest, then return that index. However, with the behaviour I
> >talked about above, this doesn't work properly. Can you offer a
suggestion
> >to correct this?
> >
> >This will not be a production product, but if I do use your code in the
> >future with your permission, I will definately give you credit!
> >
> >Thanks,
> >Steve Ziuchkovski
> >
> >
Original Message
> >From: "Tracy Allen" <tracy@e...>
> >To: <basicstamps@yahoogroups.com>
> >Sent: Friday, June 27, 2003 9:52 AM
> >Subject: Re: [noparse][[/noparse]basicstamps] Binary search on a lookup table for "closest
> >value"
> >
> >
> >> Here's a demo program for binary search. It is like the lookdown
> >> operator, except that it searches a table of increasing numbers (word
> >> values) in DATA eeprom. You enter a number at the keyboard, and the
> >> program finds the numbers closest above and below it in the table.
> >> This kind of thing is good for interpolation problems or search for
> >> free memory. The binary algorithm finds the answer in N steps, given
> >> a table with 2^N entries. E.g., a table with 1024 entries is resolved
> >> in 10 steps. Algorithm is like a successive approximation ADC. Uses
> >> a bunch of math tricks in place of IF-THEN or CASE statements.
> >>
> >> '{$STAMP BS2}
> >> '{$PBASIC 2.5}
> >> ' (c) 2001 Tracy Allen, http://www.emesystems.com
> >> ' like lookdown operator, except data in eeprom word table
> >> ' word values increasing in table.
> > > ' User enters a number. The routine finds the closest two values
> > > ' in the table such that wx < number < wy
> > > ' and the index pointer to the position of wx in the table
> >> ' Uses binary search algorithm for fast acquisition.
> >> ' Finds value in a 2^N table in N steps.
> >> ' number < smallest value in table returns smallest value
> >> ' number > largest value in table returns largest value
> >>
> >> value VAR Word ' number entered by user
> >> wx VAR Word ' comparison value from table
> >> wy VAR Word ' binary increment (word for large table)
> >> wz VAR Word ' index into table (word for large table)
> >> sign VAR Bit ' selects up or down for next step in table
> >>
> >> tablesize CON 22 ' just for example, 22 entries in DATA
table
> >> tablesize1 CON tablesize-1
> >>
> >> table DATA Word 2,Word 5,Word 30,Word 35, Word 57, Word 77, Word 99
> >> DATA Word 110, Word 125, Word 278
> >> DATA Word 678, Word 777, Word 888, Word 999
> >> DATA Word 1010, Word 1111, Word 2000, Word 3333
> > > DATA Word 4000, Word 5555, Word 6000, Word 7777
> >>
> >> DO
> >> DEBUG CR,CR,"enter a number: "
> >> DEBUGIN DEC5 value ' get user to input a number
> >>
> >> index_check0:
> >> wy=DCD NCD tablesize / 2 ' note A
> >> wz=wy-1 ' first address to check, halfway point in the
> >table
> >>
> >> index_check1:
> >> READ wz MAX tablesize1 * 2 + table, Word wx ' note B
> >> IF wx=value THEN index_check8 ' note C
> >> sign=wx/(value MIN 1) MAX 1 ' note D
> >> wy=wy/2 ' note E
> >> wz=-sign^wy+sign+wz ' note F
> >> PAUSE 2
> >> ' DEBUG CR,DEC wz,TAB, DEC wy,TAB, DEC wx ,TAB,IBIN sign ' show
> >> inner workings
> >> IF wy THEN index_check1 ' note G
> > > index_check8: ' note H
> > > IF value>=wx THEN
> > > READ wz+1 MAX tablesize1 * 2,Word wy
> wz = wz MAX tablesize1 ' in case value is out of bounds
> > > ELSE
> > > wy=wx ' final value wx was greater than target value, swap
> wz = wz MIN 1 - 1 ' adjust wz to next lower value (but not <0)
> READ wz * 2,Word wx ' this is the value less than the target
> > > ENDIf
> > > DEBUG CR,">",TAB,DEC wz,TAB,DEC wx,TAB,DEC wy ' note I
> > > LOOP
> > > IF value>=wx THEN
> >> READ wz+1 MAX tablesize1 * 2,Word wy
> >> ELSE
> >> wy=wx
> >> READ wz MIN 1 -1 * 2,Word wx
> >> ENDIf
> >> DEBUG CR,">",TAB,DEC wz,TAB,DEC wx,TAB,DEC wy ' note I
> >> LOOP
> > >
> >> ' note A: could use a constant here if tablesize is a constant
> >> ' =largest power of two less than tablesize
> >> ' tablesize does not have to be a power of two.
> >> ' note B: limit read to last table address, *2 because 2 bytes per word
> >> ' note C: speed up process if exact match is found
> >> ' note
> >> ' position in the table. "value min 1" avoids divide by zero.
> >> ' note E: wy is successively lower powers of two
> >> ' note F: add (sign=0) or subtract (sign=1) wy from wz
> >> ' -sign^wy+sign forms the conditional 2s complement of wy
> >> ' note G: continue until wy is reduced to zero
> >> ' note H: The IF-THEN-ELSE resolves wx<= value < wy
> >> ' wz is the index of wx
> >> ' note I: show index and table values below and above user value
entered
> >>
> >>
> >>
> >>
> >> To UNSUBSCRIBE, just send mail to:
> >> basicstamps-unsubscribe@yahoogroups.com
> >> from the same email address that you subscribed. Text in the Subject
and
> >Body of the message will be ignored.
> >>
> >>
> >> Your use of Yahoo! Groups is subject to
http://docs.yahoo.com/info/terms/
> >>
> >
> >
> >To UNSUBSCRIBE, just send mail to:
> > basicstamps-unsubscribe@yahoogroups.com
> >from the same email address that you subscribed. Text in the
> >Subject and Body of the message will be ignored.
> >
> >
> >Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
> To UNSUBSCRIBE, just send mail to:
> basicstamps-unsubscribe@yahoogroups.com
> from the same email address that you subscribed. Text in the Subject and
Body of the message will be ignored.
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>