Distribution of 0 digits in factorial series: Difference between revisions

Content added Content deleted
m (→‎{{header|REXX}}: reworded a comment.)
m (→‎{{header|Pascal}}: delete unused arrays, reorder, more comments)
Line 206: Line 206:
CountOfZero : array[0..999] of byte;
CountOfZero : array[0..999] of byte;
SumOfRatio :array[0..LIMIT] of extended;
SumOfRatio :array[0..LIMIT] of extended;

CoZ_Fac : array[0..LIMIT] of Uint32;

CoD_Fac : array[0..LIMIT] of Uint32;
⚫
procedure OutMul(pMul:tpMul;Lmt :NativeInt);
// for testing
⚫
Begin
⚫
write(pMul[lmt]);
⚫
For lmt := lmt-1 downto 0 do
⚫
write(Format('%.9d',[pMul[lmt]]));
⚫
writeln;
⚫
end;


procedure InitCoZ;
procedure InitCoZ;
//Init Lookup table for 3 digits
var
var
i,j : integer;
x,y : integer;
begin
begin
fillchar(CountOfZero,SizeOf(CountOfZero),#0);
fillchar(CountOfZero,SizeOf(CountOfZero),#0);
CountOfZero[0] := 3;
CountOfZero[0] := 3; //000
For i := 1 to 9 do
For x := 1 to 9 do
Begin
Begin
CountOfZero[i] := 2;
CountOfZero[x] := 2; //00x
CountOfZero[10*i] := 2;
CountOfZero[10*x] := 2; //0x0
CountOfZero[100*i] := 2;
CountOfZero[100*x] := 2; //x00
j := 10;
y := 10;
repeat
repeat
CountOfZero[j+i] := 1;
CountOfZero[y+x] := 1; //0yx
CountOfZero[10*j+i] := 1;
CountOfZero[10*y+x] := 1; //y0x
CountOfZero[10*(j+i)] := 1;
CountOfZero[10*(y+x)] := 1; //yx0
inc(j,10)
inc(y,10)
until j > 100;
until y > 100;
end;
end;
end;
end;
Line 243: Line 252:
end;
end;


procedure OutMul(pMul:tpMul;Lmt :NativeInt);
function CntZero(pMul:tpMul;Lmt :NativeInt):NativeUint;
//count zeros in Base 1,000,000,000 number
//for checking purposes
⚫
Begin
⚫
write(pMul[lmt]);
⚫
For lmt := lmt-1 downto 0 do
⚫
write(Format('%.9d',[pMul[lmt]]));
⚫
writeln;
⚫
end;

⚫
function CheckForZero(pMul:tpMul;Lmt :NativeInt):NativeUint;
// Numbers in base 1,000,000,000 divide in 3 sections
var
var
s : string[15];
q,r : LongWord;
q,r : LongWord;
i : NativeInt;
i : NativeInt;
begin
begin
result := 0;
result := 0;
For i := 0 to Lmt-1 do
For i := Lmt-1 downto 0 do
Begin
Begin
q := pMul[i];
q := pMul[i];
r := q DIV 1000;
r := q DIV 1000;
result +=CountOfZero[q-1000*r];
result +=CountOfZero[q-1000*r];//q-1000*r == q mod 1000
q := r;
q := r;
r := q DIV 1000;
r := q DIV 1000;
Line 272: Line 271:
result +=CountOfZero[q-1000*r];
result +=CountOfZero[q-1000*r];
end;
end;
//special case first digits no leading '0'
q := pMul[lmt];
q := pMul[lmt];
while q >= 1000 do
while q >= 1000 do
Line 279: Line 279:
q := r;
q := r;
end;
end;
if q > 0 then
while q > 0 do
Begin
begin
str(q,s);
r := q DIV 10;
For i := Length(s) downto 1 do
result += Ord( q-10*r= 0);
IF s[i] ='0' then
q := r;
⚫
inc(result);
end;
end;
end;
end;


function GetCoD(pMul:tpMul;Lmt :NativeInt):NativeUint;
function GetCoD(pMul:tpMul;Lmt :NativeInt):NativeUint;
//count of decimal digits
//calculate used digits
var
var
i : longWord;
i : longWord;
Line 305: Line 304:
inc(result);
inc(result);
end;
end;
⚫
end;

procedure DoChecks(pMul:tpMul;Lmt,i :NativeInt);
//(extended(1.0)* makes TIO.RUN faster // only using FPU?
⚫
Begin
⚫
SumOfRatio[i] := SumOfRatio[i-1] + (extended(1.0)*CntZero(pMul,Lmt))/GetCoD(pMul,Lmt);
end;

function MulByI(pMul:tpMul;UL,i :NativeInt):NativeInt;
var
prod : Uint64;
j : nativeInt;
carry : LongWord;
begin
result := UL;
⚫
carry := 0;
For j := 0 to result do
⚫
Begin
⚫
prod := i*pMul[0]+Carry;
⚫
Carry := prod Div LongWordDec;
⚫
pMul[0] := Prod - LongWordDec*Carry;
⚫
inc(pMul);
end;

⚫
IF Carry <> 0 then
Begin
⚫
inc(result);
⚫
pMul[0]:= Carry;
⚫
End;
end;
end;


Line 311: Line 339:
MulArr : tMul;
MulArr : tMul;
pMul : tpMul;
pMul : tpMul;
prod,carry : Uint64;
i,ul : NativeInt;
i,j,ul : NativeInt;
begin
begin
i := getFactorialDecDigits(n) DIV 9 +10;
i := getFactorialDecDigits(n) DIV 9 +10;
Line 321: Line 348:
i := 1;
i := 1;
repeat
repeat
carry := 0;
UL := MulByI(pMul,UL,i);
For j := 0 to UL do
//Now do what you like to do with i!
DoChecks(pMul,UL,i);
⚫
Begin
⚫
prod := i*pMul[j]+Carry;
⚫
Carry := prod Div LongWordDec;
⚫
pMul[j] := Prod - Carry*LongWordDec;
⚫
end;

⚫
IF Carry <> 0 then
⚫
Begin
⚫
inc(Ul);
⚫
pMul[UL]:= Carry;
⚫
End;

CoD_Fac[i] := GetCoD(pMul,UL);
CoZ_Fac[i] := CheckForZero(pMul,UL);
⚫
SumOfRatio[i] := SumOfRatio[i-1] + CoZ_Fac[i]/CoD_Fac[i];
inc(i);
inc(i);
until i> n;
until i> n;
Line 348: Line 361:
writeln(i:8,SumOfRatio[i]/i:18:15);
writeln(i:8,SumOfRatio[i]/i:18:15);
end;
end;

var
var
i : integer;
i : integer;
Line 353: Line 367:
InitCoZ;
InitCoZ;
SumOfRatio[0]:= 0;
SumOfRatio[0]:= 0;
⚫
CoD_Fac[0]:= 0;
CoZ_Fac[0]:= 0;
getFactorialExact(LIMIT);
getFactorialExact(LIMIT);
Out_(100);
Out_(100);
Line 371: Line 383:
end.</lang>
end.</lang>
{{out}}
{{out}}
⚫
<pre> 100 0.246753186167432
<pre>TIO.RUN
⚫
100 0.246753186167432
1000 0.203544551103165
1000 0.203544551103165
10000 0.173003848241866
10000 0.173003848241866
50000 0.159620054602269
50000 0.159620054602269
First ratio < 0.16 47332 0.15999999579985665
First ratio < 0.16 47332 0.15999999579985665
Real time: 5.521 s CPU share: 98.03 % // 2.67s on 2200G freepascal 3.2.2</pre>
Real time: 4.898 s CPU share: 99.55 % // 2.67s on 2200G freepascal 3.2.2</pre>


=={{header|Python}}==
=={{header|Python}}==
Retrieved from "https://rosettacode.org/wiki/Distribution_of_0_digits_in_factorial_series"