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 Message-ID: <Pine.SV4.3.95.970430100841.9936A-100000@parkplace.cet.co.jp> In-Reply-To: <199704291815.OAA01477@lakes.water.net>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.SV4.3.95.970430100841.9936A-100000>