»

[Zac67]

A binary tree search with recursion will result in very compact code but the recursion bit may take up a bit of stack space... You can do it the iterative way as well with more code and much less elegance. Plus, it'll (probably) be a lot faster.

[Fats]

Originally Posted by bloodline

Appologies! I only quickly looked over it If I had a larger array I would certainly investigate this method... I'm intrigued to see how a tiny microcontroller would cope with this kind of search!

OK, then you can go really funky. Using something like this:

struct lookup
{
   int num;
   unsigned char rank;
}

struct lookup vals[] =
{
    {4185, 4},
    {4507, 3},
    {4883, 2},
    {5327, 1},
    {MAX, 0}
}

If you make the array size a power of two you should be able to implement the binary search with bit manipulation using |= and <<. Or you can start somewhere in the middle of the array with an index that is power of two and see that you don't go over the highest index.

greets,
Staf.

[Jose]

Another idea that I don't know if it would work. If the values of the curve can be guessed by using a mathematical function you could revert the function and get the x value. Then calculate the rank by dividing by rank x size (of course that assumes rank x size is constant between ranks, as opposed to rank y size which isn't (like you say it's a curve)).

[bloodline]

Originally Posted by Jose

Another idea that I don't know if it would work. If the values of the curve can be guessed by using a mathematical function you could revert the function and get the x value. Then calculate the rank by dividing by rank x size (of course that assumes rank x size is constant between ranks, as opposed to rank y size which isn't (like you say it's a curve)).

On an 8bit microcontroller, you really want to avoid multiplication and division (unless you can use a power of 2... ie left or right shifts). I really did try to do this mathematically first, but realised that I simply don't have the CPU time

[Thorham]

Originally Posted by bloodline

On an 8bit microcontroller, you really want to avoid multiplication and division (unless you can use a power of 2... ie left or right shifts). I really did try to do this mathematically first, but realised that I simply don't have the CPU time

Out of interest, how often is this code executed per second (seems quite often seeing how that controller does 1 mips per Mhz (according to the specs I looked up at least))? Also, for the challenge, would it be a problem to post the whole threshold array here? Maybe there's a nice trick possible

[Zac67]

Reminds me of when I tried to calculate the Mandelbrot set without any(!) multiplications - it was hideously fast on a non-FPUd 68000 (for the time) but the precision was really crap - not surprising, I used a 16 bit table of squares together with (a+b)^2-a^2-b^2=2ab. 128KB was no problem but a somewhat usable 32 bit table would take 16 GB - still waiting for that to come around...