Amiga.org
Operating System Specific Discussions => Other Operating Systems => Topic started 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):
_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?

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)

How long is that list exactly? If it's not too large you can use a table, which would certainly be the fastest way.

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

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

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

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

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

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

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

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

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

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:
rank =
(num<4185) ? 4 :
(num<4507) ? 3 :
(num<4883) ? 2 :
(num<5327) ? 1 :
0;
greets,
Staf.

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

Threads like this are what makes A.org great. People helping people out.

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?

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

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

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

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

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 + (ba)/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.

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

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 + (ba)/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 :)

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

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

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

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

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

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.

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!

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.

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

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

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

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

:) Reminds me of when I tried to calculate the Mandelbrot set without any(!) multiplications  it was hideously fast on a nonFPUd 68000 (for the time) but the precision was really crap  not surprising, I used a 16 bit table of squares together with (a+b)^2a^2b^2=2ab. 128KB was no problem but a somewhat usable 32 bit table would take 16 GB  still waiting for that to come around...