Efficient way of computing division by powers of 2

[ngogo]

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?

[cadet1620]

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

[bader]

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

[cadet1620]

Are you talking about mult2n(x, n)? It's just x doubled n times using addition. (With no trickiness required to handle negative value of x!)

Or are you trying to implement Math.mult(x, y)?

Are set and filter the same variable? If not, how is set used and how is filter initialized?

    set = -16384 - 16384;
will assign set the value 1000...0000 binary, which is the 2's complement number -32768. Dividing a negative number by 2 does not do a right shift. For instance -32768/2 = -16384 = 1100...0000.

--Mark

[bader]

yes filter = set (sorry forget to mention that), and yes its just x doubled n times and thats exactly what i needed! (donno how missed this simple thing ^^' ).

 anyway the problem(as you said) was that dividing negative number by 2 do not shift it to right.
 it was worth to try though.


thanks alot,
bader