Delphi Handbooks Collection


Delphi XE Handbook


Delphi 2010 Handbook


January 3, 2008

Handbook Note 71/113: Is Prime Number Function

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.





 

4 Comments

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


Post Your Comment

Click here for posting your feedback to this blog.

There are currently 0 pending (unapproved) messages.