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

Prime Number Table Generator Expand / Collapse
Author
Message
Posted Friday, July 10, 2009 10:29 PM


Say Hey Kid

Say Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey Kid

Group: General Forum Members
Last Login: Monday, October 21, 2013 4:37 PM
Points: 701, Visits: 211
Comments posted to this topic are about the item Prime Number Table Generator


Post #751527
Posted Wednesday, July 15, 2009 6:24 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: 2 days ago @ 7:59 PM
Points: 1,945, Visits: 3,080
This is fun to me because I submitted an article on several ways to generate a table of primes weeks ago. It should be in SIMPLE TALK shortly. I did not classify the primes or use floatingp point math in my solutions.

Books in Celko Series for Morgan-Kaufmann Publishing
Analytics and OLAP in SQL
Data and Databases: Concepts in Practice
Data, Measurements and Standards in SQL
SQL for Smarties
SQL Programming Style
SQL Puzzles and Answers
Thinking in Sets
Trees and Hierarchies in SQL
Post #753359
Posted Thursday, July 16, 2009 11:38 PM


Say Hey Kid

Say Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey Kid

Group: General Forum Members
Last Login: Monday, October 21, 2013 4:37 PM
Points: 701, Visits: 211
I just uploaded a new version

I got the fastest method in http://sqlblog.com/blogs/hugo_kornelis/archive/2006/09/23/Prime-numbers.aspx beat! Gotta give this blogger credit though because I'm using his idea of using modulo to eliminate the slow floating point math (indirect suggestion by Joe Celko's previous post). I'm pretty sure others can beat me though, as long as the fancier algorithms doesn't compromise index usage in the factor-side's use of the table of numbers.


STATISTICS TIME stats for 78,498 primes up to 1,000,000
Ran on local 2008 server on a 2005 Dell XPS M170 (4 years old) laptop with Intel Centrino Pentium-M 2.0 GHZ single-core, 2GB of DDR2 SD-Ram, and 60 GB 7200 RPM hard drive.

main populate, build two nonclustered indexes, stats auto create on the two indexes, populate flags, grand total

SQL Server Execution Times:
CPU time = 17032 ms, elapsed time = 17298 ms.

(78498 row(s) affected)

SQL Server Execution Times:
CPU time = 156 ms, elapsed time = 154 ms.

SQL Server Execution Times:
CPU time = 156 ms, elapsed time = 162 ms.

SQL Server Execution Times:
CPU time = 125 ms, elapsed time = 142 ms.

SQL Server Execution Times:
CPU time = 125 ms, elapsed time = 154 ms.

SQL Server Execution Times:
CPU time = 1844 ms, elapsed time = 1854 ms.

(78498 row(s) affected)

SQL Server Execution Times:
CPU time = 19235 ms, elapsed time = 19567 ms.







STATISTICS TIME stats for 61,922 primes up to 772,524, using my normal table of numbers that completely fills a 2-level clustered index (more causes it to go to 3 levels resulting in 3 logical I/Os per seek instead of 2)
Ran on local server on a 2005 Dell XPS M170 (4 years old) laptop with Intel Centrino Pentium-M 2.0 GHZ single-core, 2GB of DDR2 SD-Ram, and 60 GB 7200 RPM hard drive.

main populate, build two nonclustered indexes, stats auto create on the two indexes, populate flags, grand total

SQL Server Execution Times:
CPU time = 12328 ms, elapsed time = 12639 ms.

(61922 row(s) affected)

SQL Server Execution Times:
CPU time = 156 ms, elapsed time = 154 ms.

SQL Server Execution Times:
CPU time = 156 ms, elapsed time = 167 ms.

SQL Server Execution Times:
CPU time = 125 ms, elapsed time = 142 ms.

SQL Server Execution Times:
CPU time = 125 ms, elapsed time = 154 ms.

SQL Server Execution Times:
CPU time = 1468 ms, elapsed time = 1473 ms.

(61922 row(s) affected)

SQL Server Execution Times:
CPU time = 14140 ms, elapsed time = 14628 ms.



Post #754625
Posted Sunday, July 19, 2009 5:21 PM


Say Hey Kid

Say Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey KidSay Hey Kid

Group: General Forum Members
Last Login: Monday, October 21, 2013 4:37 PM
Points: 701, Visits: 211
Put up a new version (it'll get moderator-approved sometime monday). Still same the brute-force method, but hard-coded checks up to the first full data page of the table of numbers (622 for mine; put up to 625 in code) and limited the factor division tests to 627 to the square root of the candidate prime. This sped it up by 40% to one million . Primes from 1 to 250K might be slower. A smaller change eliminated the sort for the ROW_NUMBER (for nth prime queries), but it had only a .1 second impact.

The speed of this is solely because it is 100% set-based, and now limits data-access on the table of numbers (eliminating it for 84%, removing 1 logical I/O for the rest), not because of any fancy algorithm. Coding in C++ with the fancy algorithms and using SQLBulkCopy to insert the data would still be the fastest way.


1-to-1,000,000

Table 'Primes'. Scan count 0, logical reads 158311, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Counter'. Scan count 81940, logical reads 328566, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 10172 ms, elapsed time = 10283 ms.

(78498 row(s) affected)

Table 'Primes'. Scan count 1, logical reads 265, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 156 ms, elapsed time = 153 ms.

SQL Server Execution Times:
CPU time = 156 ms, elapsed time = 158 ms.

Table 'Primes'. Scan count 1, logical reads 225, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 140 ms, elapsed time = 140 ms.

SQL Server Execution Times:
CPU time = 140 ms, elapsed time = 151 ms.
Table 'Primes'. Scan count 1, logical reads 795074, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 1, logical reads 158276, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 1843 ms, elapsed time = 1857 ms.

(78498 row(s) affected)

SQL Server Execution Times:
CPU time = 12656 ms, elapsed time = 12808 ms.



1-to-772,524 (table of numbers that fits a 2-level clustered index snugly, doubled by the *2+1)

Table 'Primes'. Scan count 0, logical reads 124884, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Counter'. Scan count 63469, logical reads 191027, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 7156 ms, elapsed time = 7292 ms.

(61922 row(s) affected)

Table 'Primes'. Scan count 1, logical reads 210, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 125 ms, elapsed time = 117 ms.

SQL Server Execution Times:
CPU time = 125 ms, elapsed time = 124 ms.

Table 'Primes'. Scan count 1, logical reads 177, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 94 ms, elapsed time = 115 ms.

SQL Server Execution Times:
CPU time = 94 ms, elapsed time = 118 ms.
Table 'Primes'. Scan count 1, logical reads 627187, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 1, logical reads 124854, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 1437 ms, elapsed time = 1435 ms.

(61922 row(s) affected)

SQL Server Execution Times:
CPU time = 9187 ms, elapsed time = 9395 ms.



Post #755431
« Prev Topic | Next Topic »

Add to briefcase

Permissions Expand / Collapse