Path: utzoo!attcan!uunet!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!rpi!bu.edu!xylogics!transfer!crackers!m2c!umvlsi!dime!dime.cs.umass.edu!moss From: moss@cs.umass.edu (Eliot Moss) Newsgroups: comp.theory Subject: Re: Hashing help needed Message-ID: Date: 17 Jul 90 14:15:27 GMT References: <2385@uop.uop.edu> <3140002@otter.hpl.hp.com> Sender: news@dime.cs.umass.edu Reply-To: moss@cs.umass.edu Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst) Lines: 33 In-reply-to: phmb@otter.hpl.hp.com's message of 17 Jul 90 06:25:36 GMT The Godel numbering scheme is fine, but the message says to use p1 for computing the modulus, and p1, p2, p3 for the Godel number. It should be clear that the two p1s are different. That is, use some function such as p1^L * p2^W * p3^H to get a unique single value determined from L, W, and H, and then hash by taking the modulus using a largest prime less than or equal to your maximum value. If you prefer not to compute with really large numbers, I note that you can compute (x * y) mod p via ((x mod p) * (y mod p)) mod p. Note also that the raising to a power (p^Q) can be done in time proportional to log Q by computing p^1, p^2, p^4, etc., and accumulating a result that uses the appropriate subset of the powers calculated. There are many variations on this. Finally, rather than a Godel numbering you could use the three dimensional variation of a two dimension numbering that I illustrate diagrammatically: Length Width 0: 0 1 3 6 10 ... 1: 2 4 7 11 ... 2: 5 8 12 ... 3: 9 13 ... ... ... Figuring out the formula for this, and then for three dimensions, is a bit of a pain, but the calculation will be simpler and faster than the Godel number scheme, I believe. Enjoy! Eliot Moss -- J. Eliot B. Moss, Assistant Professor Department of Computer and Information Science Lederle Graduate Research Center University of Massachusetts Amherst, MA 01003 (413) 545-4206; Moss@cs.umass.edu