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 (http://en.wikipedia.org/wiki/Binary_search_algorithm)

[HankMcSpank]

Binary Search Algorithm (http://en.wikipedia.org/wiki/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...

http://img192.imageshack.us/img192/2361/excelh.jpg (http://img192.imageshack.us/i/excelh.jpg/)

(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.

[cncmachineguy]

Let me just add, 25 instructions is a lot of asm just to check that. See, this is why I want to know how long things take.

[HankMcSpank]

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



Sorry, should have made it clear...the table I posted above is actually longer, but I shortened it to be easier on the eye! (the jist of the table was just to show the methodology of converting incoming frequency (guitar notes), to counts (comparator1 interrupt counts) & finally the end goal - a midi note value.

the LUT will only have something like this (first two columns are upper and lower comparator 'counts' for each individual musical note boundary)



Lo Hi Midi Note
62479 58971 28
58972 55662 29
55663 52538 2A
52539 49589 2B
49590 46806 2C
46807 44179 2D
44180 41699 2E
41700 39359 2F
39360 37150 30
37151 35065 31
35066 33097 32
33098 31239 33
31240 29486 34
29487 27831 35
27832 26269 36
26270 24794 37
24795 23403 38
23404 22089 39
22090 20849 3A
20850 19679 3B
19680 18575 3C
18576 17532 3D
17533 16548 3E
16549 15619 3F
15620 14743 40
14744 13915 41
13916 13134 42
13135 12397 43
12398 11701 44
11702 11044 45
11045 10424 46
10425 9839 47
9840 9287 48
9288 8766 49
8767 8274 4A
8275 7810 4B
7811 7371 4C
7372 6957 4D
6958 6567 4E
6568 6198 4F
6199 5850 50
5851 5522 51
5523 5212 52
5213 4919 53
4920 4643 54
4644 4383 55
4384 4137 56
4138 3905 57
3906 3800 58


There are about 50 individual notes on a guitar - from lowest open E (82.4Hz) thru the highest E fretted at the 24th fret of the top E string (1318.51Hz)....so an LUT will need an array 50 deep & a check condition along these lines for any change in the count value...



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


but to apply 50 of code like that each & every time guitar note changes is going to get time consuming, hence wanting something like a binary search algorithm for picbasic (a search on the forum yields almost nothing)

[cncmachineguy]

based on your chart, I would look first to see if count < 10000. thats the one to take care of the quickest. then check somewhere between 10000 and 65000.

Of course when you find the range, just use if then like you posted

[cncmachineguy]

How bout something like this?



'Is this the right symbel for comments?
'This is what I'm using it for
'
'Assuming count is the number to be checked
'
'This set of checks breaks it into 3 16 possible chuncks

If count < 3800 then ERROR ' count under 3800 must be wrong, but it could mean TMR rolled over
If (count <= 9288) and (count >= 3800) then LowCount '
If count <= 23404 then MidCount ' no need to check lower limit because that was in last check
if count <= 62479 then HighCount ' still no lower check

'now do the same for the each section:

LowCount
if count <= 4920 then LLowCount
if count <= 6568 then MLowCount
' must be High low count
'at this point do another chunck break or code for all possibles
'another chunck break

if count <=8275 then LhLowCount
'choice of 4 now
'at this point count MUST be >8275 and <=9288

LhLowCount ' count between 6569 and 8275
if (count >=6569) and (count <=7372) then note=4D : goto NoteFound
If (count >=7371) and (count <=7372) then note=4C : goto NoteFound
if (count >=7810) and (count <=8275) then note=4B : goto NoteFound



Dose this make any sense? I think there is a problem with your numbers, but it could be me. Seems like high and low of next up note are reversed. For instance note 4D is 7372-6957, and 4C is 7811-7371.

[HankMcSpank]

Hi Bert,

I wil digest your code a bit later (seriously, to my untrained eye, everything takes a while decipher & get my head around!). As it goes it seems pretty whippy already (ie just running through the whole 50 deep LUT, top to bottom)...

Here's a quick video I've just made....

(to be able to see what's going on in it, you really need to watch in full screen mode *and* 720p, which I don't know how to embed - these options can be chosen looking at the video directly on you tube via this URL http://www.youtube.com/watch?v=4mlb-LT3HU8 ).....


http://www.youtube.com/v/4mlb-LT3HU8&hd=1

Green trace is audio 'input' signal (a sine wave sent into my circuit from a synth), the yellow trace is the same signal but squared up (feeding into the PIC's comparator1), the data to the left of the scope is the midi info as transmitted out of the PIC.

the full signal path is as follows...

Synth audio sine wave signal-> squaring cct-> pic comparator->interrupt counter -> PIC LUT ->PIC then outputs midi data using HSEROUT-> into a PC MIDi In port->into an app callec MID- OX (A midi interpreter/viewer - which is what that window/data to the left in the video is)

So the sine wave jumping about is actually me playing different notes on a synth (& thereby changing the sine wave frequency into the PIC - to test the PIC frequency detection & conversion to MIDI)


PS btw I had the data the wrong way round when I posted earlier - the LUT condition was not being met, here it is corrected...



if (comp1time>= 52538 AND comp1time <= 55663) then note = $2A
if (comp1time>= 49589 AND comp1time <= 52539) then note = $2B
etc etc


So maybe I don't need a binary search algorithm, but every little helps wrt to speed, so may still explore that avenue.

[cncmachineguy]

Hank, if it works dont fix it. or if it isn't broke, fix it till it is. lol

Seriously, the only thing i would do is make sure and run your test from the bottom up. By this I mean, check for the low count first on up th to highest count. then you can be sure to have enough time. :). Something else about your linear search, Y only need to test for 1 condition in each next IF after the first. heres why:

First check establishes a range, say 3800-3900, if this fails, number must be > 3900. next check just needs to look for <4000 cuz you know its >3900. next check if <4200,again because it must be >3900. and so on. Of course my numbers are fictious, but you should get the point. Only checking 1 condition should almost double the execution speed (half the processing).

the code I posted is not complete, it shows how to go through the levels of searching.

[HankMcSpank]

Well the acid test is when I play a guitar into it & the pic 'triggers' a sound in midi synth module.

A bass E string 'period' is about 12ms (82.4Hz) ....add in the overhead that detecting the frequency will entail, then it's going to be higher.

They reckon the average musician can detect about 10ms of latency (ie from hitting a key, banging a drum,plucking a string .... to actually hearing the sound) so I'm already behind the curve so to speak. The commercial 'guitar to midi' converters pull this frequency 'detection time' in by detecting half a period....so for 82.4Hz, that'd be about 6ms - safely under the 10ms level - but I reckon that'd need a 40Mz oscillator to have the necessary granularity.

So perhaps it's better to go top down (the bass frequencies are at the top of the list), just to rescue back a little bit of 'processing time' for those lower frequencies (for example a 1Khz 'period' is 1ms, so I've far more time to play with vs lower frequencies.)