# Board index » delphi » Prime numbers - a faster way

## Prime numbers - a faster way

2005-07-21 06:03:50 AM
delphi102
Just wonder why it is not used as a base simpe rule to determinate
prime numbers in winner John O'Hara roitines, since all primes are in
form n*6-1 and n*6+1 (except for 2 and 3, where *n* is from 1 to
infinity). Approach is twice faster than simple adding 2.
A part of a code from my hash unit:
---
function SZIsPrime(Number : Cardinal) : Boolean;
var
I, J : Cardinal;
begin
if Number < 4 then
Result := Number>1
else begin
Result := False;
I:= (Number mod 6);
if (I=1) or (I=5) then
begin
J := round(sqrt(Number));
I := 5;
while I <= J do
begin
if (Number mod I = 0) then
Exit;
if (Number <>J) and
(Number mod (I+2) = 0) then
Exit;
inc(I,6);
end;
Result := True;
end;
end;
end;
---
Sasa
--
www.szutils.net

## Re:Prime numbers - a faster way

"Lars" <XXXX@XXXXX.COM>writes
##### Quote

And the IsPrimeHR_IA32_2 is almost 100 times faster than SZIsPrime !

IsPrimeHR_IA32_2 129 124 138 391
IsPrimeJOH_IA32_6 189 213 222 624
That reminds me, I must look into the montgomery reduction Hagen uses in
IsPrimeHR_IA32_2. It seems to make a massive difference on some processors
(Athlon/Pentium M).
On my P4 IsPrimeJOH_IA32_6 is faster than IsPrimeHR_IA32_2
regards,
John.

## Re:Prime numbers - a faster way

Lars writes:
##### Quote
I have not look in the prime code.

Ok i just testet you function.

And the IsPrimeHR_IA32_2 is almost 100 times faster than SZIsPrime !

IsPrimeHR_IA32_2 129 124 138 391
IsPrimeHR_IA32_1 191 210 219 620
IsPrimeJOH_IA32_6 189 213 222 624
IsPrimeJOH_IA32_4 255 260 271 786
IsPrimeDKCSSE_1 325 318 340 983
IsPrimeDKCIA32_9 330 321 344 995
IsPrimeDKCSSE_2 331 324 347 1002
IsPrimeDKCPas22 796 737 802 2335
IsPrimeJOHPas6 1020 1912 2403 5335
SZIsPrime 2580 14213 19530 36323
With all respect, your testing program do not show realistic algorithm
performance. I have lot of trouble with RDTSC on small testing
interval, expecially with large data manipulation befor and after test
starting what ever measure I to preserve process on higest priority -
is simply can not be done. That why i perfom at least 50 repeatitevly
testing cycles to get the most accurate possible value with simple
RDTSC command since any process preparation have no effect (see my
SZCodeBaseX and SZTimer unit). Before test, I close all backround
application as is AVP, etc.
About algorithm pefromance. Accordin to elemantary math prove, all
primes are in form n*6-1 or n*6+1, where n in natural number, except
for 2 and 3. According to that, instead of any second odd number check,
we have 2 times less attempts, which mean 2 time less time get result.
Of course, pascal realization of this algorithm can not compare with pure
ASM, but with all other pascal realisation.
About testing. I did performe real performance testing, searching
primes from 1 to 1.000.000, with setep 1 on 1.3MHz Celeron with
optimization On and OFF. Except the real speed performance, this way of
testing also prove correctness of all tested algorithm.
About used algorithm. The fastest John's IA32_6 ASM realization is a
reper. Dennis fastest Pass22 as well as John's Pas2 and pas6. My own
Pas1 is a raw algorithm you tested. As well as my Pas2 variatioiin with
equal number of predefined primes as in John's Pas6.
Results:
Prime number algorithm Time Up to Total
----------------------------------------------------------------
John O'Harrow IA32_6 00:00:02.373 10000000 664579
Dennis Christensen Pas22 00:00:27.920 10000000 664579
John O'Harrow Pas2 00:00:27.960 10000000 664579
Sasa Zeman Pas1 00:00:17.254 10000000 664579
John O'Harrow Pas6 00:00:24.143 10000000 664579
Sasa Zeman Pas2 00:00:15.592 10000000 664579
----------------------------------------------------------------
Column explanation:
Time : In milisecond resolution
Up to: Dearching for primes from 1 to 1.000.000 by 1 step
Total: Total number of primes from up to given number
I did post testing program to attachment group.
Apologies to John, since I wrote his last name incorrectly in previous
message.
Sasa
--
www.szutils.net

## Re:Prime numbers - a faster way

"Sasa Zeman" <XXXX@XXXXX.COM>writes
##### Quote
About testing. I did performe real performance testing, searching
primes from 1 to 1.000.000, with setep 1 on 1.3MHz Celeron with
optimization On and OFF. Except the real speed performance, this way of
testing also prove correctness of all tested algorithm.
Only testing for primes in the range 1 to 1,000,000 would expain the
difference (this is only 0.05% of the cardinal range). Over this very low
range, your loop will of course execute a very small number of times.
If you test is over the entire cardinal range.or usie a large number of
Random(MaxCardinal) values, I think you will get a completely different
result.
regards,
John

## Re:Prime numbers - a faster way

"Sasa Zeman" <XXXX@XXXXX.COM>writes
##### Quote

Apologies to John, since I wrote his last name incorrectly in previous
message.
No problem. It happens all the time.
Result of running your program on my 3.06GHz P4:-
Prime number algorithm Time Up to Total
----------------------------------------------------------------
John O'Harrow IA32_6 00:00:01.657 10000000 664579
Dennis Christensen Pas22 00:00:10.061 10000000 664579
John O'Harrow Pas2 00:00:10.250 10000000 664579
Sasa Zeman Pas1 00:00:07.139 10000000 664579
John O'Harrow Pas6 00:00:10.843 10000000 664579
Sasa Zeman Pas2 00:00:06.453 10000000 664579
----------------------------------------------------------------
However, if instead of testing the range 0 to 1,000,000 I instead test the
range 1,000,000,000 to 1,001,000,000 (still 1,000,001 values), the results
are now completely different:-
Prime number algorithm Time Up to Total
----------------------------------------------------------------
John O'Harrow IA32_6 00:00:02.313 1010000000 482449
Dennis Christensen Pas22 00:00:10.265 1010000000 482449
John O'Harrow Pas2 00:01:43.234 1010000000 482449
Sasa Zeman Pas1 00:01:09.733 1010000000 482449
John O'Harrow Pas6 00:00:24.155 1010000000 482449
Sasa Zeman Pas2 00:01:09.546 1010000000 482449
----------------------------------------------------------------
regards,
John.

## Re:Prime numbers - a faster way

Two mistake.
1. Not 1 mil, but 10 cheking.
2. Error during refreshing data to a zip file - new routines are
created in separated unit, but not deleted in the main unit .
Attached new project.
Prime number algorithm Time Up to Total
----------------------------------------------------------------
John O'Harrow IA32_1 00:00:04.586 10000000 664579
John O'Harrow IA32_2 00:00:04.475 10000000 664579
John O'Harrow IA32_4 00:00:03.185 10000000 664579
John O'Harrow IA32_6 00:00:02.362 10000000 664579
Dennis Christensen Pas22 00:00:28.221 10000000 664579
John O'Harrow Pas2 00:00:28.541 10000000 664579
Sasa Zeman Pas1 00:00:17.385 10000000 664579
John O'Harrow Pas6 00:00:24.274 10000000 664579
Sasa Zeman Pas2 00:00:11.666 10000000 664579
----------------------------------------------------------------
Pas2 need more optimization, but it is twice faster than other pascal
versions for seeking large primes.
Sasa
--
www.szutils.net

## Re:Prime numbers - a faster way

John O'Harrow writes:
##### Quote
If you test is over the entire cardinal range.or usie a large number
of Random(MaxCardinal) values, I think you will get a completely
different result.
I see, moduo operation with a large numbers is a problem.
Sasa
--
www.szutils.net

## Re:Prime numbers - a faster way

Sasa Zeman writes:
##### Quote
John O'Harrow writes:

>If you test is over the entire cardinal range.or usie a large number
>of Random(MaxCardinal) values, I think you will get a completely
>different result.

I see, moduo operation with a large numbers is a problem.
According to www.utm.edu/research/primes/prove/prove2_3.html, at
this point SPP theory is proven up to 341,550,071,728,321 (aroud 2^48)
which easily cover cardinal range.
Your algorithm (Pas6, as well as Dennis pas2) can be speed-up in range
where SPP isn't fast enough and using alternatively this standard
algorithm.
For unsigned 64 integer (if ever Borland support native 64-bits CPU
arithmetic), for unproved numbers by SPP, this algorithm is logical
choice instead incremental odd numbers by 2.
Sasa
--
www.szutils.net

## Re:Prime numbers - a faster way

Hi Sasa Zeman
You are welcome to make a function for the challenge.
Regards
Dennis