Scan a set of arrays faster

jeff-o

Hi everyone,

First off, thanks for helping me out with compacting the size of my Prism guitar code. In the end, reducing the size of the Karplus-Strong buffers made the biggest difference, though moving all the strings to the upper memory locations in EEPROM made a big difference, too.

I'm now working on the algorithm that measures the player's finger position along the frets, and returns an offset that can be added to the "open" tuning of the string to play a new pitch.

A different program is used to load in fret thresholds into memory (String0Frets -> String3Frets). When the memory checker program (and eventually, the main program) is run, those values are loaded into a local array. Inside a loop, the current position of the player's finger is continually read from the ADC. A "repeat until" loop is then used to compare that value to each indexed value in the relevant array, until the indexed item is larger than the measurement. The value of the index pointer is then set as the offset. This is done for each of the four strings.

This works well enough, but I'm wondering if there's a faster way to do it. The reason is that it takes a while for the index value for any one string to return back to zero (no offset) when the player's finger is removed from the string. Maybe half a second or so? On an ordinary guitar there is almost zero transition time so I want to replicate that as well as possible. Of course, it could be the ADC or the hardware anti-aliasing filter I'm using, so there may be no software fix.

Anyway, code is attached below in both 12blocks and ordinary spin. There probably isn't much use in compiling it since you won't have the same hardware as me, but take a look at the logic and let me know what you think...

MagIO2

From what you wrote I'd guess that the items in the array are sorted? Then it looks like a modified binary search could help here. (Have a look in Wikipedia).
The basic idea is that you start in the middle and depending on the compare result you go up or down or you found the right value. The distance of going up/down is initially 1/4 of the size of the array. With each iteration you'd divide the distance by 2.

In the plain loop-search you need 16 comparisons in average. Minimum 1, maximum 32 comparisons.
With binary search your min. is 1 and your max. is 5 to search for equal - propably one more to search for > instead.

Cluso99

jeff-o: Way to go man! This project sounds awesome.
Unfortunately from a non-music person with limited analog experience, I cannot help you in this. However, it would seem to me that there should be a software solution to reduce the decay time significantly, unless the resistor-capacitance time constant is too large in hardware to allow fast decay rates. Perhaps it would help others to comment further if you posted the ADC section of the schematic.

MagIO2

PS: "This is done for each of the four strings" sounds like letting 4 COGs do the search could also help.

jeff-o

I've got one cog I can dedicate to this. The array items are indeed sorted, from low to high. Initially I had a test case with average numbers (the same numbers used for each string) that was done using binary search (or divide-by-two, as I learned it). It used more code but I guess it was faster. Is there a better way to do a binary search, than using a huge multi level if-else chain?

kwinn

You can do arithmetic on the array pointer using shifts to divide by 2 and adds or subtracts to move up or down the array.

MagIO2

If I read your code right the arrays have a size of 32.

So, here's some pseudo-code for a non-if-then-else solution based on a loop:

idx := 15
delta := 8
repeat until (array[idx] => adc) and (array[idx-1] < adc)
  if array[idx]>adc
    idx -= delta
  else
   idx += delta
  delta >>= 1

The comparison to array[idx-1] has been added due to the fact that you don't really do a binary search, which would check for equal. But this also includes a little problem: if the right value would be in array[0] your idx would actually reach 0 in the end which gives you an access to array[0 - 1] which is out of your array. But you can propably solve this by yourself, right?! ;o) You can either extend the condition of the repeat (which is slower) or extend the array and change the start-index.

jeff-o

Ah, I see; instead of incrementing the pointer, I divide or multiply it.

But yes, it's true, I'm not looking for an exact match. Since the player's finger can be anywhere within the fret, and the value returned by the ADC will be within a range, I'm using the fret (the metal strips on the fretboard) as the threshold. Thus the use of fret0<getString0Frets(x). It looks for the first case where the array item is greater than the value, then exits the loop. My array is actually 19 elements (0 to 18) which makes thing a bit less tidy when it comes to dividing. That's why I did it using if-else statements before. I'll see how I can incorporate the bit-shifting into my code...

Perry

I am not convinced your scan array code is the problem.

Instead of "_bsl.pause(200)" at the beginning of your inner loop why not wait until a string is not pressed.

    FretCapture :=  0
    repeat until FretCapture > 0
      FretCapture :=_ adc.getval(1)