Optimizing C code to replace % and /

[tectona]

Hi all,

I need ur help to Optimize C code.

I want to know how replace "%" & "/" in C.

In my application I use this two function for finding Reminder & Quotient.

Like

6505/1000 = 6
6505 % 1000 = 505

Plz, give me good logic so I optimize my code

Thanks in advance.........

Regards
Tectona

 

[budhy]

Re: Optimize C Code

I want to know how replace "%" & "/" in C

"%" & "/" is legal arithmatic operator in C, why to replace it?

 

[xxtigerxx]

Optimize C Code

division with power of 2 is simple by left shift
example

6505 / 16
6505>>4
6505 / 1000 = (6505 >> 3)/125

 

[PaulHolland]

Re: Optimize C Code

Hi, Do not try to optimize this. In most C compilers I know this is done very very efficiently. Only a few asm instructions.

If you want to optimize:

Remove:

Multiply functions. unless the value is n^2 * X
Division functions. unless the value is X / n^2
all other math.
Try to replace them with AND or XOR.

Optimize inside loops.

Use look-up tables if possible. but do not use multi-dimentional array's try to stick with one dimension.

FOR: xxtigerxx

A good c-compiler will make the same code for.

X = 6500/16 and X = 6500>>4


Paul.

 

[echo47]

Optimize C Code

I'm guessing that your microcontroller has a slow division opcode, or none at all, and you don't like the code generated by your C compiler. Try searching the 'net for a better compiler, or search for a division algorithm optimized for your specific microcontroller and compiler.

 

[tectona]

Re: Optimize C Code

Thanks for ur support,

I required this optimization for reduce code memory & fast execution.

I use microchip 18f controller , in this controller there is no division instruction so compiler return their own routine for execution this basic arithmatic operation.

I use Hi-Tech PICC18 compiler.

I want know is there any method to findout result using + , - or >> , << , & , | .

Because i my divider is fix say 1000.

Thanks for ur support.

Regards
Tectona

 

[jonw0224]

Optimize C Code

if you are always dividing by 1000 try something like this:

/* Assume dividing a 32 bit number by 1000
    1000 is a 12 bit number */

#define shft (32 - 12)
int i;
int a = 1000 << shft;
int dividend = 6506;
int remainder = dividend;
int quotient = 0;

for(i = shft; i >= 0; i--)
{
   quotient <<= 1;
   if(remainder >= a)
   {
      quotient++;
      remainder -= a;
   }
   a >>= 1; 
}
/* quotient and remainder are correct */

 

[tectona]

Re: Optimize C Code

Hi jonw0224

I execute your code in C compiler(PICC 18) but this code cannot work.

Thanks for your support.

Regards
Tectona

 

[echo47]

Optimize C Code

jonw0224's code requires 32-bit int. Notice the "1000 << shft".
Maybe PICC has smaller int.

 

[jonw0224]

Optimize C Code

echo47,

thanks, using sizeof() would be more general.

-jonathan

 

[artem]

Optimize C Code

xxtigerxx advice is good way to start. you can further suboptimise your code if :
- value of divisor is known and restricted in range
- try to change divider to power of 2 if you can and scale all data to that value, that will give you chance to use logical operations instead of arithmetical
- if seeking for alphanumeric conversion routines, look to bcd conversion routines

Yet , have a lok to book "Algorithms for programmers Ideasa and source codes". I think that is one of the best book on such optimisation subjects. Search google should be available for free , thanks to authors.