Welcome, Guest. Please login or register.
Amiga Kit Amiga Store Iridium Banner AMIStore App Store A1200/A600 4xIDE Interface

AuthorTopic: Programming question! :)  (Read 2150 times)

0 Members and 1 Guest are viewing this topic.

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

Offline 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
 

Offline Jose

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\\"
 

Offline bloodline

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
  • Total likes: 0
    • http://www.troubled-mind.com
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 :)

Offline 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 ;)
 

Offline 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 »