Board index » delphi » 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
 

"Lars" <XXXX@XXXXX.COM>writes
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.
 

Lars writes:
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
 

"Sasa Zeman" <XXXX@XXXXX.COM>writes
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
 

"Sasa Zeman" <XXXX@XXXXX.COM>writes
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.
 

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
 

John O'Harrow writes:
Sasa
--
www.szutils.net
 

Sasa Zeman writes:
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
 

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