Prime Number Table Generator

  • Comments posted to this topic are about the item Prime Number Table Generator

  • 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.

  • 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.

  • Thanks for the script.

Viewing 4 posts - 1 through 3 (of 3 total)

You must be logged in to reply to this topic. Login to reply