4 ms·

> to multiply prime numbers one for each alphabet letter to drop the overhead of sorting how does that work?

deleted 3y ago
[deleted]
jodrellblank 3y ago
Not sure if you're asking about the technique, or the math, or the comparison with sorting, so here's a long answer of all of them - start like the secret codes from childhood by giving numbers to letters so A=1, B=2, C=3, D=4, etc. Then go through a word and find the values for each letter and multiply them together, e.g. "tab" is 20 x 1 x 2 = 40 and hopefully an anagram that just rearranges the letters gets the same answer because multiplication doesn't change if you shuffle the numbers around, e.g. "bat" is 2 x 1 x 20 = 40 which is the same, "bat" and "tab" are anagrams... but with the integers it doesn't always work and different words can clash e.g. "fab" 6 x 1 x 2 = 12 and "cad" 3 x 1 x 4 = 12 have the same answer but are not anagrams. Prime numbers help because the Fundamental Theorem of Arithmetic[1][2] says that there can't be any clashes when you multiply Primes, every number breaks down into a unique product of Primes (I can't prove that myself, but it is apparently true). So give the letters Prime numbers A=2, B=3, C=5, D=7, E=11, F=13, etc. and now "fab" 13 x 2 x 3 = 78 and "cad" 5 x 2 x 7 = 70 no longer clash. The only way to get the same answer is to have the same primes (in any order), so anagrams will have the same answer and non-anagrams will not. Why it drops the overhead of sorting is that the time for sorting any collection requires looking at each item and comparing at least some of them, and swapping positions of at least some of them, generally O(N items x log(N)). Lookup the letter in a Prime value array and multiplication once per letter doesn't need any comparisons or any swapping positions, so it is O(N items) time, that gives this approach less work to do for each word, so it can finish faster. It looks like (Python, assuming lowercase ASCII letters where 'a' starts at code 97): primes = [2,3,5,7,...] ascii_a = 97 product = 1 for c in word: product *= primes[ord(c) - ascii_a] Do that for the incoming word, and for every word in the wordlist, and see which have matching products, those are the anagrams. Or pre-compute for all the words in the wordlist and only do it for the incoming word and then lookup the matching ones. [1] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme... [2] https://www.varsitytutors.com/hotmath/hotmath_help/topics/prime-factorization https://www.varsitytutors.com/hotmath/hotmath_help/topics/pr...
- justinlloyd 3y ago
  Prime combinatorics - I think every programmer independently discovers the technique. You can also determine if a shorter word can be made from a longer word, e.g. "cat" from "catch", by looking for modulo results. And the technique of Prime Combinatorics for an "alphabet" can be used to solve Poker hands, Blackjack hands, Match 3 puzzle games, slot machine reel positions, and a slew of other similar problems where you would ordinarily have to build a very complex logic table/switch-case/if-then-else decision tree.
- kadoban 3y ago
  Is it actually faster? You could just do counting sort if the big-O is important, but I'm a bit suspicious about that big-O anyway. A model where multiplying arbitrarily big numbers is constant time is a bit unrealistic, kind of feels like it's getting off the hook for a log factor for free. It's also all such small values that I'm not sure the big-O matters either, I'm not confident which would win without just trying it. I'd _guess_ that usual sort probably just wins though, or counting sort if you really went out of the way to optimize it.
  - jodrellblank 3y ago
    Too late to edit my earlier reply, but I remembered what happened - for my newspaper puzzle, only 9 letter words are possible answers, and all 9 letter word products fit in an int64. Then in C# it is faster, casual runs seem to knock 20-25% off the runtime (~0.035 seconds vs ~0.045 seconds), but in PowerShell it is slower. (I'm curious,if it would be possible to shuffle the primes around to bring all words in my full wordlist down to UInt64; the highest is 2810298024552111657086849344270208275 - microspectrophotometries which is some quadrillion times too big. Rearranging the by letter frequency in the wordlist brings it down to 24474928756352445162715195352080 - electroencephalographically which is still a trillion times too big, so I doubt it).
    - kadoban 3y ago
      very interesting, both this comment and the sibling one. I didn't really consider how much could fit in an uint64. If all the words can be made to fit then that should indeed be quite fast (I was assuming bigints).

deleted 3y ago

[deleted]

Not sure if you're asking about the technique, or the math, or the comparison with sorting, so here's a long answer of all of them - start like the secret codes from childhood by giving numbers to letters so A=1, B=2, C=3, D=4, etc. Then go through a word and find the values for each letter and multiply them together, e.g. "tab" is 20 x 1 x 2 = 40 and hopefully an anagram that just rearranges the letters gets the same answer because multiplication doesn't change if you shuffle the numbers around, e.g. "bat" is 2 x 1 x 20 = 40 which is the same, "bat" and "tab" are anagrams... but with the integers it doesn't always work and different words can clash e.g. "fab" 6 x 1 x 2 = 12 and "cad" 3 x 1 x 4 = 12 have the same answer but are not anagrams. Prime numbers help because the Fundamental Theorem of Arithmetic[1][2] says that there can't be any clashes when you multiply Primes, every number breaks down into a unique product of Primes (I can't prove that myself, but it is apparently true). So give the letters Prime numbers A=2, B=3, C=5, D=7, E=11, F=13, etc. and now "fab" 13 x 2 x 3 = 78 and "cad" 5 x 2 x 7 = 70 no longer clash. The only way to get the same answer is to have the same primes (in any order), so anagrams will have the same answer and non-anagrams will not. Why it drops the overhead of sorting is that the time for sorting any collection requires looking at each item and comparing at least some of them, and swapping positions of at least some of them, generally O(N items x log(N)). Lookup the letter in a Prime value array and multiplication once per letter doesn't need any comparisons or any swapping positions, so it is O(N items) time, that gives this approach less work to do for each word, so it can finish faster. It looks like (Python, assuming lowercase ASCII letters where 'a' starts at code 97): primes = [2,3,5,7,...] ascii_a = 97 product = 1 for c in word: product *= primes[ord(c) - ascii_a] Do that for the incoming word, and for every word in the wordlist, and see which have matching products, those are the anagrams. Or pre-compute for all the words in the wordlist and only do it for the incoming word and then lookup the matching ones. [1] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme... [2] https://www.varsitytutors.com/hotmath/hotmath_help/topics/prime-factorization https://www.varsitytutors.com/hotmath/hotmath_help/topics/pr...

justinlloyd 3y ago
Prime combinatorics - I think every programmer independently discovers the technique. You can also determine if a shorter word can be made from a longer word, e.g. "cat" from "catch", by looking for modulo results. And the technique of Prime Combinatorics for an "alphabet" can be used to solve Poker hands, Blackjack hands, Match 3 puzzle games, slot machine reel positions, and a slew of other similar problems where you would ordinarily have to build a very complex logic table/switch-case/if-then-else decision tree.
kadoban 3y ago
Is it actually faster? You could just do counting sort if the big-O is important, but I'm a bit suspicious about that big-O anyway. A model where multiplying arbitrarily big numbers is constant time is a bit unrealistic, kind of feels like it's getting off the hook for a log factor for free. It's also all such small values that I'm not sure the big-O matters either, I'm not confident which would win without just trying it. I'd _guess_ that usual sort probably just wins though, or counting sort if you really went out of the way to optimize it.
- jodrellblank 3y ago
  Too late to edit my earlier reply, but I remembered what happened - for my newspaper puzzle, only 9 letter words are possible answers, and all 9 letter word products fit in an int64. Then in C# it is faster, casual runs seem to knock 20-25% off the runtime (~0.035 seconds vs ~0.045 seconds), but in PowerShell it is slower. (I'm curious,if it would be possible to shuffle the primes around to bring all words in my full wordlist down to UInt64; the highest is 2810298024552111657086849344270208275 - microspectrophotometries which is some quadrillion times too big. Rearranging the by letter frequency in the wordlist brings it down to 24474928756352445162715195352080 - electroencephalographically which is still a trillion times too big, so I doubt it).
  - kadoban 3y ago
    very interesting, both this comment and the sibling one. I didn't really consider how much could fit in an uint64. If all the words can be made to fit then that should indeed be quite fast (I was assuming bigints).