January 3, 2008

Note 71 of 113 of Delphi 2007 Handbook

Note 71 (a rather useless one): The IsPrime function is a slow function used to check whether a number is a prime number. I used this function in past editions of Mastering Delphi (up to version 7) because I needed a slow CPU-intensive operation. I know it could be written to perform the same task much faster, but in this case I simply don't need speed, quite the opposite.

Although this is quite useless information outside of the scope of the book, do you know where I can find a very optimized version of a function to check for prime numbers? Could be an interesting comparison...

This blog post is part of my "113 Delphi 2007 Handbook Notes" blogging project, to promote my new Delphi book.

posted by
marcocantu @ 10:37AM | 4 Comments
[0 Pending]

### Handbook Note 71/113 Is Prime Number Function

Testing a number for primality is not an easy task,
and many methods were developed - especially now that
cryptography relies so heavily on prime numbers. Some
are just "probabilistic", other are "deterministic".
See for example Miller-Rabin, or the newer Agrawal-
Kayal-Saxena.
PS: delete my previous post, please, it was submitted
by mistake.

Comment by Luigi D. Sandon on January 3, 10:54

### Handbook Note 71/113 Is Prime Number Function

Yes, much simple way - not a deterministic, the
probability function; see the "Rabin-Miller" test for
more details.
the "Lehmann" sample:
<pre>
// tested on D7
program test_lehmann;
{$APPTYPE CONSOLE}
uses
SysUtils;
// the probability of prime if true - not less 0.5
function lehmann_probe(p: integer): Boolean;
var
a,z,r,q: int64;
begin
p := abs(p);
// test for small numbers
if p<4 then
begin
result := true;
exit;
end;
// get the random a for the probe
repeat a := random(p); until a >= 3;
// calculate a^((p-1)/2) mod p
z := a;
r := (p-1) div 2;
q := 1;
while r>0 do
begin
z := (z*z) mod p;
if (r and 1) = 1 then q := (q * z) mod p;
r := r shr 1;
end;
// the result
result := (q = 1) or (q = (p-1));
end;
// numbers must be big!
function prime_lehmann(p,n: Integer): Boolean;
var
m: Integer;
begin
if n<0 then
begin
result := false;
exit;
end;
// this is only for this demo
write('is the ',p,' prime? - ');
m := n;
result := true;
while (result) and (n>0) do
begin
result := lehmann_probe(p);
dec(n);
end;
// this is only for this demo
writeln(result,', number of probes ',m-n);
end;
var
i,j: Integer;
begin
randomize;
j := 100+random(1000000);
for i := j to (j+100) do prime_lehmann(i,30);
readln;
end.
</pre>

Comment by Leonid Koninin on January 3, 18:12

### Handbook Note 71/113 Is Prime Number Function

sorry, mistype in previous source, must be:
// the probability of prime if true - not less 0.5
function lehmann_probe(p: integer): Boolean;
var
a,z,r,q: int64;
begin
p := abs(p);
// test for small numbers
if p<4 then
begin
result := true;
exit;
end;
// get the random a for the probe
repeat a := random(p); until a >= 3;
// calculate a^((p-1)/2) mod p
z := a;
r := (p-1) div 2;
q := 1;
while r>0 do
begin
if (r and 1) = 1 then q := (q * z) mod p;
z := (z*z) mod p;
r := r shr 1;
end;
// the result
result := (q = 1) or (q = (p-1));
end;

Comment by Leonid Koninin on January 3, 18:24

### Handbook Note 71/113 Is Prime Number Function

When you think of core Delphi functions and Fast, you
should think of FastCode ;-)
http://fastcode.sourceforge.net/challenge_content/IsPrime.html
Seems to be an old BV style because the RTL function
is not included (Which nowadays is)
So I can't give the correct speedup above RTL, but I
assume it's goood :)

Comment by Davy Landman
[http://delphi-snippetrs.blogspot.com]
on January 7, 17:18

There are currently 0 pending (unapproved) messages.