Path: utzoo!attcan!uunet!zephyr.ens.tek.com!uw-beaver!mit-eddie!bu.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!hplabs!otter.hpl.hp.com!otter!phmb
From: phmb@otter.hpl.hp.com (Peter Brooks)
Newsgroups: comp.theory
Subject: Re: Hashing help needed
Message-ID: <3140002@otter.hpl.hp.com>
Date: 17 Jul 90 06:25:36 GMT
References: <2385@uop.uop.edu>
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Lines: 41


You have been advised of the impossibility of your request - quarts do
not fit into pint pots, however it is probable that you knew this to
begin with and wish to get the most even spread, or to state the same
condition you wish to have the mimimum number of synonyms. The best way
I know is to use a modified form of Godel numbering ie, produce the
Godel number for your bit of wood and take its modulus within the
bound that you wish to constrain yourself to. How you then resolve
synonym clashes is your affair. In detail:

For your bound (4 digits -> 9999) take the largest prime number, p1, in
less than this. For each dimension, in your case you have three length
width and height, take a prime say p1,p2,p3 in your case. To find your
Godel number G = p1^l * p2 ^ w * p3 ^ h. For integral values of l,w and
h this number is unique. Now to compress this into your range you simply
get your number N = G mod p1. Now for practical measures, you may need
to use the final few digits of your length as otherwise the numbers
become a little large.

Eg. for the range 100, p1 = 97 your bit of wood measures l = 1828.8 mm
by w = 101.6 mm by h = 50.8 mm. for p1 = 2, p2 = 3, p3 = 5 we have
G = 2^288 * 3 ^ 1016 * 5 ^ 508 = 
337750304396705098571122337365999043230482501155685524045168492026139\
7668939363882432430791175603518883885207439163202131321120617573667213\
2410980123910106034401038053639481089220571003629510159559729945385280\
1973536128209216268413114332710640657298341500372170668411203125406938\
6573824240441039039226095004052247924130770443230816718591439248450820\
6784631181023079540800465370207294607439644943551360475114866435096689\
0238356410112741963844888055894318871075292079500904825197270438909441\
2143891224620408901314362522786931325528467005500144923988970790346871\
5326004198319743050965807687775094866975550411680728757346514612436294\
5556640625000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000
G mod 97 = 64
The spread effect is easily seen if we change one measure by 0.1 mm
if w = 101.7 mm the answer is 95 and if h is 50.7 it is 71.

Peter Brooks