# Efficient way of computing division by powers of 2

5 messages
Open this post in threaded view
|

## Efficient way of computing division by powers of 2

 I was wondering whether there is an efficient way of implementing division by powers of 2 would be, not having shifting as part of our language. It seems that checking every bit in the original number and adding it via a bitwise or operator is not much better than normal multiplication (they both run a loop over the length of the register). It only saves some constants. Any ideas for something more efficient?
Open this post in threaded view
|

## Re: Efficient way of computing division by powers of 2

 Administrator This post was updated on . ngogo wrote I was wondering whether there is an efficient way of implementing division by powers of 2 would be, not having shifting as part of our language. The hardware cannot do right shifting so you pretty much stuck with bit testing and addition. You might be able to get some improvement using something like ```// UNTESTED CODE class Math { static Array power2; function int div2n (int x, int n) { // Needs code to deal with negative numbers. Fastest might be to make // a version of the algorithm that only handles negatives. Same as this // but starts with -1 and sets 0's instead of 1's. var int test, set; var int y; // init = 0 // RANGE CHECK n -- return 0 if n>15, call mul2n() if n<0 let set = 1; let test = power2[n]; // global inited in Math.init() while (~(test=0)) { if ((x&test)=test) { let y = y | set; } let test = test+test; // Signed overflow is OK here let set = set+set; // Signed overflow is OK here } return y; } } ```--Mark
Open this post in threaded view
|

## Re: Efficient way of computing division by powers of 2

 hi, what about multiplication? i tried to write similar code but for some reason it does not work. what i did is exactly as the above but i initialized values is follows: y = 0 test = power2[16-n]; set = -16384 - 16384; // meant for the number 100000... and inside the loop i changed: filter = filter + filter; to filter = Math.div2n(filter,1); test = test + test; to test = Math.div2n(test, 1); as far as i understand , what i did should do the multiply (the same logic of the div just reversed). but this did not work for me. maybe the mistake is in "set = -16384 -16384". a help would be appreciated, bader