[Mono-devel-list] CoreLib's HashTable CalcPrime() new code

[Yuri Astrakhan]

I have rewritten CalcPrime() in the mcs\class\corlib\System.Collections\Hashtable.cs to fix several bugs (ie 15 was shown as a prime and the result was sometimes below the original value)  The speed has been improved almost 4.5 times according to the 30 second tests, by skipping numbers divisible by 2 and 3. There is some bits magic, but code is, hopefully, clear / enough commented. TestPrime() is no longer needed and should be removed.

Also, there is a hardcoded prime number's table being used in ToPrime(), which waistes lots of resources (IMHO) because it skips most of the primes and new hash tables become overbloated. Why not use the Mono.Math.BigInteger.smallPrimes[] instead? Wouldn’t that be closer to the spec? Although, i am not sure about dependencies because the Hashtable is in the corlib, whereas BigInteger might not be. 

One last question -- why does HashTable uses int for capacity? Isn't uint more appropriate? Why did MS chose to use int everywhere? Sometime in the future we will have LOTS of ram, enough to have over 2 billion elements... :-) In any case, i wounder if signed or unsigned shift operations are faster? Compiler might be adding some extra "&" masks. 

/// <sumary>
///     Written by Yuri Astrakhan ( wuzika(-AT-)yahoo(-DOT-)com ) for Mono Project
///     Calculates the first prime number more or equal to x.
/// The algorithm tests all numbers that are *NOT* divisable by 2 and 3,
/// starting from x (or x+1 if even x).
/// 1 is the smallest return value, 2 and 3 are always skipped (5 is returned next)
/// The test is done by the similar algorithm -- dividing generated
/// number (testVal) by every possible value up to the sqrt(testVal),
/// excluding those divisable by 2 and 3.
/// Everything is done inside a single function to avoid tons of function calls.
/// The local variables adder & divAdder are used to increment values.
/// </sumary>
private static int CalcPrime(int x)
{
    // start with an odd number (either x or x+1)
    int testVal = (x | 1);
    // make sure testVal is not divisible by 3 (incr by 2 if needed)
    if( (testVal % 3) == 0 ) testVal+=2;
    // adder can be either be 0 or 1
    int adder = (2-(testVal % 3));
    // Since int.MaxValue (2147483647) is a prime, no need to test
    // ATTENTION!  If you change int to some other type (not 32bit signed),
    // this code might give a wrong result for x approaching maxValue.
    // some test will be needed here:   if( testVal > maxPrime ) return testVal;
    while( true )
    {
        int maxDiv = (int) Math.Sqrt( testVal );
        int div = 5;        // 2,3,and 4 are already elliminated
        int divAdder = 0;   // for div==5, ((div+2) % 3) != 0  thus next time add 2
        // Try to divide testVal by all possible divisors (div) excluding 2 and 3
        while( div <= maxDiv )
        {
            if( (testVal % div) == 0 )
            {
                // nope, number testVal is not prime
                // move on to the next testVal by adding 2 if the result
                // is not divisible by 3, otherwise add 4
                testVal += (2 << adder);
                adder ^= 1;
                break;
            }
            // try next divisor
            div += (2 << divAdder);
            divAdder ^= 1;
        }
        // check if while() exited without "break" - if no divisor was found
        if( div > maxDiv )
            return testVal; // we have the winner
    }
}



---------------------------------
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20030901/8c0e8c4e/attachment.html