Hello, First off, thanks by the response.
I really doubt it to have something to be with md5, first off acording to wikipedia (If one can trust it...) there is no need to finding primes. I have to recognize that I'm not familiar with it's implementation of md5, though. The reason I have to think it doesn't have to do with md5, is because of the way it's used in the code of Mono. Wikipedia article: http://en.wikipedia.org/wiki/MD5 Here a link to the source code: http://anonsvn.mono-project.com/viewvc/trunk/mcs/class/corlib/System.Collections/Hashtable.cs?revision=144303&view=markup [Note: the cited array is declared on line 102, on this revision (144303)] Ok, the array in only used in the method ToPrime (line 842), which is used in an obsolete constructor (at 146), OnDesiarization (at 552) and Rehash (at 692). In the first two places calculating the size* of the tables [size = ToPrime (size);] and on Rehash to calculate the same size after rehash [uint newSize = (uint)ToPrime ((oldSize<<1)|1);] There is a notable comment on this line (696): // From the SDK docs: // Hashtable is automatically increased // to the smallest prime number that is larger // than twice the current number of Hashtable buckets Note: the use in HashSet is similar to this one, I cite HashTable, because the autor that added this array to the implementation of HashSet said he got it from HashTable, which also is an older class. *this is what reflects the capacity, the size of the arrays hashes and table, that stores hashes and key-values respectively. ----------------------- About the SDK cite in Mono code, I found this on MSDN: As elements are added to a Hashtable, the actual load factor of the Hashtable increases. When the actual load factor reaches the specified load factor, the number of buckets in the Hashtable is automatically increased to the smallest prime number that is larger than twice the current number of Hashtable buckets. Full text here: http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx ----------------------- Using this definition I was tempted to think that all the primes that where smaller that the double of the previous one where removed, but it's easy to show the opposite pointing that 19 (the second on the list) is smaller than the double of 11 (the first on the list). So far, I can say that skipping this primes doesn't affect the functionality, It must be some kind of optimization. On 18 dic, 03:09, Processor Devil <[email protected]> wrote: > Well, not all prime numbers are used for hashing and encrypting :), I would > suggest you to read something about md5 algorithm, but that thing is kinda > messy... > > 2009/12/17 Theraot <[email protected]> > > > > > Hello, > > > Recently I've been looking at HashSet and HashTable implementations in > > Mono, and I've found some code to generate prime numbers as a helper > > for the algorithms, it uses a pre-calculated array of primes. This > > array skips a few primes, while I think that for the use of this > > primes that are close in the code may be somehow hit the performance, > > I don't understand in general what was the criteria of skipping > > primes. > > > The array contains the following numbers: > > > 11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237, 1861, 2777, 4177, > > 6247, 9371, 14057, 21089, 31627, 47431, 71143, 106721, 160073, 240101, > > 360163 > > > and some times, also: > > > 540217, 810343, 1215497, 1823231, 2734867, 4102283, 6153409, 9230113, > > 13845163 > > > I've found that this same array also exists other projects under > > Apache software fundation, among other places. > > > My question is if this some arcane knowledge of why skip certain > > primes forever lost in the ancient library of alexandria, preserved > > for the even more arcane habit of code reutilization known as copy- > > paste, or does anybody know how did they come to this list. > > > In abstract: does somebody know why this primes and no others? > > > I hope I'm able to understand it when I see the explanation, I bet my > > brain is not as good to abstract the pattern... > > > By the way, the code for prime generation is long tested (of course, > > it's in a lot of open implementation) and has been long overcame. If > > you search a bit on this group the chances are of finding a little > > riddle* for a fast prime generation algarothm.... so, this has nothing > > to do with the algorithm, just the pre-calculated array... I just > > don't want to think that skipping this primes is a defect. > > > *It was one year ago (Challenge: Generate Prime Numbers). Salutes to > > Ram and CK, and let's take the chance and salute Cerberus too. > > > I repeate the question in case you missed it: does somebody know why > > this primes and no others? > > > Theraot
