Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase «««1920212223

Celko's Summer SQL Stumpers: Prime numbers Expand / Collapse
Author
Message
Posted Monday, August 3, 2009 7:34 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Yesterday @ 7:56 PM
Points: 36,775, Visits: 31,230
Mike Ross (8/3/2009)
Jeff Moden (8/3/2009)
Heh... What side effects? The function is the one with "side effects". You can't raise the proper error if you need it. The function also has the side effect of being slower even if it's just a bit so. The in-memory solution isn't actually faster as you stated... not even on your box.

Whatever. Thanks for running the test, Mike.


Ha ha. Fire off a bunch of disk-intensive tasks and then try your "test" again.
The function is faster where it counts, on our production system. Even if it wasn't, the reduced dependencies make it worth it.

A "side effect" is not where one method runs less than 10ms faster under a very contrived and unrealistic test. Nor is it one of the many design limitations in SQL2000.

A side effect and dependency is having one more, completely unnecessary, table to: script, track, and manage.

Haven't you ever had a DBA or developer change the contents of a table on you, for very good-seeming reasons? Or use an undocumented table?

Our functions are handled very well by source control. Further, if someone changes the function code, the interface and results stay the same -- no side effects.

I suppose we could try to put table contents under source control, but that seems absurd and has not been necessary for anything else.


Heh... you and I certainly have different ideas as to what a side effect may be. We also have different ideas what a DBA is allowed to do or not. We also keep source control for all such reference/tool tables and the code that generates their initial values.

You never did say... which RDBMS are you using on the non-MS servers?


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #764512
Posted Wednesday, August 5, 2009 4:59 PM
SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Friday, July 25, 2014 8:55 AM
Points: 1,615, Visits: 2,118
Just curious if there's any word yet on when the winner will be announced...

Steve
(aka smunson)


Steve
(aka sgmunson)

Internet ATM Machine
Post #765896
Posted Thursday, August 6, 2009 1:47 AM


Mr or Mrs. 500

Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500

Group: General Forum Members
Last Login: Friday, July 25, 2014 3:19 AM
Points: 577, Visits: 2,503
We're aiming for Monday. That's the date we originally promised, not quite realizing how many entries there would be!


Best wishes,

Phil Factor
Simple Talk
Post #766005
Posted Tuesday, August 11, 2009 6:06 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Wednesday, February 10, 2010 11:47 AM
Points: 34, Visits: 136
Hey! How is it going? When will we have any interesting news?
Post #768514
Posted Tuesday, August 11, 2009 7:54 AM


Mr or Mrs. 500

Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500

Group: General Forum Members
Last Login: Friday, July 25, 2014 3:19 AM
Points: 577, Visits: 2,503
We made it into a newsletter editorial http://www.sqlservercentral.com/articles/Editorial/67817/ to give the competition a bit of publicity! Don't tell me you don't subscribe to the newsletter!


Best wishes,

Phil Factor
Simple Talk
Post #768607
Posted Monday, August 24, 2009 11:45 AM
SSC-Addicted

SSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-Addicted

Group: General Forum Members
Last Login: Monday, March 10, 2014 9:05 AM
Points: 421, Visits: 363
I decided to use Sequence table only.
I have two methods on the implementation of same algorithm. One is using set operations while the other is using a WHILE loop.

Thsi is the algorithm: Remove1 and Start from 2, remove all multiples of each number and get the rest. Finally I will select the remaining numbers;

-- Method 1: Using WHILE LOOP
DECLARE @n int, @i int
SELECT @n = FLOOR(SQRT(MAX(Seq))) FROM sequence;

DELETE sequence WHERE Seq = 1;
SET @i=2;
WHILE @i <=@n
BEGIN
DELETE sequence WHERE seq % @i = 0 AND seq >= @i*@i;
SELECT @i = MIN(seq) FROM sequence WHERE seq > @i;
END
SELECT * FROM sequence;


-- Method 2: SET Based Delete
DECLARE @n int;
SELECT @n = FLOOR(SQRT(MAX(Seq))) FROM sequence;
DELETE sequence WHERE seq =1;

DELETE b
FROM sequence a INNER JOIN sequence b
ON a.seq<= FLOOR(SQRT(b.seq)) AND b.seq %a.seq =0;

SELECT * FROM sequence;


Both methods, When I compared for 100,000 numbers, perform under 1.5 seconds. The first method was slightly faster around (100 milli seconds) Even though I expected the first method to be using more resources due to multiple deletes, It had a total of 7,887 logical reads while the second method had 663,523 logical reads. It also created a worktable. The reason is the first method effectively removes all non-primary numbers.
Note: All calculations are only for the code submitted here. (Creation of the sequence table and populating data are excluded for calculations).


I will go for the first method.




Cheers,
Prithiviraj Kulasingham

http://preethiviraj.blogspot.com/
Post #776203
Posted Monday, August 24, 2009 3:27 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Friday, June 13, 2014 8:09 PM
Points: 18, Visits: 51
The problem with the first method is you are assuming a sequence table is already there, and that removing entries from it isn't an issue. If the sequence table is existing, then it can be assumed it sould be left as-is or at least re-constructed at the end, otherwise it wouldn't have been in existance in the first place.

Also, we ended up going with 10,000,000 as a figure to reach because lower figures were too fast to compare.
Post #776329
Posted Thursday, March 14, 2013 8:13 AM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Wednesday, July 23, 2014 3:35 PM
Points: 2,393, Visits: 3,399
This is about the simplest method I can think of.
Executes for about 1.5 seconds to get all primes below 1,000,000.

CREATE TABLE	#Numbers
(
Prime INT NOT NULL,
Number BIGINT PRIMARY KEY CLUSTERED
);

DECLARE @Max INT = 1000000;

WITH n0(p)
AS (
SELECT 1

UNION ALL

SELECT 1
), n1(p)
AS (
SELECT 1
FROM n0 AS a
CROSS JOIN n0 AS b
),n2(p)
AS (
SELECT 1
FROM n1 AS a
CROSS JOIN n1 AS b
),n3(p)
AS (
SELECT 1
FROM n2 AS a
CROSS JOIN n2 AS b
),n4(p)
AS (
SELECT 1
FROM n3 AS a
CROSS JOIN n3 AS b
),n5(p)
AS (
SELECT 1
FROM n4 AS a
CROSS JOIN n4 AS b
)
INSERT #Numbers
(
Prime,
Number
)
SELECT f.Prime,
f.Prime * f.Prime AS Number
FROM (
SELECT TOP (1 + @Max / 30)
30 * ROW_NUMBER() OVER (ORDER BY p)
FROM n5
) AS v(Value)
CROSS APPLY (
VALUES (v.Value - 23),
(v.Value - 19),
(v.Value - 17),
(v.Value - 13),
(v.Value - 11),
(v.Value - 7),
(v.Value - 1),
(v.Value + 1)

) AS f(Prime)
WHERE f.Prime <= @Max;

SELECT Prime
FROM (
VALUES (2),
(3),
(5)
) AS v(Prime)
WHERE Prime <= @Max

UNION ALL

SELECT n.Prime
FROM #Numbers AS n
WHERE NOT EXISTS (
SELECT *
FROM #Numbers AS p
WHERE p.Number <= n.Prime
AND n.Prime % p.Prime = 0
)

DROP TABLE #Numbers;




N 56°04'39.16"
E 12°55'05.25"


  Post Attachments 
Third.txt (1 view, 1.06 KB)
Post #1430992
« Prev Topic | Next Topic »

Add to briefcase «««1920212223

Permissions Expand / Collapse