3 ms·

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 a

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).
jodrellblank 3y ago
Huh, good call; it was 2 years ago that I did it, and I've retried to test it; the values overflow an Int64 or a Uint64 for words like "abortiveness" (== 38199980262261136506). Trying in PowerShell that overflowed to a double and then errored assigning it to an Int64. Looking what was happening, I find C# doesn't throw overflow exceptions by default and instead wraps around. That takes 0.05 seconds for all 172k words compared to 0.1 seconds for sorting all words so it ran a lot faster, yes, but it was wrong and may have clashed words. Same with Rust and overflows, it seems. Turning it to System.Numerics.BigInteger in C# makes it take about the same time 0.1s for both. In Python which handles any size integers it takes a lot more time, 0.14 seconds for sorting, 0.4 seconds for products. That means my embedded arrays of products are all overflowed as well. What a good example for arguing that programs should be correct first, and fast second. (I remember being suspicious of overflows, but I don't remember what I tried to conclude that all the word results would fit into int64, but it must have been bad).

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).

jodrellblank 3y ago

Huh, good call; it was 2 years ago that I did it, and I've retried to test it; the values overflow an Int64 or a Uint64 for words like "abortiveness" (== 38199980262261136506). Trying in PowerShell that overflowed to a double and then errored assigning it to an Int64. Looking what was happening, I find C# doesn't throw overflow exceptions by default and instead wraps around. That takes 0.05 seconds for all 172k words compared to 0.1 seconds for sorting all words so it ran a lot faster, yes, but it was wrong and may have clashed words. Same with Rust and overflows, it seems. Turning it to System.Numerics.BigInteger in C# makes it take about the same time 0.1s for both. In Python which handles any size integers it takes a lot more time, 0.14 seconds for sorting, 0.4 seconds for products. That means my embedded arrays of products are all overflowed as well. What a good example for arguing that programs should be correct first, and fast second. (I remember being suspicious of overflows, but I don't remember what I tried to conclude that all the word results would fit into int64, but it must have been bad).