Ward Pond's SQL Server blog

Ruminating on issues pertinent to the design and development of sound databases and processes under Microsoft SQL Server 2008, SQL Server 2005, and SQL Server 2000 (while reserving the right to vent about anything else that's on my mind)

Blogs

Database Programming: Denis' Prime Number Challenge: A New Leader

  • Comments 12
  • Likes

Well, folks, there's a new sheriff in town..  this is a continuation of a conversation here and here.

I've tweaked Hugo's syntax to further filter the initial seive population (similar to the pre-filtering present in the discredited tangent).  Where's Hugo's syntax took 8 seconds on my laptop and Denis' took 6 seconds, this version takes under 3 seconds!

I'm going to let the discredited version run overnight..  hopefully somebody can do even better (although from two days down to three seconds is pretty cool; thanks, Hugo!).

Here's the current leader (note that this version is also tweaked slightly to reflect the schema for my number source):

DECLARE @Start datetime, @End datetime

SET     @Start = CURRENT_TIMESTAMP

DECLARE @Limit int

SET     @Limit = 1000000

 

-- Initial fill of sieve;

-- filter out low hanging fruit right from the start.

INSERT  INTO dbo.Primes (Prime)

SELECT  Id

FROM    dbo.SetBuilder

WHERE  (Id % 2  <> 0 OR Id = 2)

AND    (Id % 3  <> 0 OR Id = 3)

AND    (Id % 5  <> 0 OR Id = 5)

AND    (Id % 7  <> 0 OR Id = 7)

AND    (Id % 11 <> 0 OR Id = 11)

AND    (Id % 13 <> 0 OR Id = 13)

AND    (Id % 17 <> 0 OR Id = 17)

AND    (Id % 19 <> 0 OR Id = 19)

AND    (Id % 23 <> 0 OR Id = 23)

AND    (Id % 29 <> 0 OR Id = 29)

AND    (Id % 31 <> 0 OR Id = 31)

AND     Id <> 1

AND     Id <= @Limit

 

-- Set @Last to 31, since multiples of 31 and all primes lower have already been processed

DECLARE @First int, @Last int

SET     @Last = 31

 

WHILE   @Last <= SQRT(@Limit) + 1

BEGIN

  -- Find next prime as start of next range

  SET @First =

             (SELECT TOP (1) Prime

              FROM     dbo.Primes

              WHERE    Prime >= @Last + 1

              ORDER BY Prime)

 

  -- Range to process ends at square of starting point

  SET @Last = @First * @First

 

  DELETE FROM dbo.Primes

  WHERE       Prime IN (SELECT     n.Id * p.Prime

                        FROM       dbo.Primes  AS p

                        INNER JOIN dbo.SetBuilder AS n

                              ON   n.Id     >= p.Prime

                              AND  n.Id     <= @Limit / p.Prime

                        WHERE      p.Prime  >= @First

                        AND        p.Prime  <  @Last)

END

 

SET     @End = CURRENT_TIMESTAMP

SELECT  @Start AS Start_time, @End AS End_time,

        DATEDIFF(ms, @Start, @End) AS Duration,

        COUNT(*) AS Primes_found, @Limit AS Limit

FROM    dbo.Primes

Well, Denis and Hugo, what have you got? J

     -wp

Comments
  • Our blogging site is going to go dark in an hour or so for a software upgrade, so I won't be able to...

  • I've jumped in...

    http://robfarley.blogspot.com/2006/09/primes.html
    http://robfarley.blogspot.com/2006/09/more-on-primes.html

    Let me know what you think.

  • Denis' Prime Number Challenge just won't die.&amp;nbsp; I think this topic has spurred more dialog than any&amp;nbsp;other...

  • Oh no, you may be thinking, he has gone off the deep end. Preparing for his talk on normalization...

  • No less a figure than Louis Davidson has weighed in on the Prime Number Challenge . I left a comment

  • Hi all,

      Pardon me if its too late a comment. Just wanted to tell that it was a wonderful implementation. Enjoyed reading through the posts. Nothing much to tweak from my side, though I thought hard and realised that I am not even in the league :)

    -Omni

  • It's never too late to chime in, Omni, and thanks for your kind words!

        -wp

  • Great post, explained really well and I could really understand. Thank you.

Your comment has been posted.   Close
Thank you, your comment requires moderation so it may take a while to appear.   Close
Leave a Comment