Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!asuvax!ncar!ico!haddock!karl
From: karl@haddock.ima.isc.com (Karl Heuer)
Newsgroups: comp.lang.c
Subject: Re: % operator (was Re: count of bits set in a long)
Message-ID: <18457@haddock.ima.isc.com>
Date: 8 Oct 90 20:01:49 GMT
References: <37545@ut-emx.uucp> <3820@goanna.cs.rmit.oz.au> <34281@cup.portal.com> <2859@litchi.bbn.com> <51467@brunix.UUCP> <3417@gmdzi.gmd.de> <121784@linus.mitre.org>
Reply-To: karl@kelp.ima.isc.com (Karl Heuer)
Organization: Interactive Systems, Cambridge, MA 02138-5302
Lines: 12

In article <121784@linus.mitre.org> bs@gauss.UUCP (Robert D. Silverman) writes:
>Here's a simple, well known trick for computing x mod (2^n-1) when x > 0.
>let x = a*2^n + b,  that is partition x into lower and upper n bits...

Note the unstated assumption that x is at most 2n bits wide.  This wasn't true
in the original context.  It can be fixed by iterating the procedure--in fact
this is where that mod came from in the first place: it replaces one or two
folding operations in the modless form of the algorithm.  (Presumably the
original algorithm was being optimized for codespace instead of time, or was
being done on a machine where mod was cheap.)

Karl W. Z. Heuer (karl@kelp.ima.isc.com or ima!kelp!karl), The Walking Lint