Welcome, Guest. Please login or register.
Amiga Kit Amiga Store Iridium Banner AMIStore App Store A1200/A600 4xIDE Interface

AuthorTopic: Programming question! :)  (Read 2152 times)

0 Members and 1 Guest are viewing this topic.

Offline bloodline

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
  • Total likes: 0
    • http://www.troubled-mind.com
Re: Programming question! :)
« Reply #15 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?

Offline Zac67

Re: Programming question! :)
« Reply #16 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).
 

Offline Jose

Re: Programming question! :)
« Reply #17 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 :)
\\"We made Amiga, they {bleep}ed it up\\"
 

Offline bloodline

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
  • Total likes: 0
    • http://www.troubled-mind.com
Re: Programming question! :)
« Reply #18 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 :)
« Last Edit: April 16, 2012, 11:03:47 PM by bloodline »
 

Offline bloodline

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
  • Total likes: 0
    • http://www.troubled-mind.com
Re: Programming question! :)
« Reply #19 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 :)

Offline Leffmann

Re: Programming question! :)
« Reply #20 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.
« Last Edit: April 17, 2012, 12:30:41 AM by Leffmann »
 

Offline smerf

Re: Programming question! :)
« Reply #21 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
I have no idea what your talking about, so here is a doggy with a small pancake on his head.

MorphOS is a MAC done a little better
 

Offline bloodline

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
  • Total likes: 0
    • http://www.troubled-mind.com
Re: Programming question! :)
« Reply #22 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 :)

Offline bloodline

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
  • Total likes: 0
    • http://www.troubled-mind.com
Re: Programming question! :)
« Reply #23 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 :)

Offline Jose

Re: Programming question! :)
« Reply #24 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).
\\"We made Amiga, they {bleep}ed it up\\"
 

Offline bloodline

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
  • Total likes: 0
    • http://www.troubled-mind.com
Re: Programming question! :)
« Reply #25 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 :)
« Last Edit: April 17, 2012, 04:13:40 PM by bloodline »
 

Offline Trev

Re: Programming question! :)
« Reply #26 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....
 

Offline bloodline

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
  • Total likes: 0
    • http://www.troubled-mind.com
Re: Programming question! :)
« Reply #27 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 :)

Offline Leffmann

Re: Programming question! :)
« Reply #28 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.
 

Offline bloodline

  • Master Sock Abuser
  • Hero Member
  • *****
  • Join Date: Mar 2002
  • Posts: 12113
  • Total likes: 0
    • http://www.troubled-mind.com
Re: Programming question! :)
« Reply #29 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!