Re^4: An optimal solution to finding weights for a weighted sum signature.

I hadn't been able to figure out why the shuffling helped you, either. Before Eily's post,

As I said, I was surprised at the result. The fact that I am not shuffling the same K primes as I had intended, but rather shuffling a set n*K primes and then selecting the leftmost K of those, was a programming error, and one I didn't twig to until some time this morning. However, the benefits of it are a very nice side-effect of my error, and I'll take that with knobs on :)

Finally, as a last thought: as Eily said, sums of primes don't approach uniqueness. However, products of primes do.

Agreed, but please note that I'm not "summing primes", but rather summing products of primes, and different multiples of different primes to boot. So, whilst the results aren't unique (otherwise my collision test would show none) with the right set of primes in the right order, and largish subsets, the results show that they do actually approach uniqueness for practical purposes.

This is using 26 element subsets (using a 26-char alphabet) and picking every 384th prime from the first 10,000 and examining the collisions in the first 1 & 10 million:

C:\test>weightedPrimeSumProduct -K=26 -M=384 -S=2417 -C=1e6
9311 32213 20393 52667 44269 36161 60953 56809 78193 40213 12907 48527
+ 104579 91331 73939 69709 95603 16603 86969 65357 82493 100109 2657 2
+8181 5849 24137
1000000 Ave. collisions: 1.163441; Max. collisions:6.000000

C:\test>weightedPrimeSumProduct -K=26 -M=384 -S=2417 -C=10e6
9311 32213 20393 52667 44269 36161 60953 56809 78193 40213 12907 48527
+ 104579 91331 73939 69709 95603 16603 86969 65357 82493 100109 2657 2
+8181 5849 24137
10000000        Ave. collisions: 2.654229; Max. collisions:17.000000
[download]

Note:The shuffle ordering is not well chosen, just the first random number I typed used to initialise the PRNG.

I realise that 1 & 10 million is a tiny proportion of the 413 septillion combinations, but that is actually fairly representative of the percentages I would expect for the much larger subsets and very much larger alphabets I'm targeting.

I think I came up with something (after looking up a few primey facts today) that would be a product of two primes.

On first reading, (and second and third) that appears to me to be genius. I love this place for ideas like that. Thank you!

This day has been way to long for my old brain to really apply much in the way of analysis tonight; but I will tomorrow ....

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re^4: An optimal solution to finding weights for a weighted sum signature. Download Code