SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Prime Number Table Generator


Prime Number Table Generator

Author
Message
YeshuaAgapao
YeshuaAgapao
Ten Centuries
Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)

Group: General Forum Members
Points: 1309 Visits: 211
Comments posted to this topic are about the item Prime Number Table Generator



YeshuaAgapao
YeshuaAgapao
Ten Centuries
Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)

Group: General Forum Members
Points: 1309 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.



YeshuaAgapao
YeshuaAgapao
Ten Centuries
Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)Ten Centuries (1.3K reputation)

Group: General Forum Members
Points: 1309 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.



Iwas Bornready
Iwas Bornready
SSC-Insane
SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)

Group: General Forum Members
Points: 22716 Visits: 885
Thanks for the script.
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search