Is there a quick way to do a divide by a sum of a power of two? For example, multiplying by 12 is as simple as: (n * 8) + (n * 4), which boils down to two shifts and an add. But is there a quick way to divide by 12? And similar numbers, like 6? Vyvyan

Where N=2...
Example: N * 640 = (N*512) + (N*128) = (N<<9)+(N<<7) = 1280.

The divide, unfortunately does not appear to work this way at all, not that I have found anyway.

Where N=1280 (from above)...
Example: N / 640 = (N/512) = 2.5 ? (N/128) = 10 ...

Also, I have been benchmarking this method with a straigt ''ole multiply. My findings are that this way is a might bit slower than just a straight ''ole multiply.

In the example above, the N * 640 = (N*512)+(N*128) = (N << 9) + (N << 7) is a bit slower than just doing N * 640.

This testing was done on a PII - 233MMX and P3-750 with the same results. The single multiply is a bit faster than two shifts plus one addition.

I do know that if what you will be dividing by is fairly consistent (ie: always or most always 12) you can multiply by the value 1/N. Example: 1/12 = .083333 So: 144 / 12 = 144 * .08333...

You could store the common multipliers in an array or something but then maybe (not sure though) that the lookups + multiply time needed may outweight the straight division (perhaps?)

Regards,
Jumpster

As this is code written for a Z-80 processor, I have no divide operation. Is there a way using shifts and subtracts?

Vyvyan

Well, I suppose you can use subtraction but that has to be ssllooww....

Example: (Source in C for pseudo-definition)

  N / 12 = DoDivide(N, 12);int DoDivide( int N, int div ){  int modulus = N;  int result = 0;  while(++result)  {    modulus = modulus - div;    if (modulus < div) break;  }  return result;}  

Assuming N=173 and div=12 (173/12), This would produce:

173 - 12 = 161 -> result = 1;
161 - 12 = 149 -> result = 2;
149 - 12 = 137 -> result = 3;
137 - 12 = 125 -> result = 4;
125 - 12 = 113 -> result = 5;
113 - 12 = 101 -> result = 6;
101 - 12 = 89 -> result = 7;
89 - 12 = 77 -> result = 8;
77 - 12 = 65 -> result = 9;
65 - 12 = 53 -> result = 10;
53 - 12 = 41 -> result = 11;
41 - 12 = 29 -> result = 12;
29 - 12 = 17 -> result = 13;
17 - 12 = 5 -> result = 14;

Modulus = 5;

14 * 12 = 168 + 5 = 173...

Again, It is going to be very slow... Perhaps someone else has a better idea...?

Regards,
Jumpster

    N / 12 = DoDivide(N, 12);int DoDivide( int N, int div ){  int modulus = N;  int result = 0;  int precision = 5; // Solve to 5-decimal digits  int remmod = 0;  int remainder = 0;  int remres = 0;  while(++result)  {    modulus = modulus - div;    if (modulus < div) break;  }  remmod = modulus;  while(precision--)  {    remres = 0;    remmod = remmod * 10;    while(++remres)    {      remmod = remmod - div;      if (remmod < div) break;    }        remainder = remainder + (remres * (10 ^ precision));  }  return result;}    

I tried to enter this a bit earlier for you but the post failed. Some OLE/DB error...

Anyway, this routine, as slow as it is, would generate the following results for you...

Assuming solving for 173/12:

result = 14 (integer result of division)
remainder = 41666 (decimal result of division)
modulus = 5 (modulus of 173 % 12)

Regards,
Jumpster

Thanks, Jumpster, but I''m still wondering if there isn''t a faster way to do it via shifts and logical ops...

Vyvyan

Vyvyan

My math isn''t too sharp, but perhaps this will help someone with better experience.

n/12 = n/8 - n/x
-> n/12 - n/8 = -n/x
-> 2n/24 - 3n/24 = -n/x
-> -n/24 = -n/x
-> n/24 = n/x
-> (I can''t remember the next step )

But this implies that
n/12 = n/8 - n/24

Which verifies with my hand calculator. This doesn''t seem to help any though, as I can''t seem to find a combination that provides an x that''s a power of two.

Micah

You could use the same algorithm as the paper and pen method. In c++ like this

    int Divide(int dividend, int divisor, int& remainder){	const int numBits=32;	int result=0;	remainder=dividend;	for(int i=numBits-1;i>=0;i--)	{		if(divisor <= (remainder >> i))			result |= (1 << i);		remainder=dividend-result*divisor;	}	return result;}    

There are more operations than Jumpsters method, but on the other hand it will only loop numBits times, while Jumpsters method will loop result times. So if you have a small divisor compared to the dividend my method is faster. But if the divisor and dividend is almost equally sized Jumsters method is faster.

Edited by - fredizzimo on November 17, 2000 4:54:44 PM

quote: Original post by VyvyanBasterd
But is there a quick way to divide by 12? And similar numbers, like 6?

Why, why, why? Have you profiled your program and identified the weak spots? Have you confirmed that your compiler is lame and won''t optimize (x / 12) for you?

Of course, if you have, then ignore me. I just find it sad that so many programmers (and I''ve seen it happen many times) get frustrated trying to optimize things that account for 2% of their program and wonder why their program still runs no faster.....

---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!
---- --- -- -
New York. New York. New York. Texas. Texas. New York. New York. Canada.
---- --- -- -

quote: Original post by mossmoss

Why, why, why? Have you profiled your program and identified the weak spots? Have you confirmed that your compiler is lame and won't optimize (x / 12) for you?

In case you haven't noticed, he's working with a z-80 processor...




Edited by - Jumpster on November 17, 2000 7:09:31 PM