Alfred Thompson and I tend to have “friendly” talks about programming and for a while we’ve been attempting to figure out who was the better coder. Someone gave us the challenge of find quickest way to figure out the first prime number after 2.2 billion. Turns out even if you’re on a cruise ship filled with PhD’s, seemed like no one knew of a better way off the top of their head other than brute force. Alfred used VB.Net, I used c#. Alfred’s VB.Net prime number solution is posted over at his blog on MSDN. Alfred’s solution and my should perform almost exactly the same even though he used Visual Basic and I used c#. This is since .Net languages all compile down to the same intermediate language. His tool is VB, mine is c#.
BUT my solution should win since I cheated. We both used brute force to solve it BUT I used threads which meant I could get a solution faster than he could since I was maxing out both my cores on my laptop instead of one. I would have used the Parallel Extensions but I lacked the install and without internet, I had to create them the hard way.
Explaining the brute force method., we go 1 by 1, verifying if a number is divisible by it. Lets take the number 12345 as it is semi large. I know it The number can be factored by 3, 5, 15 … and I stop trying when I hit 111 since 111 * 111 = 12321. Since I’m only interested in integers, 112 is past 12345 and isn’t a valid number. So I can check 3 to the floor of the square root of the number I’m attempting to find, incrementing by 2. Since to determine prime-ness, it must be an odd number or 2. Wikipedia has a few other, better, faster ways to determine the primality of a number. The fasted known method is the Elliptic curve primality test.
If you’d like to see the c# source code, you can download it here: http://www.peacelovecode.com/code/primenumbers/NextBiggestPrimeNumber.zip
What I did for my solution was used an abstract class and had both a threaded and non-threaded solution. This does the actual computation and notification. If I wanted to upgrade my solution’s performance, I just needed to tweak here. I also implemented events so I could update a UI to know that work was actually being executed.
Best of all, since my application uses the abstract, I can do some casting and do a very nice implementation call like this to execute my work:
IModelPrimeNumber prime;
if( chkThreaded.Checked )
prime = new PrimeNumberThreaded(Convert.ToUInt64(numPrimeNumberStartingPoint.Value), 2);
else
prime = new PrimeNumber(Convert.ToUInt64(numPrimeNumberStartingPoint.Value));
public abstract class IModelPrimeNumber
{
public delegate void PrimeNumberEventHandler(object sender, ulong number);
public delegate void PrimeNumberNotFoundEventHandler(object sender, ulong number, ulong divisibleBy);
public event PrimeNumberEventHandler NextAttemptedPrimeNumberEvent;
public event PrimeNumberEventHandler FoundPrimeNumberEvent;
public event PrimeNumberNotFoundEventHandler PrimeNumberNotFoundEvent;
protected bool _speedResult;
protected void InvokePrimeNumberNotFoundEvent(ulong number, ulong divisibleBy)
{
var createdEvent = PrimeNumberNotFoundEvent;
if (createdEvent != null)
createdEvent(this, number, divisibleBy);
}
protected void InvokeNextAttemptedPrimeNumberEvent(ulong number)
{
var createdEvent = NextAttemptedPrimeNumberEvent;
if (createdEvent != null)
createdEvent(this, number);
}
protected void InvokeFoundPrimeNumberEvent(ulong number)
{
var createdEvent = FoundPrimeNumberEvent;
if (createdEvent != null)
createdEvent(this, number);
}
public virtual TimeSpan StartWorking(bool speedResult)
{
return TimeSpan.MaxValue;
}
protected bool IsNumberPrime(ulong currentNumberFactoring, ulong calculateStop)
{
bool primeNumber = true;
if (!_speedResult)
InvokeNextAttemptedPrimeNumberEvent(currentNumberFactoring);
for (ulong i = 3; i <= calculateStop; i += 2)
{
if (currentNumberFactoring % i != 0)
continue;
primeNumber = false;
if (!_speedResult)
InvokePrimeNumberNotFoundEvent(currentNumberFactoring, i);
break;
}
return primeNumber;
}
}Since this is an abstract and I have virtual functions, I can override them! Here is how my threaded solution turned out. Notice how closely the engine is to my queuing system for my bartender.
public class PrimeNumberThreaded : IModelPrimeNumber
{
readonly ulong _startingPoint;
public bool IsRunning { get; set; }
public PrimeNumberThreaded(ulong startingPoint, int totalThreads)
{
_startingPoint = startingPoint;
if (_startingPoint % 2 == 0)
_startingPoint++;
_totalThreads = totalThreads;
for (int i = 0; i < totalThreads; i++)
ThreadPool.QueueUserWorkItem(FakeWorkToStartUpThreads);
}
private static void FakeWorkToStartUpThreads(object state)
{
return;
}
readonly AutoResetEvent _workWait = new AutoResetEvent(false);
int _workerThreads;
readonly int _totalThreads;
public override TimeSpan StartWorking(bool speedResult)
{
var watch = new Stopwatch();
var currentNumberFactoring = _startingPoint;
_speedResult = speedResult;
watch.Start();
while (!_foundPrime)
{
ThreadPool.QueueUserWorkItem(DoWork, currentNumberFactoring);
currentNumberFactoring += 2;
if (_workerThreads > _totalThreads)
_workWait.WaitOne();
_workerThreads++;
}
watch.Stop();
return watch.Elapsed;
}
bool _foundPrime;
private void DoWork(object state)
{
var currentNumberFactoring = (ulong)state;
var calculateStop = Convert.ToUInt64(Math.Floor(Math.Sqrt(currentNumberFactoring)));
var primeNumber = IsNumberPrime(currentNumberFactoring, calculateStop);
if (_workerThreads < _totalThreads)
_workerThreads--;
if (!primeNumber)
{
_workWait.Set();
return;
}
_foundPrime = true;
InvokeFoundPrimeNumberEvent(currentNumberFactoring);
_workWait.Set();
}
}