I would like to thank everyone who offered their history files and/or message-id logs to run this test. I wound up using most of them for smaller runs during my construction of the CRC test program, and used an 18.2 million message-id data set supplied by Joe Greco for the final test runs shown below.
Using the program I posted earlier with one minor bug in the placement of ++total corrected, I ran the 18.2 million message-id data set with CRC's ranging from 16 to 64 bits. The number of collisions are shown below. The program is included at the bottom.
The lower numbered CRC's tended on collision rates nearing 100% after a certain number of samples, which is as expected. Once the test got beyond the noise floor, each additional bit of CRC cut the number of collisions down by approximately half. No collisions occured with the 18.2 million message-id's dataset once we got beyond CRC48, but one can extrapolate a collision rate of one message-id per 2.3 Trillion message-id's with a CRC64 from empirical data. The theoretical collision rate for CRC64 and 18.2 million mesage-id's is one collision every 2 trillion message-id's so we have good correspondance to theory.
I should have used a real CRC long ago rather then try to do something fancy with prime numbers. The 1.14 diablo release is going to use the CRC64 algorithm included at the end (well, actually CRC63 as I want to reserve one bit for future use). Besides, it's a good deal faster then the old prime-mod algorithm anyway as it only requires shift and xor ops to implement.
-Matt (dillon@backplane.com)
Summary, 18.2 million sample test dataset, number of collisions.
Raw data, collisions for 18.2 million sample data set in increments of 100,000 samples for CRC16 through CRC64. Note that near the end, CRC16 through CRC20 approach a 100% collision rate. No collisions occured with the test dataset beyond CRC-48.
SAMPLES CRC16 CRC17 CRC18 CRC19 CRC20 CRC21 CRC22
0.1M 48694 29762 17032 9070 4519 2274 1212
0.2M 137655 97436 60243 34119 17834 9211 4809
0.3M 235174 182198 121457 71883 39173 20303 10626
0.4M 334630 275232 194897 120208 67433 35624 18672
0.5M 434497 371788 277068 177992 102379 55094 28973
0.6M 534472 470260 364505 242833 143019 78184 41394
0.7M 634464 569530 456066 314036 189198 105006 55646
0.8M 734464 669213 550297 389973 240256 135019 72156
0.9M 834464 769050 646412 470339 295794 168415 91007
1.0M 934464 868987 743717 554420 356011 205050 111280
1.1M 1034464 968955 841834 640870 419364 244383 133311
1.2M 1134464 1068940 940621 729741 486134 286809 157443
...
16.3M 16234464 16168928 16037856 15775712 15251424 14203708 12192725
16.4M 16334464 16268928 16137856 15875712 15351424 14303666 12290669
16.5M 16434464 16368928 16237856 15975712 15451424 14403623 12388681
16.6M 16534464 16468928 16337856 16075712 15551424 14503585 12486733
16.7M 16634464 16568928 16437856 16175712 15651424 14603553 12584808
16.8M 16734464 16668928 16537856 16275712 15751424 14703524 12682912
16.9M 16834464 16768928 16637856 16375712 15851424 14803488 12781127
17.0M 16934464 16868928 16737856 16475712 15951424 14903456 12879337
17.1M 17034464 16968928 16837856 16575712 16051424 15003425 12977634
17.2M 17134464 17068928 16937856 16675712 16151424 15103396 13076030
17.3M 17234464 17168928 17037856 16775712 16251424 15203379 13174358
17.4M 17334464 17268928 17137856 16875712 16351424 15303355 13272762
17.5M 17434464 17368928 17237856 16975712 16451424 15403335 13371202
17.6M 17534464 17468928 17337856 17075712 16551424 15503319 13469702
17.7M 17634464 17568928 17437856 17175712 16651424 15603292 13568257
17.8M 17734464 17668928 17537856 17275712 16751424 15703269 13666849
17.9M 17834464 17768928 17637856 17375712 16851424 15803253 13765429
18.0M 17934464 17868928 17737856 17475712 16951424 15903234 13863977
18.1M 18034464 17968928 17837856 17575712 17051424 16003219 13962602
18.2M 18134464 18068928 17937856 17675712 17151424 16103198 14061250
SAMPLES CRC23 CRC24 CRC25 CRC26 CRC27 CRC28 CRC29
0.1M 598 306 137 70 33 32 6
0.2M 2335 1234 566 286 148 80 36
0.3M 5306 2735 1297 660 338 185 76
0.4M 9430 4829 2366 1184 593 317 136
0.5M 14681 7449 3695 1874 921 480 212
0.6M 21107 10766 5245 2713 1329 693 298
0.7M 28501 14579 7107 3685 1816 904 418
0.8M 37024 18949 9289 4775 2368 1200 552
0.9M 46627 24062 11747 6030 2999 1535 726
1.0M 57487 29702 14566 7434 3696 1883 900
1.1M 69275 35841 17618 8982 4420 2278 1085
1.2M 82141 42418 20918 10651 5242 2735 1276
...
16.3M 9114163 5872118 3390118 1829751 951696 485017 244776
16.4M 9200121 5934331 3428694 1851395 963180 490947 247822
16.5M 9286007 5996612 3467221 1872875 974620 496944 250882
16.6M 9372012 6059317 3506292 1894849 986234 502734 253973
16.7M 9458202 6122215 3545563 1917044 997824 508770 257098
16.8M 9544827 6185514 3585185 1939007 1009459 514758 260095
16.9M 9631424 6248792 3624656 1961210 1021186 520766 263145
17.0M 9717886 6312228 3664147 1983486 1033057 526828 266255
17.1M 9804653 6376231 3704077 2005842 1045006 533034 269413
17.2M 9891451 6440246 3744092 2028282 1056942 539151 272609
17.3M 9978615 6504484 3784090 2050970 1068949 545393 275829
17.4M 10066095 6568897 3824279 2073908 1080972 551746 279052
17.5M 10153638 6633419 3864988 2096617 1093007 558241 282168
17.6M 10241316 6698409 3905771 2119439 1105345 564643 285307
17.7M 10329060 6763735 3946805 2142721 1117568 571041 288589
17.8M 10416956 6829189 3987814 2165682 1129935 577460 291925
17.9M 10505125 6894783 4028719 2188977 1142181 583945 295143
18.0M 10593200 6960451 4070229 2212196 1154546 590442 298462
18.1M 10681658 7026271 4111702 2235718 1167082 596914 301830
18.2M 10770169 7092360 4153742 2259269 1179721 603421 305089
SAMPLES CRC30 CRC31 CRC32 CRC33 CRC34 CRC35 CRC36
0.1M 5 1 3 0 0 0 0
0.2M 14 12 5 3 0 1 0
0.3M 40 24 7 8 6 3 1
0.4M 73 37 20 10 9 3 3
0.5M 110 65 29 16 12 4 4
0.6M 161 86 44 22 14 6 5
0.7M 219 121 66 33 14 8 5
0.8M 292 151 84 41 19 9 5
0.9M 370 195 104 53 26 11 5
1.0M 455 238 124 68 29 12 6
1.1M 557 281 149 78 32 15 8
1.2M 669 350 178 88 38 17 12
...
16.3M 123428 61928 31046 15393 7752 3939 1891
16.4M 124961 62691 31444 15576 7839 3991 1920
16.5M 126444 63473 31815 15776 7948 4043 1938
16.6M 127945 64235 32207 16004 8046 4097 1962
16.7M 129517 64984 32588 16230 8148 4144 1984
16.8M 131019 65739 32974 16438 8244 4194 2010
16.9M 132553 66529 33358 16632 8351 4248 2036
17.0M 134113 67326 33756 16835 8444 4290 2060
17.1M 135661 68138 34135 17032 8553 4344 2086
17.2M 137279 68952 34510 17234 8665 4387 2114
17.3M 138840 69781 34891 17448 8765 4436 2136
17.4M 140575 70594 35276 17629 8858 4483 2161
17.5M 142290 71396 35726 17807 8955 4521 2189
17.6M 143864 72236 36174 17994 9072 4561 2214
17.7M 145485 73014 36600 18204 9167 4637 2241
17.8M 147093 73825 36971 18396 9261 4682 2260
17.9M 148720 74638 37388 18586 9357 4735 2289
18.0M 150358 75498 37804 18802 9452 4801 2305
18.1M 152014 76347 38195 19014 9551 4861 2324
18.2M 153722 77254 38638 19232 9652 4914 2343
SAMPLES CRC37 CRC38 CRC39 CRC40 CRC41 CRC42 CRC43
0.1M 0 0 0 0 0 0 0
0.2M 0 0 0 0 0 0 0
0.3M 1 0 0 0 0 0 0
0.4M 1 0 0 0 0 0 0
0.5M 2 0 0 0 0 0 0
0.6M 2 0 0 0 0 0 0
0.7M 2 0 0 0 0 0 0
0.8M 3 0 1 0 0 0 0
0.9M 4 0 1 0 0 0 0
1.0M 6 0 1 0 0 0 0
1.1M 6 0 1 0 0 0 0
1.2M 6 1 1 0 0 0 0
...
16.3M 975 511 245 118 63 35 16
16.4M 989 515 247 122 65 36 17
16.5M 998 521 248 122 65 37 17
16.6M 1012 531 249 123 65 38 17
16.7M 1020 533 250 123 66 40 17
16.8M 1033 539 253 128 66 40 17
16.9M 1043 546 254 129 67 41 17
17.0M 1054 550 257 129 69 42 17
17.1M 1067 555 260 130 70 42 18
17.2M 1083 561 263 133 70 44 19
17.3M 1090 573 266 135 70 46 20
17.4M 1096 586 271 137 71 46 20
17.5M 1108 594 275 139 72 46 20
17.6M 1120 597 280 140 72 48 21
17.7M 1134 603 287 142 72 48 21
17.8M 1146 608 287 146 73 48 21
17.9M 1162 614 291 147 73 50 21
18.0M 1176 621 293 149 73 50 21
18.1M 1185 626 298 150 75 51 21
18.2M 1204 637 302 152 75 52 21
SAMPLES CRC44 CRC45 CRC46 CRC47 CRC48 CRC49 CRC50
0.1M 0 0 0 0 0 0 0
0.2M 0 0 0 0 0 0 0
0.3M 0 0 0 0 0 0 0
0.4M 0 0 0 0 0 0 0
0.5M 0 0 0 0 0 0 0
0.6M 0 0 0 0 0 0 0
0.7M 0 0 0 0 0 0 0
0.8M 0 0 0 0 0 0 0
0.9M 0 0 0 0 0 0 0
1.0M 0 0 0 0 0 0 0
1.1M 0 0 0 0 0 0 0
1.2M 0 0 0 0 0 0 0
1.3M 0 0 0 0 0 0 0
1.4M 0 0 0 0 0 0 0
1.5M 0 0 0 0 0 0 0
1.6M 0 0 0 0 0 0 0
1.7M 0 0 0 0 0 0 0
1.8M 0 0 0 0 0 0 0
1.9M 0 0 0 0 0 0 0
2.0M 0 0 0 0 0 0 0
2.1M 0 0 0 0 0 0 0
2.2M 0 0 0 0 0 0 0
2.3M 0 0 0 0 0 0 0
2.4M 0 0 0 0 0 0 0
2.5M 0 0 0 0 0 0 0
2.6M 0 0 0 0 0 0 0
2.7M 0 0 0 0 0 0 0
2.8M 0 0 0 0 0 0 0
2.9M 0 0 0 0 0 0 0
3.0M 1 0 0 0 0 0 0
3.1M 1 0 0 0 0 0 0
3.2M 1 0 0 0 0 0 0
3.3M 1 0 0 0 0 0 0
3.4M 1 0 0 0 0 0 0
3.5M 1 0 0 0 0 0 0
3.6M 2 0 0 0 0 0 0
3.7M 3 0 0 0 0 0 0
3.8M 3 0 0 0 0 0 0
3.9M 3 0 0 0 0 0 0
4.0M 3 0 0 0 0 0 0
4.1M 3 0 0 0 0 0 0
4.2M 3 0 0 0 0 0 0
4.3M 3 0 0 0 0 0 0
4.4M 3 0 0 0 0 0 0
4.5M 3 0 0 0 0 0 0
4.6M 3 0 0 0 0 0 0
4.7M 3 0 0 0 0 0 0
4.8M 3 0 0 0 0 0 0
4.9M 3 0 0 0 0 0 0
5.0M 4 0 0 0 0 0 0
5.1M 4 0 0 0 0 0 0
5.2M 4 0 0 0 0 0 0
5.3M 4 0 0 0 0 0 0
5.4M 4 0 0 0 0 0 0
5.5M 4 0 0 0 0 0 0
5.6M 5 0 0 0 0 0 0
5.7M 5 0 0 0 0 0 0
5.8M 5 0 0 0 0 0 0
5.9M 5 0 0 0 0 0 0
6.0M 5 0 0 0 0 0 0
6.1M 5 0 0 0 0 0 0
6.2M 5 0 0 0 0 0 0
6.3M 5 0 0 0 0 0 0
6.4M 5 0 0 0 0 0 0
6.5M 5 0 0 0 0 0 0
6.6M 5 0 0 0 0 0 0
6.7M 5 0 0 0 0 0 0
6.8M 5 0 0 0 0 0 0
6.9M 5 0 0 0 0 0 0
7.0M 5 0 0 0 0 0 0
7.1M 5 0 0 0 0 0 0
7.2M 5 0 0 0 0 0 0
7.3M 5 0 0 0 0 0 0
7.4M 5 0 0 0 0 0 0
7.5M 5 0 0 0 0 0 0
7.6M 5 0 0 0 0 0 0
7.7M 5 0 0 0 0 0 0
7.8M 5 0 0 0 0 0 0
7.9M 5 1 0 0 0 0 0
8.0M 5 1 0 0 0 0 0
8.1M 5 1 0 0 0 0 0
8.2M 5 1 0 0 0 0 0
8.3M 5 1 0 0 0 0 0
8.4M 5 1 0 0 0 0 0
8.5M 5 1 0 0 0 0 0
8.6M 5 1 0 0 0 0 0
8.7M 5 1 0 0 0 0 0
8.8M 5 1 0 0 0 0 0
8.9M 5 2 0 0 0 0 0
9.0M 5 2 0 0 0 0 0
9.1M 5 2 0 0 0 0 0
9.2M 5 2 0 0 0 0 0
9.3M 5 2 0 0 0 0 0
9.4M 5 2 0 0 0 0 0
9.5M 5 2 1 0 0 0 0
9.6M 5 2 1 0 0 0 0
9.7M 5 2 1 0 0 0 0
9.8M 5 2 1 0 0 0 0
9.9M 5 2 1 0 0 0 0
10.0M 5 2 1 0 0 0 0
10.1M 6 2 1 0 0 0 0
10.2M 6 2 1 0 0 0 0
10.3M 6 2 1 0 0 0 0
10.4M 6 2 1 0 0 0 0
10.5M 6 2 1 0 0 0 0
10.6M 6 2 1 0 0 0 0
10.7M 6 2 1 0 0 0 0
10.8M 6 2 1 0 0 0 0
10.9M 6 2 1 0 0 0 0
11.0M 6 2 1 0 0 0 0
11.1M 6 2 1 0 0 0 0
11.2M 6 2 1 0 0 0 0
11.3M 6 2 1 0 0 0 0
11.4M 6 2 1 0 0 0 0
11.5M 6 2 1 0 0 0 0
11.6M 6 2 1 0 0 0 0
11.7M 6 2 1 0 0 0 0
11.8M 6 2 1 0 0 0 0
11.9M 6 2 1 0 0 0 0
12.0M 6 2 1 0 0 0 0
12.1M 6 2 1 0 0 0 0
12.2M 6 2 1 0 0 0 0
12.3M 6 2 1 0 0 0 0
12.4M 6 3 1 0 0 0 0
12.5M 6 4 1 0 0 0 0
12.6M 7 4 1 0 0 0 0
12.7M 7 4 1 0 0 0 0
12.8M 7 4 1 0 0 0 0
12.9M 7 4 1 0 0 0 0
13.0M 7 4 1 0 0 0 0
13.1M 7 4 1 0 0 0 0
13.2M 7 4 1 0 0 0 0
13.3M 7 4 1 0 0 0 0
13.4M 7 4 1 0 0 0 0
13.5M 7 4 1 0 0 0 0
13.6M 7 4 1 0 0 0 0
13.7M 7 4 1 0 0 0 0
13.8M 7 4 1 0 0 0 0
13.9M 7 4 1 0 0 0 0
14.0M 7 4 1 0 0 0 0
14.1M 7 4 1 0 0 0 0
14.2M 7 4 1 0 0 0 0
14.3M 7 4 1 0 0 0 0
14.4M 7 4 1 0 0 0 0
14.5M 7 4 1 0 0 0 0
14.6M 7 4 1 0 0 0 0
14.7M 7 4 1 0 0 0 0
14.8M 7 4 1 0 0 0 0
14.9M 7 4 1 0 0 0 0
15.0M 7 4 1 0 0 0 0
15.1M 8 4 1 0 0 0 0
15.2M 8 4 1 0 0 0 0
15.3M 8 4 1 0 0 0 0
15.4M 8 4 1 0 0 0 0
15.5M 9 4 1 1 0 0 0
15.6M 9 4 1 1 0 0 0
15.7M 11 4 1 1 0 0 0
15.8M 11 4 1 1 0 0 0
15.9M 11 4 1 1 0 0 0
16.0M 11 4 1 1 0 0 0
16.1M 11 4 1 1 0 0 0
16.2M 12 5 1 1 0 0 0
16.3M 12 5 1 1 0 0 0
16.4M 12 5 1 1 0 0 0
16.5M 12 5 1 1 0 0 0
16.6M 12 5 1 1 0 0 0
16.7M 13 5 1 1 0 0 0
16.8M 13 5 1 1 0 0 0
16.9M 13 5 1 1 0 0 0
17.0M 13 5 1 1 0 0 0
17.1M 13 5 1 1 0 0 0
17.2M 13 5 1 1 0 0 0
17.3M 13 6 1 1 0 0 0
17.4M 13 6 1 1 0 0 0
17.5M 13 6 1 1 0 0 0
17.6M 13 6 1 1 0 0 0
17.7M 13 6 1 1 0 0 0
17.8M 13 6 1 1 0 0 0
17.9M 13 6 1 1 0 0 0
18.0M 13 6 1 1 0 0 0
18.1M 13 6 1 1 0 0 0
18.2M 13 7 1 1 1 0 0
SAMPLES CRC51 CRC52 CRC53 CRC54 CRC55 CRC56 CRC57
(all zero)
SAMPLES CRC58 CRC59 CRC60 CRC61 CRC62 CRC63 CRC64
(all zero)