    ### AuthorTopic: Programming question! :)  (Read 2346 times)

0 Members and 1 Guest are viewing this topic.

#### Zac67 ##### Re: Programming question! :)
« Reply #30 on: April 17, 2012, 07:07:19 PM »
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 ##### Re: Programming question! :)
« Reply #31 on: April 17, 2012, 07:08:10 PM »
Quote from: bloodline;689088
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:

Code: [Select]
`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.
Trust me...                                              I know what I\'m doing

#### Jose

• Hero Member
•     • Join Date: Feb 2002
• • Posts: 2868
• Total likes: 1 ##### Re: Programming question! :)
« Reply #32 on: April 19, 2012, 12:40:38 AM »
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)).
\\"We made Amiga, they {bleep}ed it up\\"

#### bloodline ##### Re: Programming question! :)
« Reply #33 on: April 19, 2012, 05:43:26 AM »
Quote from: Jose;689458
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 ##### Re: Programming question! :)
« Reply #34 on: April 19, 2012, 03:15:00 PM »
Quote from: bloodline;689507
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 ##### Re: Programming question! :)
« Reply #35 on: April 19, 2012, 07:30:39 PM » 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...
« Last Edit: April 19, 2012, 07:33:51 PM by Zac67 »