Re: Modulo optimizations

Robert Harley <harley@corton.inria.fr>
21 Oct 1999 00:47:50 -0400

          From comp.compilers
Related articles
Modulo optimizations gmarshal@globalnet.co.uk (Graham Marshall) (1999-10-04)
Re: Modulo optimizations jgk@jgk.org (Joe Keane) (1999-10-11)
Re: Modulo optimizations torbenm@diku.dk (1999-10-13)
Re: Modulo optimizations chase@world.std.com (David Chase) (1999-10-13)
Re: Modulo optimizations ger@informatik.uni-bremen.de (George Russell) (1999-10-14)
Re: Modulo optimizations harley@corton.inria.fr (Robert Harley) (1999-10-14)
Re:Modulo optimizations Wilco.Dijkstra@arm.com (Wilco Dijkstra) (1999-10-19)
Re: Modulo optimizations harley@corton.inria.fr (Robert Harley) (1999-10-21)
Re: Modulo optimizations Peter-Lawrence.Montgomery@cwi.nl (1999-10-27)
| List of all articles for this month |
From: Robert Harley <harley@corton.inria.fr>
Newsgroups: comp.compilers
Date: 21 Oct 1999 00:47:50 -0400
Organization: I.N.R.I.A Rocquencourt
References: 99-10-017 99-10-093
Keywords: arithmetic

Wilco Dijkstra <Wilco.Dijkstra@arm.com> writes:
> 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;
> }


On ARM, where shifts are free, here is another fast method:


static unsigned mod3(unsigned x) {
    unsigned y;
    static const unsigned tab[16] = { 0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0 };


    y = x>>2;
    y += y>>2;
    y += y>>4;
    y += y>>8;
    y += y>>16;


    return tab[x-y*3];
}




The middle part does: y = x * 1/3 rounded down slightly.


Bye,
    Rob.

Post a followup to this message

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