Re:Modulo optimizations

George Russell wrote:
  >The Alpha does not have integer divide. However as one of the manuals
>points out (I forget the exact URL), you can for unsigned integers
>implement division by any constant as an integer multiplication
>followed by a shift. For example, to divide a 32 bit integer by a 32
>bit integer you do a multiplication by a pre-computed number
>(producing a 64 bit result) followed by a right shift.


Yes, but unfortunately not all divisions by a constant can be treated
like that... A problem occurs when the error after multiplication
could be greater than the pre-computed value you are multiplying with,
forcing a correction step.


Interestingly there exists an algorithm to calculate modulos without
doing 64 bit multiplies (posted a few years ago on comp.sys.arm):


typedef unsigned int u32;


u32 mod3(u32 x)
{
        x *= 0xAAAAAAAB;
        if ((x - 0x55555556) < 0x55555555) return 2;
        return x >> 31;
}


It starts out like a normal division by a constant. Since 0xAAAAAAAB *
3 mod 2 ^ 32 = 1, any multiple of 3 will give a result between 0 and
0xFFFFFFFF / 3 = 0x55555555. Any x with x % 3 = 1 lies in the range
0xAAAAAAAB..0xFFFFFFFF, x % 3 = 2 in 0x55555556..0xAAAAAAAA. A range
test filters out modulo 2 results, while a shift is used to
distinguish between modulo 1 (bit 31 set) and 0 (bit 31 clear)
results.


The drawback of this method is that it is only really useful for small
constants, for larger ones the range search effectively becomes a
division itself!


Wilco

Return to the comp.compilers page.
Search the comp.compilers archives again.