From owner-freebsd-hackers  Tue Apr 29 12:20:58 1997
Return-Path: <owner-hackers>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.5/8.8.5) id MAA04247
          for hackers-outgoing; Tue, 29 Apr 1997 12:20:58 -0700 (PDT)
Received: from dg-rtp.dg.com (dg-rtp.rtp.dg.com [128.222.1.2])
          by hub.freebsd.org (8.8.5/8.8.5) with SMTP id MAA04237
          for <hackers@hub.freebsd.org>; Tue, 29 Apr 1997 12:20:51 -0700 (PDT)
Received: by dg-rtp.dg.com (5.4R3.10/dg-rtp-v02)
	id AA06879; Tue, 29 Apr 1997 15:20:06 -0400
Received: from ponds by dg-rtp.dg.com.rtp.dg.com; Tue, 29 Apr 1997 15:20 EDT
Received: from lakes.water.net (lakes [10.0.0.3]) by ponds.water.net (8.8.5/8.7.3) with ESMTP id OAA14347; Tue, 29 Apr 1997 14:08:58 -0400 (EDT)
Received: (from rivers@localhost) by lakes.water.net (8.8.5/8.6.9) id OAA01477; Tue, 29 Apr 1997 14:15:37 -0400 (EDT)
Date: Tue, 29 Apr 1997 14:15:37 -0400 (EDT)
From: Thomas David Rivers <ponds!rivers@dg-rtp.dg.com>
Message-Id: <199704291815.OAA01477@lakes.water.net>
To: ponds!labinfo.iet.unipi.it!luigi, ponds!lakes.water.net!rivers
Subject: Re: namei & hash functions
Cc: ponds!zeta.org.au!bde, ponds!hub.freebsd.org!hackers,
        ponds!cet.co.jp!michaelh, ponds!atrad.adelaide.edu.au!msmith
Content-Type: text
Sender: owner-hackers@FreeBSD.ORG
X-Loop: FreeBSD.org
Precedence: bulk

> 
> > > Umm.  I didn't notice it in the logs.  Just curious how many integer mults
> > > by 33 equal a integer mod by a prime? 
> > > 
> > > Mike Hancock
> > 
> >  Well, hmm, let's see.
> > 
> >  A multiply by 33 becomes a shift-left 5 and an add.
> > 
> >  A mod by a prime is going to involve a division (there's not
> > much else you can do with a prime number...)  which will be
> > _considerably_ slower; possibly involving 32 shifts and as many
> > subtracts (although more likely around 16 or so.)
> > 
> >  So; my answer would be "lots"; around 16 or so.
> 
> not really, computing r = x mod p where p = 2^n +/- 1 are pretty easy:
> 
> For p = 2^n - 1:
> 
> 	x = c_1 2^n + c_2  = c_1 ( 2^n - 1 ) + c_2 + c_1
> 
>     since c_1 and c_2 are simply computed by shift and masking,
>     your r is simply  ( c_2 + c_1 ) mod p, and this is simple to
>     compute. BTW this is the algorithm used for TCP checksums where
>     p=2^16-1
> 
> For p = 2^n + 1 things are not much different:
> 
> 	x = c_1 2^n + c_2  = c_1 ( 2^n + 1 ) + c_2 - c_1
> 
>     again you reduce the problem to the computation of c_2 - c_1 mod p
>     which is relatively simple to do.
> 
> 	Cheers
> 	Luigi

 Hey - that's pretty sweet...

 Are there some nice prime numbers that are one-off from 2^n?

	- Dave R. -