Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Challenge for Feeb: dealing with large numbers in C Date: Wed, 23 Oct 2019 07:18:16 -0700 Organization: A noiseless patient Spider Lines: 66 Message-ID: <861rv3h7fb.fsf@linuxsc.com> References: <8736fmz455.fsf@bsb.me.uk> <87wocxy7ro.fsf@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="09129d99e56165cafc27964696c7f4e6"; logging-data="32039"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19x/J3du2973o0m93k3zHnbD1eRjLHjdTg=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:yCaNKdNozZZICJ5UDc4vSOcAbRM= sha1:wB2UhZtIlRTbhD6SySZ94WI6YmI= Xref: csiph.com comp.lang.c:147174 Ben Bacarisse writes: > DFS writes: > >> On 10/21/2019 8:15 AM, Ben Bacarisse wrote: >> >>> DFS writes: >>> >>>> superincomprehensibleness 2116343913154240100000000000000000000 >>>> antidisestablishmentarianism 10816738360843397000000000000000000000 >>>> microspectrophotometrically 5063607945377863500000000000000000000000 >>>> dichlorodiphenyltrichloroetha 29387878280664888000000000000000000000000 >>>> hydroxydesoxycorticosterone 260918185927817140000000000000000000000000 >>>> hydroxydehydrocorticosterone 354994003426527000000000000000000000000000 >>>> cyclotrimethylenetrinitramine >>>> {} 1816546187380119700000000000000000000000000 >>>> trinitrophenylmethylnitramine >>>> {} 286030059853623620000000000000000000000000000 >>>> >>>> >>>> It's looking like prime products is not the right hash function for a >>>> table of only 370K entries. >>> >>> I'm not sure you are using the right terminology. >> >> wiki says "A hash function is any function that can be used to map >> data of arbitrary size to fixed-size values." > > That's a reasonable stab at a definition. > >> I don't see why the hashes have to be of equal size for the generator >> function to be considered a hash function. Or is that just how the >> term evolved? > > I'd say so, yes. But the key point here is that a good hash function > will not preserve any useful property of the strings. A good hash > function give a wildly different result if two different letters are > swapped. To me a hash function is any deterministic single-valued function that produces a fixed-sized, integer-valued output (usually with a dense output space though not necessarily). The key property, apart from the fixed-size integer output, is that if the hash values are different then the input values must be different. Whatever other properties a hash function might or might not have depend on the application. A good example is a Zobrist hash https://en.wikipedia.org/wiki/Zobrist_hashing which has the property that small changes in the input allow easy re-computation of the hash value. Certainly there are applications where we would like wildly different outputs for two inputs with only a single pair of swapped letters. As I use the term though (and I believe this is fairly common but I have made no effort to confirm that), it is perfectly appropriate to call a function that maps anagrams to the same[1] output value a hash function. Note further that we can do both at once - a single hash function with a 128-bit output could have 64 bits that would match for anagrams, and 64 bits that would give very different results for words with letters swapped. Which choice makes sense depends on how the hashing is being used, but all of them count, I would say, as hash functions. [1] Either usually the same, or assuming a bounded input space.