Programming question! :)

[bloodline]

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?

[bloodline]

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

[bloodline]

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)

[bloodline]

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

[bloodline]

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

[bloodline]

Ahhh! Good call, I'm quite comfortable with usig a function, but I won't forget this either!! Many thanks for your help

[bloodline]

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?

[bloodline]

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

[bloodline]

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

[bloodline]

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

[bloodline]

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

[bloodline]

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

[bloodline]

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

[bloodline]

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!

[bloodline]

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