A speed-tatstic way to look up a value? (LUTs)

[HankMcSpank]

I'd like to resolve 'Comparator interrupt counts' (frequency) to a Musical note & therefore have a table to base a LUT on as follows....

(btw: I've not got the low & high columns mixed up....they are with respect to frequency - as the incoming frequency increases the amount of interrupt counts get less)

Count	low	High	Note
68104	67000	66193	D
64282	66194	62478	D#
60674	62479	58971	E
57269	58972	55662	F
54054	55663	52538	F#
51021	52539	49589	G
48157	49590	46806	G#
45454	46807	44179	A
42903	44180	41699	A#
40495	41700	39359	B
38222	39360	37150	C
36077	37151	35065	C#
34052	35066	33097	D
32141	33098	31239	D#
30337	31240	29486	E
28634	29487	27831	F
27027	27832	26269	F#
25510	26270	24794	G
24078	24795	23403	G#
22727	23404	22089	A
21451	22090	20849	A#
20247	20850	19679	B
19111	19680	18575	C
18038	18576	17532	C#
17026	17533	16548	D
16070	16549	15619	D#
15168	15620	14743	E
14317	14744	13915	F
13513	13916	13134	F#
12755	13135	12397	G
12039	12398	11701	G#
11363	11702	11044	A
10725	11045	10424	A#
10123	10425	9839	B
9555	9840	9287	C5
9019	9288	8766	C#
8513	8767	8274	D
8035	8275	7810	D#
7584	7811	7371	E
7158	7372	6957	F
6756	6958	6567	F#
6377	6568	6198	G
6019	6199	5850	G#
5681	5851	5522	A
5362	5523	5212	A#
5061	5213	4919	B
4777	4920	4643	C
4509	4644	4383	C#
4256	4384	4137	D
4017	4138	3905	D#
3792	3906	3800	E

Therefore if the comparator interrupt count comes in a somewhere between 19680 & 18575.....then I need to establish (look up) what the associated musical note is - in this case a 'C'

If it then changes again to between 4138 & 3905 then it's high 'D#' ....and so on.

Now as a beginner, the simple way I'd approach this is take my comparator 'interrupt count' & go through the list one entry at a time until I get a match.....but if the notes are changing rapidly (&/or are at different ends of the table), then that's quite an overhead - is there a slick way to get to the actual note fast (eg way back, I was taught something in military wrt finding a fault in an electronic cct - the 'split half technique' ...basically to first check if the 'fault' is present at the halfway point in a circuit - if not, split the mid point again and check if it's present there....etc - this quickly gets you to the general area where the fault lies)....I'm sure something similar could be applied like that here?

[rmteo]

Binary Search Algorithm

[HankMcSpank]

Binary Search Algorithm

That's exactly what I was thinking of - so now, how to implement in picbasic!

Imagine an array 100 deep (& for simplicity's sake, populated with values 1 thru 100), with an incoming number of 90 to 'look up' against...

So, the methodology....

is new incoming value higher or lower than 50

(result = higher therefore the next stage...)

is new incoming number higher of lower than 75

result = higher again, & so on it continues...

but eventually it all starts getting tricky (because half way between 75 & 100 is 87.5 ....what to do here, etc?)

[cncmachineguy]

something I've been thinking about. since this is music, i assume there is a predictable difference between the low or high numbers? I ask because if you could divide all the numbers to create a case type lookup.

The answer to 87.5 IMHO is to use 87 or 88. Since the half tests are hard coded in(at least for your example) no need to be exact.

[HankMcSpank]

something I've been thinking about. since this is music, i assume there is a predictable difference between the low or high numbers? I ask because if you could divide all the numbers to create a case type lookup.

The answer to 87.5 IMHO is to use 87 or 88. Since the half tests are hard coded in(at least for your example) no need to be exact.

The table I posted earlier was the shortened version, I had diffs formatting the full version, but this screenshot shows what I'm getting at...



(note the first two notes in the table will actually cause a timer 1 overflow and therefore can't be monitored when using a 20Mhz Osc - well not without extra code in the interrupt handler - so I include them only for completeness)


the frequency of the incoming signal is derived from the the number of comparator interrupts rx'ed for the frequency 'peroid' ...& becuase I want to map the frequency to a midi 'note' - and musical 'notes' are set in stone (ie no such thing a middle C.23) - I therefore also need to establish what the midway count is between successive note 'frequencies' (the note boundary if you like)

....but with a LUT 50 deep & with two conditions to check for per LUT entry, eg .....

if (comp1time>= 66194 and comp1time <= 62478) then note = $27

then if the incoming frequency is changing rapidly (becuase the notes are changing rapidly), then I need to have a fast way of resolving the incoming frequency to a note value.

[cncmachineguy]

Well I only count 32 notes, but I'm on my phone so maybe I don't get to see the whole thing.

That said, A is the last note I see, and it seems there is a count of ~11,000 for that note. So to me that's ~11,000 instructions to waste before a new interupt. That's tons of time if I understand your chart correctly. In any event, I like to get things done fast. My suggestion is a hybrid search. Maybe check the middle, decide higher or lower, then do a linear search from there.

Now back to the numbers: If each test took 25 instructions and you have 50 tests: that's 1250 instructions. Approx 10% of the time between interupts. So still no prob.