PrimeFinder

steve — Wed, 26 Nov 2008 01:50:00 GMT

Alright everyone has written the obligatory "Hello World!" program when they start to learn a new language. I have my own variety of that practice and its PrimeFinder. Whenever I start to learn a new language I write a program that finds primes. I know this may sound a little strange but this normally allows me to practice a number of new skills and techniques as well as see if there is a way I can improve both my prime number finding logic and find out if the new language has anything to offer that is unique for this task. In this post I'll examine PrimeFinder written in PowerShell, C#, and T-SQL. I will discuss each and the surprises I found out about each. Feel free to take this as a challenge to find more efficient ways in these languages or any others; I would like to see any different solutions that are more efficient.

There are some rules though, here they are:

1. The solution must be robust enough to find all primes ranging from 1 to 2,147,483,647 (signed 4 byte int limit)

2. The solution must output the prime numbers in some manner which is recordable. (printing to standard out is fine since that can be pushed into a text file)

3. The solution must restartable, or easily changed to a state that allows it to be restartable. In that it can produce a certain number of primes, stopped and pick up where it left off. (this is the reason for the requirement #2, very flexible on this requirment)

4. The solution must be timed

5. The solution should find the first 10000 primes by default when executed

6. The solution is allowed three primary constants of 1, 2, and 3. These are allowed to remove any single use code that would be in place to find these 3 primes.

The first solution was written in C# and is the reason that I was looking into the problem to begin with. This code was a pretty much brute force attack against prime numbers but it seems to be very efficient. I am running this code in a screen shot below wrapped in a a few lines of PowerShell code to produce an easy to read timer at the bottom of the screen shot.

7.48 seconds not bad!

Save the following code in a .cs file, compile it should be exectable.

using System;
namespace fibich.math
{
class primeFinder
{
  const int prime1=1;
  const int prime2=2;
  const int prime3=3;

  static void Main()
  {
   //Variable Decleration
   bool isPrime =true;
   int possiblePrime =prime3;
   int primeCount=0;

   //Const Output
   Console.WriteLine("Starting to find Primes");
   Console.WriteLine("prime:" + prime1.ToString());
   Console.WriteLine("prime:" + prime2.ToString());
   Console.WriteLine("prime:" + prime3.ToString());

//Finding Primes

   while (primeCount<10000)
   {
    possiblePrime+=prime2;
    for (int primeFinder =prime3; primeFinder<Math.Sqrt(possiblePrime)+1;primeFinder+=prime2)
    {
     if ((possiblePrime % primeFinder)==0)
     {
      isPrime=false;
      break;
     }
     else
     {
      isPrime=true;
     }
    }
    if (isPrime==true)
    {
     primeCount++;
     Console.WriteLine("prime:"+possiblePrime.ToString()+" primeCount:"+primeCount.ToString());
    }

   }
  return;
  }
}
}

The second solution I offer up is written in PowerShell. The reason I wrote this was because I wrote the C# solution I noticed how similar the syntax was and I figured why not I it only required a few changes to the code to make it executable as a powershell script. Basically I added $ all my variables, changed == to -eq and < to -gt removed the Console.WriteLine from the output statements and that was about it. I wrapped this code in the same PowerShell statements to produce the exact same timer information.

277 seconds! Wow that was over 37 times slower than the C# solution.

I expected PowerShell to be slower but man I didn't expect that, I was thinking maybe 10 times as worst. Hey PowerShell's power is not in number crunching, its a scripting environment and gets its power from delivering more productivity per key stroke, empowering the developer not squeezing every ounce of performance from a process so I'm not disappointed. Just a little surprised.

Save the following code to a ps1 file enable scripts in PowerShell and you should be good to go.

#Variable Decleration
$primeCount=1
$prime1=1;
$prime2=2;
$prime3=3;
$isPrime =$true;
$possiblePrime =$prime3;
$primeCount=0;

#Const Output
"Starting to find Primes";
"prime:" + $prime1.ToString();
"prime:" + $prime2.ToString();
"prime:" + $prime3.ToString();

#Finding Primes
while ($primeCount -lt 10000)
{
$possiblePrime+=$prime2;
for ($primeFinder =$prime3; $primeFinder -le ([Math]::Sqrt($possiblePrime))+1;$primeFinder+=$prime2)
{
  if (($possiblePrime % $primeFinder) -eq 0)
  {
   $isPrime=$false;
   break;
  }
   else
  {
   $isPrime=$true;
  }
}
  if ($isPrime -eq $true)
  {
   $primeCount++;
   "prime:"+$possiblePrime.ToString()+" primeCount:"+$primeCount.ToString();
  }
}

The final solution is something a little different. It’s a T-SQL solution, where the prime numbers that are found are used to find the next prime numbers. I was hoping that this approach would be more efficient than the brute force used by the other two solutions and it still maybe at the higher range end of prime numbers. This solution also utilizes set based logic to calculate the modulus of each number, instead of trying one number at a time against the trial prime number.

No Screen shot unfortunately but this solution took 70 seconds so it came in third in the trails to find the first 10,000 primer numbers.

This solution requires a database name dataHub, a schema named numbers and a table named primes in that schema.

use datahub

BEGIN

if not exists(select * from sys.schemas where name='numbers')

BEGIN

execute('Create Schema numbers authorization dbo')

print 'schema created:Numbers'

END

else

BEGIN

print 'schema already exists:Numbers'

END

use datahub

IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[Numbers].[primes]') AND type in (N'U'))

DROP TABLE [Numbers].[primes]

create table numbers.primes (

prime bigint not null primary key

,version int not null

)

use dataHub

IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[Numbers].[primeFinder]') AND type in (N'P', N'PC'))

DROP PROCEDURE [Numbers].[primeFinder]

create procedure numbers.primeFinder

@primeCount int = 10000

,@purge bit =0

declare @version int

declare @possiblePrime bigInt

declare @primeCounter int

set @primeCounter=0

if @purge=1

BEGIN

delete numbers.primes

set @version=1

--insert into numbers.primes

--(prime,version)

--values(1,@version)

--insert into numbers.primes

--(prime,version)

--values(2,@version)

insert into numbers.primes

(prime,version)

values(3,@version)

END

else

BEGIN

select @version = coalesce(max(version),0) from numbers.primes

END

select @possiblePrime = max(prime) from numbers.primes

while @primeCounter <@primeCount

BEGIN

set @possiblePrime=@possiblePrime+2

if not exists(select 1 from numbers.primes where prime<=sqrt(@possiblePrime) and @possiblePrime%prime=0)

BEGIN

insert into numbers.primes

(prime,version)

values(@possiblePrime,@version)

set @primeCounter=@primeCounter+1

END

Well that’s it; I look forward to hearing back from everyone and seeing any different or new takes on these solutions. I already I have an idea for a combination solution utilizing the CLR integration in SQL Server, but that will have to wait to another time.

Two Projects

steve — Wed, 28 Nov 2007 17:21:00 GMT

I have decided that the best way to have a more interactive community blog is to have posts that follow a project from start to finish. To accomplish this goal and because I know I get board if I only have one project I decided to start posting about two personal projects on this site. “theSystem” and another project “SOAK”. Each of these projects has entirely different goals and each will allow me to explore and learn about different areas of SQL Server (and its components….SSIS, Service Broker, Reporting Services, ect…)

The first is called “theSystem” and is my attempt to create a game engine based wholly SQL Server. I know this sound like a daunting task and may make someone to ask “why would you want to do this? “ The answer is simple, the challenge, I have been kicking around the idea o building a game engine since about 5^th grade when I first came across nethack/rogue. I think SQL Server is up to the challenge, and when I say game engine I mean the game logic, functions, and data required making a game like this progress. If I ever get around to building a front end for it, it will be in something else…don’t know what. The current plan is to have all user functions available via stored procedures (either T-SQL or .NET) and make them available to users through and ODBC/OLE/JDBC connection and through the web via an XML interface.

· SQL Server 2005 based gaming engine

· All “business/game” logic to be encapsulated in SQL Server objects (T-SQL or .NET)

· All game data to be stored in SQL Server 2005

· All user functions to be available through ODBC/OLE/JDBC connections (XML Web Service when time allows)

· All users to get individual SQL Server accounts (we will see how this works out)

The second is “SOAK”, a Data Warehousing and Master Data Management project dedicated to collecting, consolidating, cleansing all of the publicly available datasets found on the web for free. (No sending off for CD’s or any other costs). The examples attached to this project will not only give overall view of how to do something in SSIS for instance but provide actual code for a particular data set that is usable by anyone who needs to gather this data. This system will also provide the ability for users to enter their own statistical information for given datasets to allow the system to grown on its own. The current plan is to have all user functions available via stored procedures (either T-SQL or .NET) and make them available to users through and ODBC/OLE/JDBC connection and through the web via an XML interface. Finally statistical information in the system should be made available through Reporting Services reports.

· Datasets to be pulled from the web for free

· Allow users to enter updated statistics/information on pre-defined datasets

· All user Functions to be available through ODBC/OLE/JDBC Connections(XML Web Service when time allows)

· All users to get individual SQL Server accounts (we will see how this works out)

· Provide reporting thru MS Reporting Services

Hopefully this will be a good learning experience for everyone including myself. If you see me going down the wrong path some let me know. I plan on making the code base of each project available on line. As each of these projects is flushed out I will utilize this post to document ground rules for each. Finally if you know of any other projects like these let me know… I did a quick Google search and couldn’t find anything resembling these two ideas so I figured I would try to take them on.

Steve Fibich : SOAK

PrimeFinder

Two Projects