Jump to content

Multi-base primes: Difference between revisions

Multi-base primes (view source)

Revision as of 14:24, 8 July 2021

1,207 bytes added ,  2 years ago
m
→‎{{header|Pascal}}: using inc in base to speed up converting, CnvtoBase base was the true reason.
m (→‎Up to base 62: make sub item)
m (→‎{{header|Pascal}}: using inc in base to speed up converting, CnvtoBase base was the true reason.)
Line 634:
First counting the bases that convert a MAXBASE string of n into a prime number.<BR>
Afterwards only checking the maxcount for the used bases.<BR>
Most time consuming is sieving for the primes.
<lang pascal>program MAXBaseStringIsPrimeInBase;
{$IFDEF FPC}
Line 646 ⟶ 645:
sysutils;
const
CharOfBase= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
MINBASE = 2;
MAXBASE = 3662;//62;//36
MAXDIGITCOUNT = 65;//56;
type
tdigits = array [0..15] of byte;//must be 0..15record
dgtDgts : array [0..13] of byte;
dgtMaxIdx,
dgtMaxDgtVal :byte;
dgtNum : Uint64;
end;
tSol = array of Uint64;
var
BoolPrimes: array of boolean;
 
//memorize the highest used digit
function Out_String(n:Uint64;var s: AnsiString):Uint32;forward;
MaxDgtPos : UInt32;
 
procedure Out_Digits(const dgts:tDigits);
var
s : ANsistring;
i : Int32;
begin
s := '';
with dgts do
Begin
i := dgtMaxIdx;
while i >= 0 do
begin
s := s+CharOfBase[dgtDgts[i]];
dec(i);
end;
end;
write(#13,s);
end;
 
function BuildWheel(primeLimit:Int64):NativeUint;
var
Line 742 ⟶ 766:
end;
 
functionprocedure getDgtsInMAXBASEandMaxDigitCnvtoMAXBASE(n:Uint64;var dgt:tDigits):uint32;
var
pQ :pQWord;
q,r: Uint64;
i :Int64 Int32;
Begin
pQ := @dgt[0];
pQ[0] := 0;pQ[1] := 0;
//aka fillChar(dgt[0],SizeOf(dgt),#0);
 
i := 0;
resultwith :=dgt 0;do
repeatBegin
q dgtNum:= n DIV MAXBASE;
repeat
r := (n-q*MAXBASE);
dgt[i] r := rn;
if result <q r:= thenn div result := rMAXBASE;
inc(i) r -= q*MAXBASE;
n := q;
until n dgtDgts[i] := 0r;
MaxDgtPos := inc(i-1);
until (q = 0);
dec(i);
dgtMaxIdx := i;
r := 1;
repeat
q := dgtDgts[i];
if r < q then
r := q;
dec(i);
until i <0 ;
dgtMaxDgtVal := r;
end;
end;
 
function CnvtoBase(const dgt:tDigits;base:NativeUint;DgtCnt:NativeInt):Uint64;
var
tmpDgt,i: NativeInt;
Begin
result := 0;
with dgt do
repeat
Begin
result := base*result+dgt[DgtCnt];
dec(DgtCnt)i:= dgtMaxIdx;
repeat
until (DgtCnt< 0);
//result := base*result + dgtDgts[i];
//this is th reason for speed up.Hide the waiting for reading of dgtDgts[i]
tmpDgt := dgtDgts[i];
result *= base;
dec(i);
result +=tmpDgt;
until (i< 0);
end;
end;
 
procedure IncMAXBASEDigits(var dgt:tDigits);
function CntPrimeInBases(n:Uint64;max:Int32):Uint32;
var
i,q,tmp :NativeInt;
Begin
with dgt do
Begin
tmp := dgtMaxIdx;
i := 0;
repeat
q := dgtDgts[i]+1;
q -= (-ORD(q >=MAXBASE) AND MAXBASE);
dgtDgts[i] := q;
inc(i);
until q <> 0;
dec(i);
if tmp < i then
begin
tmp := i;
dgtMaxIdx := i;
end;
 
i := tmp;
repeat
tmp := dgtDgts[i];
if q< tmp then
q := tmp;
dec(i);
until i <0;
dgtMaxDgtVal := q;
end;
end;
 
function CntPrimeInBases(var Digits :tdigits;max:Int32):Uint32;
var
Digits :tdigits;
pr : Uint64;
base,dgtCnt: Uint32;
begin
result := 0;
Base := getDgtsInMAXBASEandMaxDigitIncMAXBASEDigits(n,Digits)+1;
Base := Digits.dgtMaxDgtVal+1;
IF Digits[0] = 0 then
//divisible by every base
IF Digits.dgtDgts[0] = 0 then
EXIT;
if base < MinBase then
base := MinBase;
// if (MAXBASE - Base) <= (max-result) then BREAK;
max := (max+Base-MAXBASE);
if (max>=0) then
EXIT;
for base := base TO MAXBASE do
dgtCnt := MAXDIGITCOUNT-1;
while (dgtCnt>0) AND (Digits[dgtCnt]= 0) do
dec(dgtCnt);
result := Ord(boolprimes[n]);
for base := base TO MAXBASE-1 do
begin
pr := CnvtoBase(Digits,base,MaxDgtPos);
inc(result,Ord(boolprimes[pr]));
//no chance to reach max then exit
if result<=max then
break;
inc(max);
end;
end;
 
function GetMaxBaseCnt(var dgt:tDigits;MinLmt,MaxLmt:Uint32):tSol;
var
i : Uint32;
Line 815 ⟶ 884:
For i := MinLmt to MaxLmt do
Begin
baseCnt := CntPrimeInBases(idgt,max);
if baseCnt = 0 then
continue;
Line 840 ⟶ 909:
function Out_String(n:Uint64;var s: AnsiString):Uint32;
//out-sourced for debugging purpose
const
CharOfBase= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
var
dgt:tDigits;
Line 848 ⟶ 915:
Begin
result := 0;
base:= getDgtsInMAXBASEandMaxDigitCnvtoMAXBASE(n,dgt)+1;
sl := '';
with dgt do
i := MaxDgtPos;
begin
while (i>=0)do
base:= dgtMaxDgtVal+1;
Begin
sli +:= CharOfBase[dgt[i]+1]dgtMaxIdx;
decwhile (i>=0);do
Begin
sl += CharOfBase[dgtDgts[i]+1];
dec(i);
end;
s := sl+' -> [';
end;
s := sl+' -> [';
 
For base := base to MAXBASE do
if boolprimes[CnvtoBase(dgt,base,MaxDgtPos)] then
begin
inc(result);
Line 887 ⟶ 957:
 
var
dgt:tDigits;
T0 : Int64;
i : NativeInt;
lmt,minLmt : UInt32;
 
i : Uint32;
begin
T0 := GetTickCount64;
Line 896 ⟶ 968:
for i := 1 to MAXDIGITCOUNT do
lmt :=lmt*MAXBASE+MAXBASE-1;
writeln('max prime limit ',lmt);
Sieve(lmt);
writeln('Prime sieving ',(GetTickCount64-T0)/1000:6:3,' s');
CnvtoMAXBASE(0,dgt);
T0 := GetTickCount64;
i := 1;
Line 904 ⟶ 978:
repeat
write(i:2,' character strings which are prime in count bases = ');
Out_Sol(GetMaxBaseCnt(dgt,minLmt,MAXBASE*minLmt-1));
minLmt *= MAXBASE;
inc(i);
until i>MAXDIGITCOUNT;
writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s');
{$IFDEF WINDOWS} readln; {$ENDIF}
end.</lang>
{{out}}
<pre>
 
//at home 2200G 16GB Linux
TIO.RUN// extreme volatile timings for sieving primes
max prime limit 916132831
Prime sieving 3.788 s
1 character strings which are prime in count bases = 60
2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62]
 
2 character strings which are prime in count bases = 31
65 -> [7,8,9,11,13,14,16,17,18,21,22,24,27,28,29,31,32,37,38,39,41,42,43,44,46,48,51,52,57,58,59]
 
3 character strings which are prime in count bases = 33
1L1 -> [22,23,25,26,27,28,29,30,31,32,33,34,36,38,39,40,41,42,43,44,45,46,48,51,52,53,54,57,58,59,60,61,62]
B9B -> [13,14,15,16,17,19,20,21,23,24,26,27,28,30,31,34,36,39,40,42,45,47,49,50,52,53,54,57,58,59,60,61,62]
 
4 character strings which are prime in count bases = 32
1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36,37,38,39,41,45,46,48,50,51,57,58,60,61]
417B -> [12,13,15,16,17,18,19,21,23,25,28,30,32,34,35,37,38,39,41,45,48,49,50,51,52,54,56,57,58,59,61,62]
 
5 character strings which are prime in count bases = 30
50161 -> [7,8,9,13,17,18,19,20,25,28,29,30,31,33,35,36,38,39,41,42,43,44,47,48,52,55,56,59,60,62]
 
Converting 12.738 s
Real time: 16.768 s User time: 16.128 s Sys. time: 0.488 s CPU share: 99.09 %
//at home AMD 2200G Linux fpc 3.2.2
real 0m8,609s user 0m8,378s sys 0m0,220s
max prime limit 916132831
Prime sieving 1.734 s
Converting 6.842 s
 
//base = 36 maxcharacters = 6
max prime limit 2176782335
Prime sieving 54.003986 s
1 character strings which are prime in count bases = 34
2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36]
Line 938 ⟶ 1,040:
441431 -> [5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33]
 
Converting 2415.313507 s// 24.3s before
real 0m29,389s
######################
TIO.RUN// extreme volatile timings for sieving primes
Maxbase = 62 maxcharacters = 5
max prime limit 916132831
Prime sieving 14.576 s
1 character strings which are prime in count bases = 60
2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62]
 
2 character strings which are prime in count bases = 31
65 -> [7,8,9,11,13,14,16,17,18,21,22,24,27,28,29,31,32,37,38,39,41,42,43,44,46,48,51,52,57,58,59]
 
3 character strings which are prime in count bases = 33
1L1 -> [22,23,25,26,27,28,29,30,31,32,33,34,36,38,39,40,41,42,43,44,45,46,48,51,52,53,54,57,58,59,60,61,62]
B9B -> [13,14,15,16,17,19,20,21,23,24,26,27,28,30,31,34,36,39,40,42,45,47,49,50,52,53,54,57,58,59,60,61,62]
 
4 character strings which are prime in count bases = 32
1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36,37,38,39,41,45,46,48,50,51,57,58,60,61]
417B -> [12,13,15,16,17,18,19,21,23,25,28,30,32,34,35,37,38,39,41,45,48,49,50,51,52,54,56,57,58,59,61,62]
 
5 character strings which are prime in count bases = 30
50161 -> [7,8,9,13,17,18,19,20,25,28,29,30,31,33,35,36,38,39,41,42,43,44,47,48,52,55,56,59,60,62]
 
real 0m20,566s</pre>
Converting 19.044 s
Real time: 33.929 s User time: 24.091 s Sys. time: 9.093 s CPU share: 97.80 %
//at home real 0m12,614s user 0m12,336s sys 0m0,238s
</pre>
 
=={{header|Phix}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/313414"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information