-- Solution by Steve Kass
If you want to further optimize the function with a naïve
method, you
can populate the primes table with all primes up to the first prime that
is greater than the square root of the maximum BIGINT value (max
BIGINT = 9,223,372,036,854,775,807, first prime > sqrt(max
BIGINT) =
3,037,000,507). This would mean populating the primes table with
146,144,319 primes, and the table size will be a bit under 2.5 GB. To
achieve this you can use the usp_populateprimes procedure I provided
earlier. With the current implementation of the procedure it would take
a day or two to complete the task, but keep in mind that you do this
only once. Here’s the code you would need to run (again, it will take a
day or two to complete!):
exec dbo.usp_populateprimes
@max = 3037000507;
I provided a fairly simple implementation of the usp_populateprimes
procedure. Of course you can optimize it using similar concepts to the
ones described for optimizing the fn_isprime function. Either way, if
you populate the primes table with all primes up to at least
3,037,000,507, you can revise the fn_isprime function to a much
simpler form that doesn’t rely on the primorial-coprime approach. To
test the primality of @n, assuming @maxp is the maximum prime
stored in the primes table, for @n <= @maxp you simply
check
whether a prime p exists in the primes table where p = @n. This would
require a single seek operation in the clustered index on the primes
table and the answer is pretty much instantaneous. For @n > @maxp,
you would need to check whether any p from 2 to floor(sqrt(@n))
divides @n. Here’s the revised implementation of fn_isprime
assuming
you populated the primes table with all primes up to 3,037,000,507:
-- function fn_isprime, version 5
if object_id('dbo.fn_isprime') is not null
drop function dbo.fn_isprime;
go
create function
dbo.fn_isprime(@n
as bigint) returns bit
with returns null on null input
as
begin
-- check if @n
is an obvious prime or nonprime
declare
@explicitprime as
bigint;
set
@explicitprime = 23;
if @n < @explicitprime
if
@n in (2, 3, 5, 7, 11, 13, 17, 19) return 1 else return 0;
if @n%2 = 0 or @n%3 = 0 or @n%5 = 0 or @n%7 = 0
or @n%11 = 0 or @n%13 = 0 or @n%17 = 0 or @n%19 = 0 return 0;
if @n < cast(square(@explicitprime) as bigint) return 1;
declare @sqrt
as bigint, @maxp as bigint;
set @sqrt = cast(sqrt(@n) as bigint);
set @maxp = (select max(p) from dbo.primes);
return
case
when @n <= @maxp then
case when exists
(select * from dbo.primes where p = @n)
then 1 else 0 end
when
@sqrt <= @maxp then
case when exists
(select * from dbo.primes where p <= @sqrt and @n%p = 0)
then 0 else 1 end
else null
end
end;
go
Version 5 of the fn_isprime
function had the following run times to test
the primality of the following primes:
10,000,000,000,037: < 1 sec
100,000,000,000,031: < 1 sec
1,000,000,000,000,037: 2 sec
10,000,000,000,000,061: 6 sec
100,000,000,000,000,003: 18 sec
1,000,000,000,000,000,003: 54 sec
9,223,372,036,854,775,783: 233 sec
That’s probably as good as you can get with a naïve method
using set-
based logic. But apparently you can get much faster solutions with
non-naïve methods using iterative logic.
Probabilistic Techniques
Probabilistic techniques rely on some degree of randomization
as part
of their logic. Those techniques can be very fast. When reporting that
the input is a composite, the answer is certain, but when reporting that
the input is a prime, you don’t get 100% assurance. You can control
the probability for reporting a false prime with the number of tests that
you apply. These techniques are very popular when 100% assurance
is not required. You can still get extremely fast implementations with a
very low probability for reporting a false prime. Examples for
probabilistic techniques include the Miller-Rabin primality test and
Solovay-Strassen primality test.
As far as I can tell, existing fast probabilistic techniques
are suited for
iterative/recursive implementations and not set-based ones. You can
read more about such techniques here:
http://en.wikipedia.org/wiki/Primality_test.
Fast Deterministic Techniques
Fast deterministic techniques provide 100% assurance that an
input
reported as a composite is a composite and that an input reported as a
prime is a prime. Examples of fast deterministic tests include a version
of the Miller-Rabin test that is turned into a deterministic test and the
AKS primality test. Steve Kass implemented a solution based on a
deterministic version of the Miller-Rabin test. That’s the fastest
primality test I’ve ever seen in T-SQL. It runs well under 1 second for
any prime (his version supports inputs up to one-half max BIGINT).
Here’s Steve’s description of his solution and a pointer to a
website
where you can get more details, followed by the definitions of auxiliary
functions and the primality test function:
“Here is
a function that should work for integers up to one-half the
maximum bigint. It's designed to be efficient for very large inputs.
For
example, it tests the odd integers between 300000000000001 and
300000000001000, finding the 24 primes, in about 6 seconds on a
modest machine. (Equivalent CLR code would probably be a lot
faster.)
Prev. page
1
2
3
4
5
[6]
7
next page 
