Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147130 > unrolled thread
| Started by | DFS <nospam@dfs.com> |
|---|---|
| First post | 2019-10-20 18:12 -0400 |
| Last post | 2019-10-29 15:15 +0100 |
| Articles | 20 on this page of 114 — 19 participants |
Back to article view | Back to comp.lang.c
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
Page 1 of 6 [1] 2 3 4 5 6 Next page →
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-10-20 18:12 -0400 |
| Subject | Challenge for Feeb: dealing with large numbers in C |
| Message-ID | <e_4rF.285583$iJ2.198603@fx47.iad> |
1. assign primes to letters of the alphabet
int primes[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
char *charset = "abcdefghijklmnopqrstuvwxyz";
(a=2,b=3,c=5...x=89,y=97,z=101)
2. calculate the product of the primes for a given word
product of prime factors (pf) variable is an unsigned long long.
#define MAXPF 18446744073709551615
Using print format specifier %llu.
word = deal
i ch prime product
-- -- ----- --------
1. d 7 7
2. e 11 77
3. a 2 154
4. l 37 5698
The prime factor of deal is 5698
No problem here
Now use a big word or lots of letters
afoijdfbxxijetadvabb
i ch prime product
-- -- ----- --------
1. a 2 2
2. f 13 26
3. o 47 1222
4. i 23 28106
5. j 29 815074
6. d 7 5705518
7. f 13 74171734
8. b 3 222515202
9. x 89 19803852978
10. x 89 1762542915042
11. i 23 40538487045966
12. j 29 1175616124333014
13. e 11 12931777367663154
14. t 71 918156193104083934
15. a 2 1836312386208167868
16. d 7 12854186703457175076
18446744073709551615 (max ull)
17. v 79 909825519091492124 (incorrect)
18. a 2 1819651038182984248 (incorrect)
19. b 3 5458953114548952744 (incorrect)
20. b 3 16376859343646858232 (incorrect)
The last calculation sets the prime factor of afoijdfbxxijetadvabb =
16376859343646858232.
Which is wrong, because the 17th calculation should've exceeded the max
value of the unsigned long long data type. Instead, the calculation
returns a lower number (16376859343646858232). The subsequent
iterations return succeedingly larger values.
What do you know about dealing with large numbers in C.
I don't want to deal with 'big int' libraries or anything like that.
I'd actually just like to truncate to 0, or maybe the max size of ull.
But since the calculation won't ever exceed MAXPF I don't see how to
even make the truncate decision.
This large numbers issue shows prime factors isn't a good hash value.
[toc] | [next] | [standalone]
| From | Barry Schwarz <schwarzb@delq.com> |
|---|---|
| Date | 2019-10-20 18:33 -0700 |
| Message-ID | <ld2qqedn61hgi25fa0602tle88oobhmspf@4ax.com> |
| In reply to | #147130 |
On Sun, 20 Oct 2019 18:12:33 -0400, DFS <nospam@dfs.com> wrote:
>
>1. assign primes to letters of the alphabet
>
>int primes[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
> 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
>char *charset = "abcdefghijklmnopqrstuvwxyz";
>
>(a=2,b=3,c=5...x=89,y=97,z=101)
>
>
>
>2. calculate the product of the primes for a given word
>
>product of prime factors (pf) variable is an unsigned long long.
>#define MAXPF 18446744073709551615
>Using print format specifier %llu.
>
>word = deal
>i ch prime product
>-- -- ----- --------
>1. d 7 7
>2. e 11 77
>3. a 2 154
>4. l 37 5698
>The prime factor of deal is 5698
>
>No problem here
>
>
>Now use a big word or lots of letters
>
>afoijdfbxxijetadvabb
>i ch prime product
>-- -- ----- --------
>1. a 2 2
>2. f 13 26
>3. o 47 1222
>4. i 23 28106
>5. j 29 815074
>6. d 7 5705518
>7. f 13 74171734
>8. b 3 222515202
>9. x 89 19803852978
>10. x 89 1762542915042
>11. i 23 40538487045966
>12. j 29 1175616124333014
>13. e 11 12931777367663154
>14. t 71 918156193104083934
>15. a 2 1836312386208167868
>16. d 7 12854186703457175076
> 18446744073709551615 (max ull)
>17. v 79 909825519091492124 (incorrect)
>18. a 2 1819651038182984248 (incorrect)
>19. b 3 5458953114548952744 (incorrect)
>20. b 3 16376859343646858232 (incorrect)
>
>The last calculation sets the prime factor of afoijdfbxxijetadvabb =
>16376859343646858232.
>
>Which is wrong, because the 17th calculation should've exceeded the max
>value of the unsigned long long data type. Instead, the calculation
>returns a lower number (16376859343646858232). The subsequent
>iterations return succeedingly larger values.
>
>What do you know about dealing with large numbers in C.
>
>I don't want to deal with 'big int' libraries or anything like that.
>
>I'd actually just like to truncate to 0, or maybe the max size of ull.
>
>But since the calculation won't ever exceed MAXPF I don't see how to
>even make the truncate decision.
>
>This large numbers issue shows prime factors isn't a good hash value.
Unsigned arithmetic never overflows. If the mathematical result of
the operation exceeds the maximum value the target can hold, then the
value is repeatedly reduced by (max_value+1) until it no exceeds the
maximum. You can visualize it as simply ignoring the high order bits.
One way to determine if a product of two factors will exceed the
maximum value is to divide the max by either of the factors and see if
the quotient is smaller than the other factor.
--
Remove del for email
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-10-20 23:16 -0400 |
| Message-ID | <Yq9rF.26213$kV2.22694@fx22.iad> |
| In reply to | #147139 |
On 10/20/2019 9:33 PM, Barry Schwarz wrote: > Unsigned arithmetic never overflows. If the mathematical result of > the operation exceeds the maximum value the target can hold, then the > value is repeatedly reduced by (max_value+1) until it no exceeds the > maximum. You can visualize it as simply ignoring the high order bits. > > One way to determine if a product of two factors will exceed the > maximum value is to divide the max by either of the factors and see if > the quotient is smaller than the other factor. Thanks for the explanation. I just changed the datatype to double and I got the enormous prime products 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.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-10-21 13:15 +0100 |
| Message-ID | <8736fmz455.fsf@bsb.me.uk> |
| In reply to | #147143 |
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. 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, but it will be "big nums" (as they are often called). An actual hash function (as the term is usually used) won't help you find anagrams because "hash" and "sash" will usually map to different hash values. What you are calculating is some function of the string that ignores letter order but respects letter frequency. 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. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-10-21 14:40 -0400 |
| Message-ID | <nZmrF.306585$LC2.229987@fx45.iad> |
| In reply to | #147149 |
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." 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? > 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 Another reasonable and even easier method is to sort the letters of the words in ascending or descending order. > but it will be "big nums" (as they are often called). Way bigger than necessary for use with a dictionary of 370K words. > An actual hash function (as the term is usually used) won't help you > find anagrams because "hash" and "sash" will usually map to different > hash values. As they should; they aren't anagrams of each other. > 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? Once you generate those hashes, how do you search for them? For my little anagram finder, I just do a for..loop and match on the prime product. It is blazing fast in C: Searching for anagrams of 'players'... asperly parleys parsley pyrales replays sparely splayer 7 anagram(s) found in 0.00288s
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-10-22 00:54 +0100 |
| Message-ID | <87wocxy7ro.fsf@bsb.me.uk> |
| In reply to | #147152 |
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.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2019-10-22 10:05 +0200 |
| Message-ID | <qomd81$r57$1@dont-email.me> |
| In reply to | #147159 |
On 22/10/2019 01:54, Ben Bacarisse wrote: > 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. Hash functions can happily be used to map fixed-size data to smaller fixed-size values. Arbitrary size data, such as strings, are common sources for a hash function, but it could just as well be, say, 8-byte double's. The key point is to take bigger bits of data and map them to smaller bits of data in a way that attempts to preserve uniqueness over the domain of source data. (Occasionally hash functions can also be used to /increase/ the size of the data - such as using sha512 to generate deterministic but unpredictable data blocks from a short keyword.) > >> 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. It aims to preserve one vital property - the equality or inequality of the strings.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2019-10-23 07:18 -0700 |
| Message-ID | <861rv3h7fb.fsf@linuxsc.com> |
| In reply to | #147159 |
Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> 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.
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.
[toc] | [prev] | [next] | [standalone]
| From | Manfred <noname@invalid.add> |
|---|---|
| Date | 2019-10-26 20:01 +0200 |
| Message-ID | <qp21m7$11sj$1@gioia.aioe.org> |
| In reply to | #147152 |
On 10/21/19 8:40 PM, DFS wrote: > wiki says "A hash function is any function that can be used to map data > of arbitrary size to fixed-size values." > > 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 believe what is meant here is that hash functions map data to fixed-limit values, i.e. they map arbitrary values to e.g. 16-bit or 32-bit values. Hash values need to be of fixed size as long as they are used as indexes into the hash table.
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-10-26 17:50 -0400 |
| Message-ID | <we3tF.151093$O_.115836@fx39.iad> |
| In reply to | #147252 |
On 10/26/2019 2:01 PM, Manfred wrote: > On 10/21/19 8:40 PM, DFS wrote: >> wiki says "A hash function is any function that can be used to map >> data of arbitrary size to fixed-size values." >> >> 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 believe what is meant here is that hash functions map data to > fixed-limit values, i.e. they map arbitrary values to e.g. 16-bit or > 32-bit values. > Hash values need to be of fixed size as long as they are used as indexes > into the hash table. Why do they need to be of fixed size?
[toc] | [prev] | [next] | [standalone]
| From | Manfred <noname@add.invalid> |
|---|---|
| Date | 2019-10-28 16:33 +0100 |
| Message-ID | <qp71o0$1div$1@gioia.aioe.org> |
| In reply to | #147267 |
On 10/26/2019 11:50 PM, DFS wrote: > On 10/26/2019 2:01 PM, Manfred wrote: >> On 10/21/19 8:40 PM, DFS wrote: >>> wiki says "A hash function is any function that can be used to map >>> data of arbitrary size to fixed-size values." >>> >>> 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 believe what is meant here is that hash functions map data to >> fixed-limit values, i.e. they map arbitrary values to e.g. 16-bit or >> 32-bit values. >> Hash values need to be of fixed size as long as they are used as >> indexes into the hash table. > > > Why do they need to be of fixed size? Because they are used as indices into a finite-size table. I.e. for a 64K hash table they have to be 16bit unsigned integers.
[toc] | [prev] | [next] | [standalone]
| From | Barry Schwarz <schwarzb@delq.com> |
|---|---|
| Date | 2019-10-21 07:56 -0700 |
| Message-ID | <4nhrqeljnkjk0p397q28fatgva9m943qsg@4ax.com> |
| In reply to | #147143 |
On Sun, 20 Oct 2019 23:16:13 -0400, DFS <nospam@dfs.com> wrote: >On 10/20/2019 9:33 PM, Barry Schwarz wrote: > > >> Unsigned arithmetic never overflows. If the mathematical result of >> the operation exceeds the maximum value the target can hold, then the >> value is repeatedly reduced by (max_value+1) until it no exceeds the >> maximum. You can visualize it as simply ignoring the high order bits. >> >> One way to determine if a product of two factors will exceed the >> maximum value is to divide the max by either of the factors and see if >> the quotient is smaller than the other factor. > > >Thanks for the explanation. I just changed the datatype to double and I >got the enormous prime products > > superincomprehensibleness 2116343913154240100000000000000000000 > antidisestablishmentarianism 10816738360843397000000000000000000000 > microspectrophotometrically 5063607945377863500000000000000000000000 > dichlorodiphenyltrichloroetha 29387878280664888000000000000000000000000 > hydroxydesoxycorticosterone 260918185927817140000000000000000000000000 > hydroxydehydrocorticosterone 354994003426527000000000000000000000000000 > cyclotrimethylenetrinitramine 1816546187380119700000000000000000000000000 > trinitrophenylmethylnitramine >286030059853623620000000000000000000000000000 I hope you realize that none of those values is exact. >It's looking like prime products is not the right hash function for a >table of only 370K entries. -- Remove del for email
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-21 16:46 +0100 |
| Message-ID | <3pkrF.1790269$HWr.573547@fx36.am4> |
| In reply to | #147143 |
On 21/10/2019 04:16, DFS wrote:
> On 10/20/2019 9:33 PM, Barry Schwarz wrote:
>
>
>> Unsigned arithmetic never overflows. If the mathematical result of
>> the operation exceeds the maximum value the target can hold, then the
>> value is repeatedly reduced by (max_value+1) until it no exceeds the
>> maximum. You can visualize it as simply ignoring the high order bits.
>>
>> One way to determine if a product of two factors will exceed the
>> maximum value is to divide the max by either of the factors and see if
>> the quotient is smaller than the other factor.
>
>
> Thanks for the explanation. I just changed the datatype to double and I
> got the enormous prime products
>
> superincomprehensibleness 2116343913154240100000000000000000000
> antidisestablishmentarianism 10816738360843397000000000000000000000
> microspectrophotometrically 5063607945377863500000000000000000000000
> dichlorodiphenyltrichloroetha 29387878280664888000000000000000000000000
> hydroxydesoxycorticosterone 260918185927817140000000000000000000000000
> hydroxydehydrocorticosterone 354994003426527000000000000000000000000000
> cyclotrimethylenetrinitramine
> 1816546187380119700000000000000000000000000
> trinitrophenylmethylnitramine
> 286030059853623620000000000000000000000000000
These values are not right as has already been stated.
The correct values are:
superincomprehensibleness :
2116343913154240043567072445807789615
antidisestablishmentarianism :
10816738360843396874796178492197077328
microspectrophotometrically :
5063607945377863816547272523387703764750
dichlorodiphenyltrichloroetha :
29387878280664889590552354940915144150850
hydroxydesoxycorticosterone :
260918185927817220516363619911470787340775
hydroxydehydrocorticosterone :
354994003426527102138061051206064480579525
cyclotrimethylenetrinitramine :
1816546187380118721203679993771742512144550
trinitrophenylmethylnitramine :
286030059853623711806692899673855354612258762
These are as reported in the C program below (which formats them to
avoid line-wrap when posting).
> It's looking like prime products is not the right hash function for a
> table of only 370K entries.
No, it would be a very poor, and slow, if multiplying all those
characters together. And especially if using bignums, although for hash
functions, you /want/ to truncate them, so even 32-bit calculations
would be fine (floating point is less suitable).
But if you just wanted a hash function, just ask that instead.
I have a cheap and cheerful one, but it's one of those things, like
random number generators, where nothing but perfection will do for many
people.
------------------------------------------------
#include <stdio.h>
#include "bignum.h"
int primes[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
char *words[]={
"superincomprehensibleness",
"antidisestablishmentarianism",
"microspectrophotometrically",
"dichlorodiphenyltrichloroetha",
"hydroxydesoxycorticosterone",
"hydroxydehydrocorticosterone",
"cyclotrimethylenetrinitramine",
"trinitrophenylmethylnitramine"};
Bignum getwordprod(char* w) {
Bignum prod;
prod=bn_makeint(1);
while (*w) {
bn_mul(prod, bn_makeint(primes[*w-'a']), prod);
++w;
}
return prod;
}
int main(void) {
Bignum hash;
for (int i=0; i<8; ++i) {
hash = getwordprod(words[i]);
printf("%-30s:\n ",words[i]);
bn_println(hash);
bn_free(hash);
}
}
------------------------------------------------
(Needs bignum.h/bignum.c already linked to elsewhere. Build using:
gcc prog.c bignum.c
)
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-10-21 14:57 -0400 |
| Message-ID | <CdnrF.146403$hL1.58740@fx35.iad> |
| In reply to | #147151 |
On 10/21/2019 11:46 AM, Bart wrote:
> On 21/10/2019 04:16, DFS wrote:
>> On 10/20/2019 9:33 PM, Barry Schwarz wrote:
>>
>>
>>> Unsigned arithmetic never overflows. If the mathematical result of
>>> the operation exceeds the maximum value the target can hold, then the
>>> value is repeatedly reduced by (max_value+1) until it no exceeds the
>>> maximum. You can visualize it as simply ignoring the high order bits.
>>>
>>> One way to determine if a product of two factors will exceed the
>>> maximum value is to divide the max by either of the factors and see if
>>> the quotient is smaller than the other factor.
>>
>>
>> Thanks for the explanation. I just changed the datatype to double and
>> I got the enormous prime products
>>
>> superincomprehensibleness 2116343913154240100000000000000000000
>> antidisestablishmentarianism 10816738360843397000000000000000000000
>> microspectrophotometrically 5063607945377863500000000000000000000000
>> dichlorodiphenyltrichloroetha
>> 29387878280664888000000000000000000000000
>> hydroxydesoxycorticosterone
>> 260918185927817140000000000000000000000000
>> hydroxydehydrocorticosterone
>> 354994003426527000000000000000000000000000
>> cyclotrimethylenetrinitramine
>> 1816546187380119700000000000000000000000000
>> trinitrophenylmethylnitramine
>> 286030059853623620000000000000000000000000000
>
> These values are not right as has already been stated.
>
> The correct values are:
>
> superincomprehensibleness :
> 2116343913154240043567072445807789615
> antidisestablishmentarianism :
> 10816738360843396874796178492197077328
> microspectrophotometrically :
> 5063607945377863816547272523387703764750
> dichlorodiphenyltrichloroetha :
> 29387878280664889590552354940915144150850
> hydroxydesoxycorticosterone :
> 260918185927817220516363619911470787340775
> hydroxydehydrocorticosterone :
> 354994003426527102138061051206064480579525
> cyclotrimethylenetrinitramine :
> 1816546187380118721203679993771742512144550
> trinitrophenylmethylnitramine :
> 286030059853623711806692899673855354612258762
>
>
> These are as reported in the C program below (which formats them to
> avoid line-wrap when posting).
>
>> It's looking like prime products is not the right hash function for a
>> table of only 370K entries.
>
> No, it would be a very poor, and slow, if multiplying all those
> characters together.
It's not slow, in my opinion.
1.13 seconds to load 370104 words, including calculating the prime
product of each word.
It's quite fast to search: finds 7 anagrams in 3/1000ths of a second.
> And especially if using bignums, although for hash
> functions, you /want/ to truncate them, so even 32-bit calculations
> would be fine (floating point is less suitable).
>
> But if you just wanted a hash function, just ask that instead.
>
> I have a cheap and cheerful one, but it's one of those things, like
> random number generators, where nothing but perfection will do for many
> people.
Yeah, other than for crypto reasons, why are hash generators made so
complicated?
> ------------------------------------------------
>
> #include <stdio.h>
> #include "bignum.h"
>
> int primes[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
> 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
>
> char *words[]={
> "superincomprehensibleness",
> "antidisestablishmentarianism",
> "microspectrophotometrically",
> "dichlorodiphenyltrichloroetha",
> "hydroxydesoxycorticosterone",
> "hydroxydehydrocorticosterone",
> "cyclotrimethylenetrinitramine",
> "trinitrophenylmethylnitramine"};
>
> Bignum getwordprod(char* w) {
> Bignum prod;
>
> prod=bn_makeint(1);
>
> while (*w) {
> bn_mul(prod, bn_makeint(primes[*w-'a']), prod);
> ++w;
> }
> return prod;
> }
>
> int main(void) {
> Bignum hash;
>
> for (int i=0; i<8; ++i) {
> hash = getwordprod(words[i]);
>
> printf("%-30s:\n ",words[i]);
> bn_println(hash);
>
> bn_free(hash);
> }
> }
>
> ------------------------------------------------
>
> (Needs bignum.h/bignum.c already linked to elsewhere. Build using:
> gcc prog.c bignum.c
> )
$ tcc -o bart.exe bart_prog.c bignum.c
In file included from anagrams_bart_clc.c:2:
bignum.h:7: error: declaration expected
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-21 20:53 +0100 |
| Message-ID | <41orF.3049827$dw4.2946808@fx12.am4> |
| In reply to | #147153 |
On 21/10/2019 19:57, DFS wrote:
> On 10/21/2019 11:46 AM, Bart wrote:
>> No, it would be a very poor, and slow, if multiplying all those
>> characters together.
>
>
> It's not slow, in my opinion.
>
> 1.13 seconds to load 370104 words, including calculating the prime
> product of each word.
>
> It's quite fast to search: finds 7 anagrams in 3/1000ths of a second.
When used for name lookups, hash functions might be called large numbers
of times, a slow function can have an adverse effect.
I don't know how many times you need to check for anagrams. But even for
only 7, there better ways than doing a linear search of up to 370,000
words, but they are also more elaborate.
>> And especially if using bignums, although for hash functions, you
>> /want/ to truncate them, so even 32-bit calculations would be fine
>> (floating point is less suitable).
>>
>> But if you just wanted a hash function, just ask that instead.
>>
>> I have a cheap and cheerful one, but it's one of those things, like
>> random number generators, where nothing but perfection will do for
>> many people.
>
> Yeah, other than for crypto reasons, why are hash generators made so
> complicated?
I don't know. Here's mine anyway, as used inside programs like compilers:
int gethash(char *s) {
int hsum = 0;
while (*s) {
hsum = (hsum<<4) - hsum + *s++;
}
return (hsum<<5) - hsum;
}
(I normally use it with a 64-bit int (for 'hsum' and return type here),
but for lookups, 32 bits will suffice.)
>
>> ------------------------------------------------
>>
>> #include <stdio.h>
>> #include "bignum.h"
>> (Needs bignum.h/bignum.c already linked to elsewhere. Build using:
>> gcc prog.c bignum.c
>> )
> $ tcc -o bart.exe bart_prog.c bignum.c
> In file included from anagrams_bart_clc.c:2:
> bignum.h:7: error: declaration expected
That's odd. I get:
osboxes@osboxes:~$ gcc c.c bignum.c
osboxes@osboxes:~$ tcc c.c bignum.c
on Linux, and:
C:\c>tcc c.c bignum.c
C:\c>gcc c.c bignum.c
on Windows (either -m32 or -m64 when the compiler can do both). And that
particular line is blank:
1 // Simple arbitrary-precision integer and float library
2 // Header exporting functions and types
3 // <no available>
4
5 // This source code is placed in the public domain.
6 // You can do with it as you please.
7
8 typedef struct _bignumrec* Bignum;
What tcc version is this (tcc -v)? Mine is 0.9.27.
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-10-21 16:05 -0400 |
| Message-ID | <YcorF.70488$hB2.5518@fx42.iad> |
| In reply to | #147154 |
On 10/21/2019 3:53 PM, Bart wrote:
> On 21/10/2019 19:57, DFS wrote:
>> On 10/21/2019 11:46 AM, Bart wrote:
>
>>> No, it would be a very poor, and slow, if multiplying all those
>>> characters together.
>>
>>
>> It's not slow, in my opinion.
>>
>> 1.13 seconds to load 370104 words, including calculating the prime
>> product of each word.
>>
>> It's quite fast to search: finds 7 anagrams in 3/1000ths of a second.
>
> When used for name lookups, hash functions might be called large numbers
> of times, a slow function can have an adverse effect.
>
> I don't know how many times you need to check for anagrams. But even for
> only 7, there better ways than doing a linear search of up to 370,000
> words, but they are also more elaborate.
>
>>> And especially if using bignums, although for hash functions, you
>>> /want/ to truncate them, so even 32-bit calculations would be fine
>>> (floating point is less suitable).
>>>
>>> But if you just wanted a hash function, just ask that instead.
>>>
>>> I have a cheap and cheerful one, but it's one of those things, like
>>> random number generators, where nothing but perfection will do for
>>> many people.
>>
>> Yeah, other than for crypto reasons, why are hash generators made so
>> complicated?
>
> I don't know. Here's mine anyway, as used inside programs like compilers:
>
> int gethash(char *s) {
> int hsum = 0;
>
> while (*s) {
> hsum = (hsum<<4) - hsum + *s++;
> }
> return (hsum<<5) - hsum;
> }
>
> (I normally use it with a 64-bit int (for 'hsum' and return type here),
> but for lookups, 32 bits will suffice.)
>
>>
>>> ------------------------------------------------
>>>
>>> #include <stdio.h>
>>> #include "bignum.h"
>
>>> (Needs bignum.h/bignum.c already linked to elsewhere. Build using:
>>> gcc prog.c bignum.c
>>> )
>
>> $ tcc -o bart.exe bart_prog.c bignum.c
>> In file included from anagrams_bart_clc.c:2:
>> bignum.h:7: error: declaration expected
>
> That's odd.
Not when you consider I right-clicked on your links to the bignum files
and chose 'save link as' and saved the html (but the extension was .c so
I didn't check the contents).
Now that I copied the code:
$bart_anagram
superincomprehensibleness :
2116343913154240043567072445807789615
antidisestablishmentarianism :
10816738360843396874796178492197077328
microspectrophotometrically :
5063607945377863816547272523387703764750
dichlorodiphenyltrichloroetha :
29387878280664889590552354940915144150850
hydroxydesoxycorticosterone :
260918185927817220516363619911470787340775
hydroxydehydrocorticosterone :
354994003426527102138061051206064480579525
cyclotrimethylenetrinitramine :
1816546187380118721203679993771742512144550
trinitrophenylmethylnitramine :
286030059853623711806692899673855354612258762
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-21 21:12 +0100 |
| Message-ID | <oiorF.1054667$4F2.974871@fx26.am4> |
| In reply to | #147155 |
On 21/10/2019 21:05, DFS wrote: > On 10/21/2019 3:53 PM, Bart wrote: >> That's odd. > > > Not when you consider I right-clicked on your links to the bignum files > and chose 'save link as' and saved the html (but the extension was .c so > I didn't check the contents). Sorry, I don't go into details of exactly how these things are downloaded, usually people are more adept at this stuff than I am. (And things can go wrong as you've found.) With github links to source, probably the simplest way to download a file is to click 'Raw', select all the text (Ctrl A), then copy & paste to a local editor.
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-10-21 20:08 -0400 |
| Message-ID | <tNrrF.93850$XA2.69506@fx05.iad> |
| In reply to | #147154 |
On 10/21/2019 3:53 PM, Bart wrote: > On 21/10/2019 19:57, DFS wrote: >> On 10/21/2019 11:46 AM, Bart wrote: > >>> No, it would be a very poor, and slow, if multiplying all those >>> characters together. >> >> >> It's not slow, in my opinion. >> >> 1.13 seconds to load 370104 words, including calculating the prime >> product of each word. >> >> It's quite fast to search: finds 7 anagrams in 3/1000ths of a second. > > When used for name lookups, hash functions might be called large numbers > of times, a slow function can have an adverse effect. > > I don't know how many times you need to check for anagrams. But even for > only 7, there better ways than doing a linear search of up to 370,000 > words, but they are also more elaborate. I don't search words - I search sorted prime products. If it's a small word with letters near the beginning of the alphabet (tag/gat, bat/tab, bag/gab), it will find anagrams in 1/10,000th of a second. That's fast enough for me. >>> And especially if using bignums, although for hash functions, you >>> /want/ to truncate them, so even 32-bit calculations would be fine >>> (floating point is less suitable). >>> >>> But if you just wanted a hash function, just ask that instead. >>> >>> I have a cheap and cheerful one, but it's one of those things, like >>> random number generators, where nothing but perfection will do for >>> many people. >> >> Yeah, other than for crypto reasons, why are hash generators made so >> complicated? > > I don't know. Someone told me it's to minimize the number of collisions.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2019-10-22 10:27 +0200 |
| Message-ID | <qomegr$2bk$1@dont-email.me> |
| In reply to | #147160 |
On 22/10/2019 02:08, DFS wrote: > On 10/21/2019 3:53 PM, Bart wrote: >> On 21/10/2019 19:57, DFS wrote: >>> On 10/21/2019 11:46 AM, Bart wrote: >>>> >>>> But if you just wanted a hash function, just ask that instead. >>>> >>>> I have a cheap and cheerful one, but it's one of those things, like >>>> random number generators, where nothing but perfection will do for >>>> many people. >>> >>> Yeah, other than for crypto reasons, why are hash generators made so >>> complicated? >> >> I don't know. > > > Someone told me it's to minimize the number of collisions. > There are various characteristics that are considered "nice to have" in a hash function. Different use-cases place the emphasis differently, and there are always trade-offs - thus there are many hash functions that can be useful in different circumstances. Examples include: 1. Speed of algorithm (possibly also the speed on different types of processor). 2. Size of output (you want big outputs for things like digital fingerprints to eliminate collisions, but want small outputs when making a hashmap structure in a program). 3. Cryptographic security (sometimes you want it, sometimes you don't care). 4. "Avalanche effect" - small changes in the input making big changes to the output. Sometimes that is useful, sometimes it does not matter. 5. Avoiding pathological results (such as extra zeros leaving the output unchanged, or zero in giving zero out). 6. Mathematical guarantees (such as guaranteeing detection of any N bits changed, or other specific patterns of changes in the input). 7. Perfect hashes - minimal size of output while guaranteeing uniqueness for a known set of inputs.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-22 19:45 +0100 |
| Message-ID | <K7IrF.3053334$dw4.575231@fx12.am4> |
| In reply to | #147153 |
On 21/10/2019 19:57, DFS wrote: > On 10/21/2019 11:46 AM, Bart wrote: >>> It's looking like prime products is not the right hash function for a >>> table of only 370K entries. >> >> No, it would be a very poor, and slow, if multiplying all those >> characters together. > > > It's not slow, in my opinion. > > 1.13 seconds to load 370104 words, including calculating the prime > product of each word. > > It's quite fast to search: finds 7 anagrams in 3/1000ths of a second. For anagrams, there is another neat way, which uses a different kind of hash. If U[] is the word list, then create a corresponding list V[] where each entry is a sorted version of each word in U (so "bart" in U becomes "abrt" in V). If you want to find anagrams of S, then search for sorted(S) within V, and read off the actual word in U. And a quicker way of doing that is to further sort both U and V, in order of the strings in V. Then it becomes a binary search of sorted(S) within V. (There might be a cluster of identical strings in V, then you just need to find the limits of that group, and read off the actual anagrams from U.)
[toc] | [prev] | [next] | [standalone]
Page 1 of 6 [1] 2 3 4 5 6 Next page →
Back to top | Article view | comp.lang.c
csiph-web