Greetings, Mr. Gilmore, Apparently I fail to understand some aspect of your claim regarding the remainders when 36 is used as a divisor. If I divide each of the numbers from 1 to n by 36, each of the values from 0 to 35 is encountered as a remainder as many times as all other values, provided n is a multiple of 36; if n is not a multiple of 36 then there are n mod 36 remainders that occur (only) one additional time. If 2 and/or 3 appear as remainders more often then there must be some attribute of the distribution of the dividends that causes this. Have I misunderstood your claim, or is there another condition that has been implied (or stated explicitly) that I overlooked? Thank you for any information you can give me.
- mb Mark Boonie z/TPF Development 845-433-4918 (t/l 293-4918) From: John Gilmore <[email protected]> To: [email protected], Date: 11/01/2012 06:19 PM Subject: Re: Curosity Question Sent by: IBM Mainframe Assembler List <[email protected]> If a hashing scheme is working well there is almost no clustering. Suppose we divide by 17, a prime, i.e., use it, in the jargon, as our hashing modulus.. Remainders will have one of the 17 values 0, 1, 2, . . . , 16. Then some goodly number of hashing operations the same or about the same number of of the hash values 0, 1, 2, . . . , 16 are generated, clustering does not occur. For concreteness, suppose we do 170 divisions. Then if clustering does not occur there are about ten remainders having the value 0, about 10 having the value 1, about 10 having the value 2, etc., etc. What happens when the divisor used is composite is that hash values that are prime factors of the divisor occur more frequently than others. For 36 we have 36 = 2 x 2 x 3 x 3, which is usually written 2^2 x 3^2 or 2**2 x 3**2. Its prime factors are 2 and 3; and when it is used as a divisor there are more remainders having the value 2 and the value 3 than there are having other pairs of values. 37, on the other hand, is prime, divisible only by 1 and itself. Its use as a divisor yields no clustering of remainders. Never hesitate to ask notional gurus such questions. A request for a further explanation is always in order. --jg
