From owner-freebsd-hackers  Tue Apr 29 09:50:53 1997
Return-Path: <owner-hackers>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.5/8.8.5) id JAA25475
          for hackers-outgoing; Tue, 29 Apr 1997 09:50:53 -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 JAA25424
          for <hackers@hub.freebsd.org>; Tue, 29 Apr 1997 09:50:40 -0700 (PDT)
Received: by dg-rtp.dg.com (5.4R3.10/dg-rtp-v02)
	id AA22908; Tue, 29 Apr 1997 12:50:08 -0400
Received: from ponds by dg-rtp.dg.com.rtp.dg.com; Tue, 29 Apr 1997 12:50 EDT
Received: from lakes.water.net (lakes [10.0.0.3]) by ponds.water.net (8.8.5/8.7.3) with ESMTP id MAA10028; Tue, 29 Apr 1997 12:10:46 -0400 (EDT)
Received: (from rivers@localhost) by lakes.water.net (8.8.5/8.6.9) id MAA00794; Tue, 29 Apr 1997 12:17:25 -0400 (EDT)
Date: Tue, 29 Apr 1997 12:17:25 -0400 (EDT)
From: Thomas David Rivers <ponds!rivers@dg-rtp.dg.com>
Message-Id: <199704291617.MAA00794@lakes.water.net>
To: ponds!zeta.org.au!bde, michaelh@cet.co.jp
Subject: Re: namei & hash functions
Cc: ponds!hub.freebsd.org!hackers, ponds!atrad.adelaide.edu.au!msmith
Content-Type: text
Sender: owner-hackers@FreeBSD.ORG
X-Loop: FreeBSD.org
Precedence: bulk

> 
> On Sun, 27 Apr 1997, Bruce Evans wrote:
> 
> > The mask version is the original 4.4Lite version.  The prime version is
> > supposed to be a FreeBSD enhancement.  One would hope that whoever changed
> > it did extensive tests :-).
> 
> 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.

	- Dave Rivers -