Rapid multiplication
I am writing code for a microprocessor with fast integer arithmetic and not so fast float arithmetic. I need to divide an integer by a number from 1 to 9 and convert the result back to an integer.
I made a floating point array with elements like 0, 1, 0.5, 0.3333, etc. But I think there are MAGIC constants (e.g. 0x55555556) for numbers other than (1/3).
What are these numbers?
source to share
If the divide instruction on your microcontroller is fast enough, use that. If you want the fractional part of the result, you can use the remainder; on most architectures, the division instruction puts the factor in one register and the others in another.
If your division instruction is not fast enough, but your multiplication instruction, you can use the following technique (and it sounds like it was the technique you are using). In most architectures, multiplying a 32-bit number by another 32-bit number produces a 64-bit result; the more significant half is stored in one register, and the less significant half is stored in another register. You can take advantage of this by realizing that dividing by n is the same as multiplying by (2 ^ 32) / n and then accepting more significant 32 bits of the result. In other words, if you want to divide by 3, you can instead multiply by 0x100000000 / 3 = 0x55555555 and then take the more significant 32 bits of the result.
What you are doing here is indeed a form of fixed point arithmetic. Take a look at the Wikipedia article for more information.
source to share
My guess is that based on the microcontroller tag, you don't have fast integer division. My answer is also for unsigned values - it will work for signed values, you just need to limit the numbers used in the complex bit below.
Good start is divisible by 2, 4, and 8. This can be done with right shifts of 1, 2 and 3 bits, respectively, if your processor has a logical shift instruction to the right.
Second, dividing by 1 is just storing the number as-is. It just goes away, 3, 5, 6, 7 and 9.
This is where the bit begins:
For other numbers, you can use the fact that division can be replaced by multiplication and shift.
Let's say you have a 16-bit processor. To divide by N, you multiply by 256 / N and shift the right 8 bits:
N = 3, multiply by 85
N = 5, multiply by 51
N = 6, multiply by 43
N = 7, multiply by 37
N = 9, multiply by 28
Take a random example from 72/5. Multiply 72 by 51 to get 3672, then shift the right 8 bits to get 14.
For this to work, your numbers you are using must not overflow 16 bits. Since your worst case is multiplied by 85, you can handle numbers up to 771.
The reason this works is because the 8-bit right side is the same as dividing by 256, and:
m * (256 / n) / 256
= m / (n / 256) / 256
= m / n * 256 / 256
= m / n * (256 / 256)
= m / n
If you have a 32-bit processor, the values and ranges change slightly since this is 65536 / N:
N = 3, multiply by 21,846, right shift 16 bits, max value roughly 196,600.
N = 5, multiply by 13,108.
N = 6, multiply by 10,923.
N = 7, multiply by 9,363.
N = 9, multiply by 7,282.
Again, let's pick a random 20,000/7: 20,000 multiplied by 9.363 is 187,260,000, and when you're right shift those 16 bits, you get 2.857 - the real result is 2.857.
The following C test program shows the precision values for the given values. It uses signed values, so it is only good up to 98,000, but you can see that the largest error is 1 and that it occurs at the low point of 13.110 (only 0.008% error).
#include <stdio.h>
int res[5] = {0};
int low[5] = {-1,-1,-1,-1,-1};
int da[] = {3,5,6,7,9};
int ma[] = {21846,13108,10923,9363,7282};
int main (void) {
int n, i;
for (n = 0; n < 98000; n++) {
for (i = 0; i < sizeof(da)/sizeof(da[0]); i++) {
int r1 = n / da[i];
int r2 = (n * ma[i])>>16;
int dif = abs (r1-r2);
if (dif >= 5) {
printf ("%d / %d gives %d and %d\n", n, da[i], r1, r2);
return 1;
}
res[dif]++;
if (low[dif] == -1) {
low[dif] = n;
}
}
}
for (i = 0; i < sizeof(res)/sizeof(res[0]); i++) {
printf ("Difference of %d: %6d, lowest value was %6d\n", i, res[i], low[i]);
}
return 0;
}
Output:
Difference of 0: 335874, lowest value was 0
Difference of 1: 154126, lowest value was 13110
Difference of 2: 0, lowest value was -1
Difference of 3: 0, lowest value was -1
Difference of 4: 0, lowest value was -1
source to share
Dividing an integer by an integer constant can be replaced with a combination of shift and multiplication. See this optimization guide for details . Of course, this is useful if it acts faster on the chip of interest.
source to share