Amazon.com Widgets

Quiz: Primes in the BCL...

I played around a little with computing prime numbers last week, fun stuff but more on that for a another day…. When I discussed some thoughts on the subject with devs on the BCL team I found out (to my surprise) that we actually have code in the BCL for computing prime numbers… Now it is not directly callable publicly, but the source code is in rotor…

 

Anyone know where?  Extra credit if you can explain why we use primes (and need to compute them)… even more extra credit if you can find a small bug in that code…

Published 28 July 04 06:52 by BradA
Filed under:

Comments

# thomas woelfer said on July 28, 2004 7:01 AM:
Brad,

haven't looked at rotor, but my first guess is you're generating primes for use in hashtables.

WM_MY0.02$
thomas woelfer
# a. said on July 28, 2004 7:19 AM:
I've actually seen an array in the Hashtable containing prime numbers, while debugging.
# oleg@tkachenko.com (Oleg Tkachenko) said on July 28, 2004 7:21 AM:
Sure it's hashtable.cs.
# Juan Felipe Machado said on July 28, 2004 7:31 AM:
And that's because it's based in "Knuth's Art of Computer Programming, Vol. 3, p. 528-9" :)
# Eric Wilson said on July 28, 2004 7:31 AM:
Specifically, primes are used when the size of a hash table must be increased because of the load has reached a certain level. The size of the hashtable is increased such that the number of buckets in the hashtable increases to the smallest prime number that is larger than twice the current number of Hashtable buckets.

The reason for this is two fold. Using a prime number of buckets reduces the effect of clustering in the hashtable (having multiple keys hash to the same location). The size is at least doubled because by doing that the BCL can insure that over a series of N insert, the total time for all inserts takes no more than O(log(N)) total time.
# RichB said on July 28, 2004 7:35 AM:
Also Crypto stuff/Strong names?
# Norman Headlam said on July 28, 2004 7:36 AM:
It is used for the hashtable buckets. The hashtable.cs file has a list of static prime numbers and a function to return the prime number

private static int GetPrime(int minSize)
{
for (int i = 0; i < primes.Length; i++)
{
int size = primes[i];
if (size >= minSize) return size;
}
//outside of our predefined table.
//compute the hard way.
for (int j = (minSize | 1);j < Int32.MaxValue;j+=2)
{
if (Primep (j))
return j;
}
return minSize;
}
# Mike Marshall said on July 28, 2004 7:59 AM:
To the guy that mentioned crypto stuff. If it was all managed code then you would think so, but the probability is that most of it is done through P/Invoke to the CryptoAPI, which would reduce the change of prime generations showing up in the BCL code.
# Jonathan Perret said on July 28, 2004 8:14 AM:
Hashtable was the obvious suspect... but there's another one. Fire up Reflector and try a member search for "prime", and you'll find that System.Windows.Forms.NativeWindow has its own hashtable code, obviously snarfed from Hashtable.

As to the bug, well I don't see one in the Rotor code posted above, but in what Reflector shows me there's a ((minSize - 2)|1) where Rotor has (minSize|1). I think the effect of this is that GetPrime(minSize) will actually return (minSize-2) whenever minSize is equal to P+1 or P+2, where P is a prime larger than can be found in the predefined table.

From a quick look at what is done with the return value from GetPrime() this does not look like it would break anything, but still I would call it a violation of the contract that is implied by naming the parameter 'minSize'.

Also, the code relies on Int32.MaxValue being an odd number.

And there's an inefficiency in Primep(), it recomputes the square root of the candidate on each iteration of the loop. I have just verified that the JIT does not optimize this away.

Cheers,
--Jonathan
# Ryan Heath said on July 28, 2004 8:19 AM:
Now that we all agree on hashtables,

I saw with Reflector a for-loop in Hashtable.GetPrime that is
looping over an int while it is less than maxint

This is a (minor) bug, when passing the maxint value
the int will wrap to a negative value...

// Ryan
# Lance Fisher said on July 28, 2004 8:39 AM:
The primes array is defined as:

// Table of prime numbers to use as hash table sizes. Each entry is the
// smallest prime number larger than twice the previous entry.
private readonly static int[] primes = {
11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,
1103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591,
17519,21023,25229,30293,36353,43627,52361,62851,75431,90523, 108631, 130363,
156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403,
968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287,
4999559, 5999471, 7199369
};

However, 17 is not the smallest prime number after 11 * 2 = 22, that would be 23. Likewise for each subsequent entry in the array. So when this is used by the GetPrime() function, you're getting a smaller prime than you really wanted.
# Jonathan Perret said on July 28, 2004 8:57 AM:
Ryan : this is the loop I was referring to when I wrote that the code relies on Int32.MaxValue being an odd number.

If minSize is already Int32.MaxValue then the for loop will not even be entered.

If minSize is >2147483629 (largest prime that is <Int32.MaxValue) and <Int32.MaxValue, the loop will run to Int32.MaxValue and correctly stop without overflow, since it iterates only on odd numbers. If Int32.MaxValue were even, the loop would jump right past it and continue with Int32.MinValue.
Then GetPrime() will return minSize itself. Which is another bug since minSize is not prime in this case. GetPrime() should just return Int32.MaxValue, since amazingly, it is M31, a Mersenne prime number.

This is all mostly of academical interest however: GetPrime()'s return value is used as the size of an array. 32-bit machines will have a hard time allocating a array of Int32.MaxValue elements...

Cheers,
--Jonathan
# Jonathan Perret said on July 28, 2004 9:01 AM:
Lance: as you point out, the comment is incorrect. However I believe the intent was moved into the expand() function :

private void expand()
{
this.rehash(this.GetPrime(1 + (this.buckets.Length * 2)));
}

Cheers,
--Jonathan
# Keith Patrick said on July 28, 2004 6:20 PM:
Primes are most useful in asymmetrical encryption. 2 primes form your public and private keys, which, when combined, can encrypt/decrypt data in such a way that due to the nature of primes, you cannot derive the crypto key without having both prime-based "keys"
Dunno what the bug is, though.
# Keith Patrick said on July 28, 2004 6:25 PM:
HA! I just read some of the middle posts about the crypto stuff being just a wrapper for CryptoAPI. Whoops, true (maybe...it probably is, but I don't know myself), although that is what I think of when I ponder the utility of primes (Gates said in "The Road Ahead" something about there being an infinite # of primes, hence their suitability as crypto keys)

The hashtable usage is pretty neat, though. I never really thought of that as the means of ensuring uniqueness in the buckets. I recall having to write a hashtable in college, but I had some algorithm that was much less computationally-expensive, yet more fallible (I think I ultimately had my buckets storing lists in case of collisions)
# Brad Abrams said on July 28, 2004 11:12 PM:
# RichB said on July 29, 2004 10:43 PM:
Most of the Crypto stuff is a wrapper around the Win32 CryptoAPI - except for Rijndael. However, Rijndael/AES is a symmetric cipher. Therefore, Keith's post about primes in the Crypto BCL probably holds true.
# protected virtual void jayBlog { said on August 1, 2004 5:49 PM:
# protected virtual void jayBlog { said on August 1, 2004 5:50 PM:
# Web Log di Gianluca Carucci said on August 27, 2004 12:38 PM:
New Comments to this post are disabled

Search

This Blog



These postings are provided "AS IS" with no warranties, and confer no rights.



Ads by Lake Quincy Media

Syndication

Page view tracker