From owner-freebsd-hackers  Tue Apr 29 18:15:31 1997
Return-Path: <owner-hackers>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.5/8.8.5) id SAA22506
          for hackers-outgoing; Tue, 29 Apr 1997 18:15:31 -0700 (PDT)
Received: from parkplace.cet.co.jp (parkplace.cet.co.jp [202.32.64.1])
          by hub.freebsd.org (8.8.5/8.8.5) with ESMTP id SAA22498
          for <Hackers@FreeBSD.ORG>; Tue, 29 Apr 1997 18:15:28 -0700 (PDT)
Received: from localhost (michaelh@localhost) by parkplace.cet.co.jp (8.8.5/CET-v2.1) with SMTP id BAA10029; Wed, 30 Apr 1997 01:15:19 GMT
Date: Wed, 30 Apr 1997 10:15:19 +0900 (JST)
From: Michael Hancock <michaelh@cet.co.jp>
To: Thomas David Rivers <ponds!rivers@dg-rtp.dg.com>
cc: FreeBSD Hackers <Hackers@FreeBSD.ORG>
Subject: Re: namei & hash functions
In-Reply-To: <199704291815.OAA01477@lakes.water.net>
Message-ID: <Pine.SV4.3.95.970430100841.9936A-100000@parkplace.cet.co.jp>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-hackers@FreeBSD.ORG
X-Loop: FreeBSD.org
Precedence: bulk

On Tue, 29 Apr 1997, Thomas David Rivers wrote:

> > 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?

8191