Ormiston pairs: Difference between revisions

Content added Content deleted
m (uups sort entries)
(→‎{{header|Free Pascal}}: checking mod 18 =0 is faster.)
Line 412: Line 412:
=={{header|Pascal}}==
=={{header|Pascal}}==
==={{header|Free Pascal}}===
==={{header|Free Pascal}}===
update the digits by adding difference.
//update the digits by adding difference.// Using MOD 18 = 0 and convert is faster.
<syntaxhighlight lang=pascal>
<syntaxhighlight lang=pascal>
program Ormiston;
program Ormiston;
Line 533: Line 533:


type
type
td10_UsedDgts = array[0..11] of byte;
tDigits10 = array[0..15] of byte;
td10_UsedDgts2 = array[0..2] of Uint32;
td10_UsedDgts2 = array[0..3] of Uint32;
tpd10_UsedDgts2 = ^td10_UsedDgts2;
tpd10_UsedDgts2 = ^td10_UsedDgts2;
//size of 32 byte. two XMMx - 16 byte copies p1:=p2
tDigits10 = record
d10_UsedDgts :td10_UsedDgts;
d10_dgts :array[0..15] of byte;
d10_maxIdx : Uint32;
⚫
end;

procedure Out_Digits10(const p0:tDigits10);
var
var
p_zero : tDigits10;// faster than fillchar
i : Int32;
⚫
begin
with p0 do
begin
i := d10_maxIdx;
while i >= 0 do
begin
write(d10_dgts[i]);
⚫
dec(i);
end;
write(' ');
For i := 0 to 9 do
write(d10_UsedDgts[i]);
writeln;
end;
end;


procedure OutIn(cnt,p1,p2:NativeInt);
procedure OutIn(cnt,p1,p2:NativeInt);
Line 575: Line 552:
end;
end;


function Convert2Digits10(p:Uint32):tDigits10;
procedure Convert2Digits10(p:NativeUint;var outP:tDigits10);
var
var
i,r,m10: Uint32;
r : NativeUint;
begin
begin
⚫
outP := p_zero;
fillchar(result,SizeOf(result),#0);
with result do
begin
begin
⚫
i := 0;
repeat
repeat
r := p DIV 10;
r := p DIV 10;
m10 := p-10*r;
inc(outP[p-10*r]);
d10_dgts[i] := m10;
inc(d10_UsedDgts[m10]);
inc(i);
p := r;
p := r;
until r = 0;
until r = 0;
Line 594: Line 566:
end;
end;


⚫
function CheckOrmiston(const d1,d2:tpd10_UsedDgts2):boolean;inline;
procedure Add2Digits10(delta:Uint32;var p0,p1:tDigits10);
// checking four digits at once.Ord to circumvent conditional jumps
var
i,r,m10,dgt: Uint32;
begin
p1 := p0;
with p1 do
begin
i := 0;
repeat
m10 := d10_dgts[i];
//remove old digit
dec(d10_UsedDgts[m10]);
r := delta DIV 10;
dgt := m10 + delta -10*r;
⚫
if dgt >= 10 then
begin
dgt -= 10;
r += 1;
end;
d10_dgts[i] := dgt;
//insert new digit
inc(d10_UsedDgts[dgt]);
delta := r;
inc(i);
until (i> d10_maxIdx) OR (delta = 0);
if (i> d10_maxIdx) AND (delta>0) then
begin
d10_maxIdx += 1;
r := delta DIV 10;
dgt := delta -10*r;
d10_dgts[i] := dgt;
inc(d10_UsedDgts[dgt]);
end;
end;
end;

⚫
function CheckOrmiston(d1,d2:tpd10_UsedDgts2):boolean;inline;
//check 4 byte at once, not byte by byte
begin
begin
result := (d1^[0]=d2^[0]) AND (d1^[1]=d2^[1]) AND (d1^[2]=d2^[2]);
exit((ORD(d1^[0]=d2^[0]) + ORD(d1^[1]=d2^[1]) + ORD(d1^[2]=d2^[2])) =3);
// result := (d1^[0]=d2^[0]) AND (d1^[1]=d2^[1]) AND (d1^[2]=d2^[2]);
end;
end;


Line 639: Line 576:
pSieve : tpPrimes;
pSieve : tpPrimes;
T1,T0: TDateTime;
T1,T0: TDateTime;
{$align 16}
p1,p2 :tDigits10;
p1,p2 :tDigits10;
pr,pr_before,
pr,pr_before,
Line 650: Line 588:
pSieve := @PrimeSieve[0];
pSieve := @PrimeSieve[0];
pr_before := 2;
pr_before := 2;
p1 := Convert2Digits10(pr_before);
Convert2Digits10(pr_before,p1);
pr := pr_before;
pr := pr_before;
prLimit := 100*1000;
prLimit := 100*1000;
Line 660: Line 598:
if pr > limit then
if pr > limit then
BREAK;
BREAK;
Add2Digits10(pr-pr_before,p1,p2);
if (pr-pr_before) mod 18 = 0 then
if CheckOrmiston(@p1.d10_UsedDgts,@p2.d10_UsedDgts) then
begin
begin
inc(cnt);
Convert2Digits10(pr,p1);
Convert2Digits10(pr_before,p2);
IF cnt <= 30 then
OutIn(cnt,pr_before,pr);
if CheckOrmiston(@p1,@p2) then
⚫
begin
⚫
inc(cnt);
⚫
IF cnt <= 30 then
OutIn(cnt,pr_before,pr);
⚫
end;
end;
end;
p1 := p2;
p1 := p2;
Line 688: Line 630:
34,901 Ormiston pairs before 100,000,000
34,901 Ormiston pairs before 100,000,000


Real time: 0.824 s User time: 0.717 s Sys. time: 0.100 s CPU share: 99.08 %
Real time: 0.648 s User time: 0.557 s Sys. time: 0.085 s CPU share: 99.05 %

@home 1E10
@home 1E10
// Limit= 10*1000*1000*1000;
time for sieving 00:17.926
time for sieving 00:17.708
...
....
34,901 Ormiston pairs before 100,000,000
34,901 Ormiston pairs before 100,000,000
326,926 Ormiston pairs before 1,000,000,000
326,926 Ormiston pairs before 1,000,000,000
3,037,903 Ormiston pairs before 10,000,000,000
3,037,903 Ormiston pairs before 10,000,000,000


real 0m30,479s user 0m28,191s sys 0m2,279s
real 0m25,887s user 0m23,680s sys 0m2,199s
</pre>
</pre>

=={{header|Phix}}==
=={{header|Phix}}==
{{trans|Wren}}
{{trans|Wren}}
Retrieved from "https://rosettacode.org/wiki/Ormiston_pairs"