Date: Tue, 29 Apr 1997 14:15:37 -0400 (EDT) From: Thomas David Rivers <ponds!rivers@dg-rtp.dg.com> To: ponds!labinfo.iet.unipi.it!luigi, ponds!lakes.water.net!rivers Cc: ponds!zeta.org.au!bde, ponds!hub.freebsd.org!hackers, ponds!cet.co.jp!michaelh, ponds!atrad.adelaide.edu.au!msmith Subject: Re: namei & hash functions Message-ID: <199704291815.OAA01477@lakes.water.net>
next in thread | raw e-mail | index | archive | help
> > > > 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. -
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199704291815.OAA01477>