»

[bloodline]

Originally Posted by Duce

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?

[Zac67]

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

[Jose]

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

[bloodline]

Originally Posted by Zac67

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]

Originally Posted by Jose

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

[Leffmann]

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:

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

[smerf]

Originally Posted by 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):

_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

[bloodline]

Originally Posted by Leffmann

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:

// 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

[Jose]

Is the size between boundaries constant ? (i.e. is the total nr. of ranks a multiple of the size of one rank).

[bloodline]

Originally Posted by Jose

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

[Trev]

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

[bloodline]

Originally Posted by Trev

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

[Leffmann]

Originally Posted by bloodline

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.

[bloodline]

Originally Posted by Leffmann

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!