Welcome, Guest. Please login or register.

Author Topic: Programming question! :)  (Read 3165 times)

Description:

0 Members and 1 Guest are viewing this topic.

Offline bloodlineTopic starter

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
    • Show only replies by bloodline
    • http://www.troubled-mind.com
Re: Programming question! :)
« Reply #29 from previous page: April 17, 2012, 06:31:02 PM »
Quote from: Leffmann;689077
Actually it's adjusted to do exactly what you want, and can even be optimized further.
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!

Offline Zac67

  • Hero Member
  • *****
  • Join Date: Nov 2004
  • Posts: 2890
    • Show only replies by 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

  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 672
    • Show only replies by 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

  • Hero Member
  • *****
  • Join Date: Feb 2002
  • Posts: 2869
    • Show only replies by 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 bloodlineTopic starter

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
    • Show only replies by bloodline
    • 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

  • Hero Member
  • *****
  • Join Date: Oct 2009
  • Posts: 1149
    • Show only replies by 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

  • Hero Member
  • *****
  • Join Date: Nov 2004
  • Posts: 2890
    • Show only replies by 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 »