Amiga.org

Operating System Specific Discussions => Other Operating Systems => Topic started by: bloodline on April 16, 2012, 03:44:36 PM

Title: Programming question! :)
Post by: bloodline on April 16, 2012, 03:44:36 PM
I have a list that I want to compare a value against to determine the value's "rank", the problem is that once I have determined the rank I wish to end the search... In ASM this is easy (please bare with my half remembered 68k):
Code: [Select]


_start  move.l _number,d0
          cmpi.l #4185,d0
          blt.s _case4184
          cmpi.l #4507,d0
          blt.s _case4507
          cmpi.l #4883,d0
          blt.s _case4883
          cmpi.l #5327,d0
          blt.s _case5327
          move.l 0,d0
_break

           rts

_case4185
           move.l #4,d0
           jmp _break

_case4507
           move.l #3,d0
           jmp _break

_case4883
           move.l #2,d0
           jmp _break

_case5327
           move.l #1,d0
           jmp _break


But I want to write this in C... Suffice to say the actual list is much larger and CPU time is at a premium, is there any way I can write it without using Goto?
Title: Re: Programming question! :)
Post by: jorkany on April 16, 2012, 03:49:46 PM
Try using a switch statement. It should produce code very similar to what you have posted, usually using a jump table but check the asm output to make sure it's acceptable.



Also, you might want to consider examining your algorythmic boundaries!  (j/k)
Title: Re: Programming question! :)
Post by: Thorham on April 16, 2012, 03:51:15 PM
How long is that list exactly? If it's not too large you can use a table, which would certainly be the fastest way.
Title: Re: Programming question! :)
Post by: TheBilgeRat on April 16, 2012, 04:09:03 PM
Quote from: jorkany;688784
Try using a switch statement. It should produce code very similar to what you have posted, usually using a jump table but check the asm output to make sure it's acceptable.



Also, you might want to consider examining your algorythmic boundaries!  (j/k)


I see what you did there :D
Title: Re: Programming question! :)
Post by: bloodline on April 16, 2012, 04:10:24 PM
Quote from: jorkany;688784
Try using a switch statement. It should produce code very similar to what you have posted, usually using a jump table but check the asm output to make sure it's acceptable.



Also, you might want to consider examining your algorythmic boundaries!  (j/k)
Can't use a switch, notice that I score the number based on it being lower than a threshold value... The problem is that the threshold boundaries are not linear (and for the purpose of this task can't be calculated... I'm probably going to have a loop that compares against an array of threshold values. I was just hoping it could be done in a nice simple table for maximum performance :)
Title: Re: Programming question! :)
Post by: Thorham on April 16, 2012, 04:24:18 PM
Quote from: bloodline;688789
The problem is that the threshold boundaries are not linear (and for the purpose of this task can't be calculated...
What are those values exactly?

Quote from: bloodline;688789
I'm probably going to have a loop that compares against an array of threshold values. I was just hoping it could be done in a nice simple table for maximum performance :)
If you can have an array of threshold values, then you might still have your table. How big is the largest value?
Title: Re: Programming question! :)
Post by: bloodline on April 16, 2012, 04:29:00 PM
Quote from: Thorham;688793
What are those values exactly?

If you can have an array of threshold values, then you might still have your table. How big is the largest value?
The values are rotational time values and I need to set an index dependant on a specific time. They scale somewhat geometrically, but not exactly, and I don't have enough CPU time to calculate that anyway :-/

The largest value is 60,000 (a lookup table is totally out of the question) :)
Title: Re: Programming question! :)
Post by: SamuraiCrow on April 16, 2012, 04:33:42 PM
Quote from: bloodline;688783
I have a list that I want to compare a value against to determine the value's "rank", the problem is that once I have determined the rank I wish to end the search... In ASM this is easy (please bare with my half remembered 68k):
Code: [Select]


_start  move.l _number,d0
          cmpi.l #4185,d0
          blt.s _case4184
          cmpi.l #4507,d0
          blt.s _case4507
          cmpi.l #4883,d0
          blt.s _case4883
          cmpi.l #5327,d0
          blt.s _case5327
          move.l 0,d0
_break

           rts

_case4185
           move.l #4,d0
           jmp _break

_case4507
           move.l #3,d0
           jmp _break

_case4883
           move.l #2,d0
           jmp _break

_case5327
           move.l #1,d0
           jmp _break


But I want to write this in C... Suffice to say the actual list is much larger and CPU time is at a premium, is there any way I can write it without using Goto?

Code: [Select]

int test(num)
{
  if (num<4185)return 4;
  if (num<4507)return 3;
  if (num<4883)return 2;
  if (num<5327)return 1;
  return 0;
}

This is an exact conversion of the Assembly code you gave and it doesn't use any goto statements.
Title: Re: Programming question! :)
Post by: bloodline on April 16, 2012, 04:36:23 PM
Quote from: SamuraiCrow;688795
Code: [Select]

int test(num)
{
  if (num<4185)return 4;
  if (num<4507)return 3;
  if (num<4883)return 2;
  if (num<5327)return 1;
  return 0;
}

This is an exact conversion of the Assembly code you gave and it doesn't use any goto statements.
Damn, I couldn't see for looking! Cheers :) hahahah
Title: Re: Programming question! :)
Post by: Thorham on April 16, 2012, 05:30:31 PM
Quote from: bloodline;688794
The values are rotational time values and I need to set an index dependant on a specific time. They scale somewhat geometrically, but not exactly, and I don't have enough CPU time to calculate that anyway :-/
I was going to say that you don't have to calculate anything if you know the thresholds beforehand, and can just use a table, but ...

Quote from: bloodline;688794
The largest value is 60,000 (a lookup table is totally out of the question) :)
... if a 60000 entry long array is out of the question, then what's the target system (memory constraints)? Is such a table too large? Or is the problem that the thresholds are floating point? If it's floating point, and you don't need more than three decimals of precision (which 60,000 leads me to believe), then a table may still possible (fixed point).

Please provide us with some more information here, because you've left out crucial details.
Title: Re: Programming question! :)
Post by: bloodline on April 16, 2012, 06:04:55 PM
Quote from: Thorham;688807
I was going to say that you don't have to calculate anything if you know the thresholds beforehand, and can just use a table, but ...

... if a 60000 entry long array is out of the question, then what's the target system (memory constraints)? Is such a table too large? Or is the problem that the thresholds are floating point? If it's floating point, and you don't need more than three decimals of precision (which 60,000 leads me to believe), then a table may still possible (fixed point).

Please provide us with some more information here, because you've left out crucial details.
The target system is an ATMega328 :) and Sam Crow has poked my brain and given me exactly the solution I was trying to think of... Funny how I could see it in 68k Asm (that haven't used for 15 years), but not in C
Title: Re: Programming question! :)
Post by: Thorham on April 16, 2012, 06:12:44 PM
Quote from: bloodline;688813
The target system is an ATMega328 :) and Sam Crow has poked my brain and given me exactly the solution I was trying to think of... Funny how I could see it in 68k Asm (that haven't used for 15 years), but not in C
Ah, that clears it up then. On a system with such a small amount of memory, a table is indeed out of the question :)
Title: Re: Programming question! :)
Post by: Fats on April 16, 2012, 07:17:40 PM
Quote from: SamuraiCrow;688795
Code: [Select]

int test(num)
{
  if (num<4185)return 4;
  if (num<4507)return 3;
  if (num<4883)return 2;
  if (num<5327)return 1;
  return 0;
}



If you don't want to do it in a function you could use ? : operator like:

Code: [Select]

  rank =
    (num<4185) ? 4 :
    (num<4507) ? 3 :
    (num<4883) ? 2 :
    (num<5327) ? 1 :
    0;


greets,
Staf.
Title: Re: Programming question! :)
Post by: bloodline on April 16, 2012, 07:47:55 PM
Ahhh! Good call, I'm quite comfortable with usig a function, but I won't forget this either!! Many thanks for your help :)
Title: Re: Programming question! :)
Post by: Duce on April 16, 2012, 09:29:45 PM
Threads like this are what makes A.org great.  People helping people out.
Title: Re: Programming question! :)
Post by: bloodline on April 16, 2012, 10:08:39 PM
Quote from: Duce;688854
Threads like this are what makes A.org great.  People helping people out.
There are loads of great programmer on A.org... Odd actually that there isn't a dedicated forum for programming issues?
Title: Re: Programming question! :)
Post by: Zac67 on April 16, 2012, 10:23:07 PM
Actually, comparing against an array uses less RAM all in all (just the values and the loop, you save the space of all but one cmp and blt ops minus loop ops). On a somewhat caching CPU it should also perform better since the loop needs only be fetched once and then just the array values get read - the slowest is always the memory. Without cache your approach will be faster, saving the loop overhead.

Also depends on the indexing range the CPU is capable of, of course...

You could also combine both methods with a larger loop (did that once on a 6502 to save the few cycles I needed).
Title: Re: Programming question! :)
Post by: Jose on April 16, 2012, 10:53:01 PM
I have an idea. Depending on how you want to optimize it (apparently for speed rather than size) you could organize ranks comparisons in a binary tree like sequence (assuming the ranks are fixed). This would grant you the fastest search results possible but probably a tid bit bigger code.
Don't ask me for a code sample right now though :)
Title: Re: Programming question! :)
Post by: bloodline on April 16, 2012, 10:58:08 PM
Quote from: Zac67;688866
Actually, comparing against an array uses less RAM all in all (just the values and the loop, you save the space of all but one cmp and blt ops minus loop ops). On a somewhat caching CPU it should also perform better since the loop needs only be fetched once and then just the array values get read - the slowest is always the memory. Without cache your approach will be faster, saving the loop overhead.

Also depends on the indexing range the CPU is capable of, of course...

You could also combine both methods with a larger loop (did that once on a 6502 to save the few cycles I needed).
The code needs to execute as quickly as possible, I have very few CPU cycles and no cache to speed the loop (though the loop is where my instincts took me).

Trying to do real time stuff with 8bit Microcontrollers is fun! :)

-edit- just want to add that the uc I'm using has plenty of program memory 32k, but only 2k of ram... So I need to be a bit careful with my arrays and variables :)
Title: Re: Programming question! :)
Post by: bloodline on April 16, 2012, 10:59:08 PM
Quote from: Jose;688875
I have an idea. Depending on how you want to optimize it (apparently for speed rather than size) you could organize ranks comparisons in a binary tree like sequence (assuming the ranks are fixed). This would grant you the fastest search results possible but probably a tid bit bigger code.
Don't ask me for a code sample right now though :)
Not sure a binary tree would be faster, post some code and we can look through the merits :)
Title: Re: Programming question! :)
Post by: Leffmann on April 17, 2012, 12:26:09 AM
Don't know about a binary tree, but a binary search will reduce the number of searches to log2 n, i.e. if you have an array of 256 numbers it will do 8 searches. Basic implementation would be:

Code: [Select]
// For an array of 100 numbers, call with binsearch(n, 0, 99);

int binsearch(int n, int a, int b)
{
  if(a == b)
    return a;

  int mid = a + (b-a)/2;
 
  if(n < array[mid])
    return binsearch(n, a, mid);
  else
    return binsearch(n, mid+1, b);
}

EDIT: this binary search assumes the array is sorted in ascending order.
Title: Re: Programming question! :)
Post by: smerf on April 17, 2012, 02:53:09 AM
Quote from: bloodline;688783
I have a list that I want to compare a value against to determine the value's "rank", the problem is that once I have determined the rank I wish to end the search... In ASM this is easy (please bare with my half remembered 68k):
Code: [Select]


_start  move.l _number,d0
          cmpi.l #4185,d0
          blt.s _case4184
          cmpi.l #4507,d0
          blt.s _case4507
          cmpi.l #4883,d0
          blt.s _case4883
          cmpi.l #5327,d0
          blt.s _case5327
          move.l 0,d0
_break

           rts

_case4185
           move.l #4,d0
           jmp _break

_case4507
           move.l #3,d0
           jmp _break

_case4883
           move.l #2,d0
           jmp _break

_case5327
           move.l #1,d0
           jmp _break


But I want to write this in C... Suffice to say the actual list is much larger and CPU time is at a premium, is there any way I can write it without using Goto?


Hi,

This is quite simple, just go to kings Knight pawn, and move two to the left, not forgetting to move queen pawn two spaces to the right, and then you get
checkmate.

If you figured out that I don't have a clue to what your talking about, it means that you are 10 times smarter than the average person here at Amiga.org

:-)

smerf
Title: Re: Programming question! :)
Post by: bloodline on April 17, 2012, 03:19:56 PM
Quote from: Leffmann;688892
Don't know about a binary tree, but a binary search will reduce the number of searches to log2 n, i.e. if you have an array of 256 numbers it will do 8 searches. Basic implementation would be:

Code: [Select]
// For an array of 100 numbers, call with binsearch(n, 0, 99);

int binsearch(int n, int a, int b)
{
  if(a == b)
    return a;

  int mid = a + (b-a)/2;
 
  if(n < array[mid])
    return binsearch(n, a, mid);
  else
    return binsearch(n, mid+1, b);
}

EDIT: this binary search assumes the array is sorted in ascending order.
An elegant search algorithm, but unsuitable for my application as I'm not searching for a specific value, but a boundary :)
Title: Re: Programming question! :)
Post by: bloodline on April 17, 2012, 03:21:48 PM
Hmmm, looking around the interwebs suggest that using Staf's ternary operator based code might compile to more efficient code... I'll have to implement both and look at the Asm :)
Title: Re: Programming question! :)
Post by: Jose on April 17, 2012, 03:55:07 PM
Is the size between boundaries constant ? (i.e. is the total nr. of ranks a multiple of the size of one rank).
Title: Re: Programming question! :)
Post by: bloodline on April 17, 2012, 03:58:34 PM
Quote from: Jose;689053
Is the size between boundaries constant ? (i.e. is the total nr. of ranks a multiple of the size of one rank).
No, for the sake of argument the boundaries are somewhat arbitrary... In reality they should scale geometrically in most cases (but not all, due to mechanical requirements).

-edit-
The values I used in my example were real, and if you were to plot them on a graph you should see the beginnings of a curve, here is more of the sequence:

5859
6525
7342
8371
9766
11719
14648
19531
29297

You get the idea :)
Title: Re: Programming question! :)
Post by: Trev on April 17, 2012, 04:33:28 PM
If the compiler is at all recent, I'd expect the trigraph and the function (inlined) to produce the same code. Use the function. :-) (Or put the trigraph in a function.)

I know this isn't Amiga coding, but as an aside, I really miss utilitybase.com. I lost interest in my Amigas when it shut down....
Title: Re: Programming question! :)
Post by: bloodline on April 17, 2012, 05:10:43 PM
Quote from: Trev;689063
If the compiler is at all recent, I'd expect the trigraph and the function (inlined) to produce the same code. Use the function. :-) (Or put the trigraph in a function.)

I know this isn't Amiga coding, but as an aside, I really miss utilitybase.com. I lost interest in my Amigas when it shut down....
This is slightly related to Amiga programming... Since much of coding for tr Amiga was trying to squeeze every last drop of performance from decidedly weak CPUs... At least it is now :)

Also many people on this site have expressed an interest in learning to program, they would be wise to read threads like these :)
Title: Re: Programming question! :)
Post by: Leffmann on April 17, 2012, 05:47:59 PM
Quote from: bloodline;689044
An elegant search algorithm, but unsuitable for my application as I'm not searching for a specific value, but a boundary :)


Actually it's adjusted to do exactly what you want, and can even be optimized further.
Title: Re: Programming question! :)
Post by: bloodline on 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!
Title: Re: Programming question! :)
Post by: Zac67 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.
Title: Re: Programming question! :)
Post by: Fats 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.
Title: Re: Programming question! :)
Post by: Jose 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)).
Title: Re: Programming question! :)
Post by: bloodline 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 :)
Title: Re: Programming question! :)
Post by: Thorham 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 ;)
Title: Re: Programming question! :)
Post by: Zac67 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...