Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147159
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Challenge for Feeb: dealing with large numbers in C |
| Date | 2019-10-22 00:54 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87wocxy7ro.fsf@bsb.me.uk> (permalink) |
| References | <e_4rF.285583$iJ2.198603@fx47.iad> <ld2qqedn61hgi25fa0602tle88oobhmspf@4ax.com> <Yq9rF.26213$kV2.22694@fx22.iad> <8736fmz455.fsf@bsb.me.uk> <nZmrF.306585$LC2.229987@fx45.iad> |
DFS <nospam@dfs.com> writes:
> On 10/21/2019 8:15 AM, Ben Bacarisse wrote:
>> DFS <nospam@dfs.com> 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.
>> You appear to be
>> looking for anagrams with this plan that two strings that are anagrams
>> will have the same product of primes. That's a reasonable plan,
>
> It's more than reasonable: it's the law!
>
> https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
No that's just why it works! I say no more than it's "reasonable"
because I think there are probably better methods (it's not easy to be
sure without knowing the full requirements, including any possible
future developments).
> Another reasonable and even easier method is to sort the letters of
> the words in ascending or descending order.
Indeed. There are lots of ways to do this, but counting the letters has
some useful properties that might be important depending on where you
are going with this program.
<cut>
>> What you are calculating is some function of the string
>> that ignores letter order but respects letter frequency.
>
> Yes.
>
>> An alternative "hash" would be to count the letters and store the counts
>> in some array. You could pack the counts two to a byte with four bits
>> (allowing a word to have a letter repeated up to 15 times) or even three
>> bits if space was really at a premium.
>
> That sounds pretty simple, can you post the code to do it?
One way:
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#define N_LETTERS ('z' - 'a' + 1)
struct lcount {
unsigned char count[N_LETTERS/2];
};
bool count_letters(const char *str, struct lcount *lcount)
{
unsigned char count[UCHAR_MAX] = {0};
for (const unsigned char *cp = (const void *)str; *cp; cp++)
count[*cp]++;
for (size_t i = 0; i < sizeof lcount->count; i++) {
int n1 = count['a' + 2*i], n2 = count['a' + 2*i + 1];
if (n1 > 0xf || n2 > 0xf)
return false;
lcount->count[i] = (n1 << 4) + n2;
}
return true;
}
void print_lcount(const struct lcount *lcount)
{
for (size_t i = 0; i < sizeof lcount->count; i++)
printf("%02x", lcount->count[i]);
}
int main(int argc, char **argv)
{
size_t max_len = 0;
for (int a = 1; a < argc; a++) {
size_t l = strlen(argv[a]);
if (l > max_len) max_len = l;
}
for (int a = 1; a < argc; a++) {
printf("%*s: ", (int)max_len, argv[a]);
struct lcount lc;
if (count_letters(argv[a], &lc))
print_lcount(&lc);
else printf("letter count out of range.");
putchar('\n');
}
}
> Once you generate those hashes, how do you search for them?
They're not really hashes. The mapping is very carefully constructed to
preserve data. A hash function is carefully constructed /not/ to.
Ironically, the fastest way to search them would be to use a real hash
table (by hashing the letter count data), but it's unlikely to be worth
it given that searching a list of 370K values (even quite complex ones)
is going to be, as you say below, quite fast.
> For my little anagram finder, I just do a for..loop and match on the
> prime product. It is blazing fast in C:
The trouble is you are missing some words where the product can't
represented exactly as a double. Mind you, it would still be fast even
if you used some big number format. You don't even need a full big
number implementation. The largest number you need seems to be
286030059853623711806692899673855354612258762
which can be represented in five 32-bit "digits" or "limbs" and the only
operation you need is multiplication by a small number. That could be
done in a few lines of C.
Every once in a while, comp.lang.c has a "let's write a program" thread.
This could be one of those, if we had a more tightly specified problem.
There are lots of way to do this and it might be fun to compare...
--
Ben.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 18:12 -0400
Re: Challenge for Feeb: dealing with large numbers in C Barry Schwarz <schwarzb@delq.com> - 2019-10-20 18:33 -0700
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 23:16 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-21 13:15 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 14:40 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-22 00:54 +0100
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-22 10:05 +0200
Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-23 07:18 -0700
Re: Challenge for Feeb: dealing with large numbers in C Manfred <noname@invalid.add> - 2019-10-26 20:01 +0200
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-26 17:50 -0400
Re: Challenge for Feeb: dealing with large numbers in C Manfred <noname@add.invalid> - 2019-10-28 16:33 +0100
Re: Challenge for Feeb: dealing with large numbers in C Barry Schwarz <schwarzb@delq.com> - 2019-10-21 07:56 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 16:46 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 14:57 -0400
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 20:53 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 16:05 -0400
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 21:12 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 20:08 -0400
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-22 10:27 +0200
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-22 19:45 +0100
Re: Challenge for Feeb: dealing with large numbers in C Eli the Bearded <*@eli.users.panix.com> - 2019-10-22 19:58 +0000
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-23 11:46 -0400
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-23 20:02 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 01:38 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-23 22:10 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ike Naar <ike@sdf.lonestar.org> - 2019-10-24 07:24 +0000
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 09:29 -0400
Re: Challenge for Feeb: dealing with large numbers in C James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-10-24 08:45 -0700
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 11:56 -0400
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-24 09:13 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 18:28 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 10:36 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 09:26 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 18:29 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 14:38 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 21:30 +0100
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-24 11:30 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 20:36 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 21:34 +0100
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-24 22:42 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 18:59 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-25 02:48 +0100
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-26 04:33 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 17:21 +0100
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-26 18:47 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 23:24 +0100
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-27 00:29 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 01:58 +0100
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-27 12:02 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 02:08 +0000
Re: Challenge for Feeb: dealing with large numbers in C Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-10-26 14:29 -0600
Re: Challenge for Feeb: dealing with large numbers in C Keith Thompson <kst-u@mib.org> - 2019-10-26 13:36 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-26 22:06 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 23:04 +0100
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-27 12:49 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 18:20 +0000
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-27 22:45 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 00:08 +0000
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-27 14:57 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 01:08 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 01:44 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 02:31 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 10:42 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 12:45 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 17:39 +0000
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-28 20:31 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 20:22 +0000
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-28 22:07 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 22:22 +0000
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-29 10:17 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 11:21 +0000
Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-28 11:05 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 19:26 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 21:08 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 21:57 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 23:59 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 00:53 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 01:09 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 01:32 +0000
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-28 22:44 -0400
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 03:05 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 11:12 +0000
Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-29 04:19 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 11:47 +0000
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 05:03 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 13:16 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 17:13 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 17:35 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ike Naar <ike@sdf.lonestar.org> - 2019-10-30 07:19 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 16:19 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 16:50 +0000
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 10:03 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 17:13 +0000
Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-29 10:23 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 22:20 +0000
Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-30 03:04 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-30 15:39 +0000
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-30 09:02 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-30 19:35 +0000
Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-30 14:11 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-31 03:34 +0000
Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-04 17:02 -0800
Re: Challenge for Feeb: dealing with large numbers in C Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2019-10-26 12:30 -0400
Re: Challenge for Feeb: dealing with large numbers in C Robert Wessel <robertwessel2@yahoo.com> - 2019-10-26 12:03 -0500
Re: Challenge for Feeb: dealing with large numbers in C Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-10-26 14:25 -0600
Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-24 18:06 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 22:44 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 19:00 -0400
Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 10:20 +0800
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 12:44 +0100
Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 10:24 +0800
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 23:05 -0400
Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 11:32 +0800
Re: Challenge for Feeb: dealing with large numbers in C Autist <autist69@gmail.com> - 2019-10-29 15:15 +0100
csiph-web