Humble numbers: Difference between revisions

Content added Content deleted
m (→‎{{header|Pascal}}: improvement check up to 1000 digits)
m (→‎{{header|Pascal}}: checked values with different float types)
Line 748: Line 748:
=={{header|Pascal}}==
=={{header|Pascal}}==
modification of hamming-numbers http://rosettacode.org/wiki/Hamming_numbers#a_fast_alternative
modification of hamming-numbers http://rosettacode.org/wiki/Hamming_numbers#a_fast_alternative
<BR>Using not extended, but check for the first ocurence of 2^i/5^i -> 10^i <BR>
>BR>Check for the first ocurence of 2^i/5^i -> 10^i <BR>
<BR>Using float80/extended and float64/double and single/float32 version, to get a possibility to check values.
Up to 1000 digits needs 9.6 GB = 10.3e9 Byte<BR>
runtime double digits => ~ runtime 2^4 , thats bad<BR>
Up to 877 digits I was able to compare, than float80 run out of memory (13.5 Gb )<BR>
float80 and float64 got same values up to 877.float64 is 2,3x faster than float80<BR>
float32 get wrong at 37 digits,->37 104925 instead of 104926<BR>
⚫
<lang pascal>program hammNumb;
runtime: 2 x digits => ~ runtime 2^4 <BR>
⚫
<lang pascal>
{$IFDEF FPC}
{$IFDEF FPC}
{$MODE DELPHI}
{$MODE DELPHI}
{$OPTIMIZATION ON,ALL}
{$OPTIMIZATION ON,ALL}
{$CODEALIGN proc=16}
{$CODEALIGN proc=32,loop=1}
{$ALIGN 16}
{$ALIGN 16}
{$ELSE}
{$ELSE}
Line 765: Line 767:
const
const
//PlInit(4); <= maxPrimFakCnt+1
//PlInit(4); <= maxPrimFakCnt+1
maxPrimFakCnt = 3;//if tNumber= double 3,7,11
maxPrimFakCnt = 3;//3,7,11 to keep data 8-Byte aligned
//if tNumber= extended 2,6,10 to keep data aligned
minElemCnt = 10;
minElemCnt = 10;
type
type
tPrimList = array of NativeUint;
tPrimList = array of NativeUint;
tnumber = double;
tnumber = extended;
tpNumber= ^tnumber;
tpNumber= ^tnumber;
tElem = record
tElem = record
n : tnumber;//ln(prime[0]^Pots[0]*...
n : tnumber;//ln(prime[0]^Pots[0]*...
// dummy: array[0..5] of byte;//extend extended to 16 byte
dummy: array[0..5] of byte;//extend extended to 16 byte
Pots: array[0..maxPrimFakCnt] of word;
Pots: array[0..maxPrimFakCnt] of word;
end;
end;
Line 892: Line 893:
end;
end;


function LoEGetActElem(pFr:tpFaktorRec):tElem;
function LoEGetActElem(pFr:tpFaktorRec):tElem;inline;
Begin
Begin
with pFr^ do
with pFr^ do
Line 898: Line 899:
end;
end;


function LoEGetActLstNumber(pFr:tpFaktorRec):tpNumber;
function LoEGetActLstNumber(pFr:tpFaktorRec):tpNumber;inline;
Begin
Begin
with pFr^ do
with pFr^ do
Line 938: Line 939:
Begin
Begin
frInsElems[cnt] := LoEGetNextElement(frNextFr);
frInsElems[cnt] := LoEGetNextElement(frNextFr);
// writeln( 'Ins ',frInsElems[cnt].n:10:8,' < ',pNum^:10:8);

inc(cnt);
inc(cnt);
IF cnt > High(frInsElems) then
IF cnt > High(frInsElems) then
Line 963: Line 962:
frMaxIdx:= u;
frMaxIdx:= u;
repeat
repeat
// writeln(i:10,cnt:10,u:10); writeln( pElems^[i].n:10:8,' < ',frInsElems[cnt].n:10:8);
IF pElems^[i].n < frInsElems[cnt].n then
IF pElems^[i].n < frInsElems[cnt].n then
Begin
Begin
Line 1,012: Line 1,010:
var
var
pElems : tpElemArr;
pElems : tpElemArr;
j : NativeUint;
j,PotNum : NativeInt;
lnPrime : tnumber;
begin
begin
with pFR^ do
with pFR^ do
Begin
Begin
//increase Elements by factor
//increase all Elements by factor
pElems := @frElems[0];
pElems := @frElems[0];
LnPrime := frLnPrime;
PotNum := frPotNo;
for j := frMaxIdx Downto 0 do
for j := frMaxIdx Downto 0 do
with pElems^[j] do
with pElems^[j] do
Begin
Begin
n := n+frLnPrime;
n := LnPrime+n;
inc(Pots[frPotNo]);
inc(Pots[PotNum]);
end;
end;
//x^j -> x^(j+1)
//x^j -> x^(j+1)
Line 1,028: Line 1,029:
with frActNumb do
with frActNumb do
begin
begin
n:= j*frLnPrime;
n:= j*LnPrime;
Pots[frPotNo]:= j;
Pots[PotNum]:= j;
end;
end;
frActPot := j;
frActPot := j;
Line 1,099: Line 1,100:
procedure GetDigitCounts(MaxDigit:Uint32);
procedure GetDigitCounts(MaxDigit:Uint32);
var
var
⚫
FA: tArrFR;
pElem : tpElem;
T1,T0 : TDateTime;
T1,T0 : TDateTime;
⚫
FA: tArrFR;
i,j,LastCnt : NativeUint;
i,j,LastCnt : NativeUint;
Begin
Begin
Line 1,114: Line 1,114:
repeat
repeat
inc(j);
inc(j);
pElem := LoEGetNextElementPointer(@FA[0]);
with LoEGetNextElementPointer(@FA[0])^ do
with pElem^ do
IF (Pots[2]= i) AND (Pots[0]= i) then
IF (Pots[2]= i) AND (Pots[0]= i) then
break;
break;
until false;
until false;
writeln(i:4,j-LastCnt:11,j:15,(now-T0)*86.6e3:10:3,' s');
writeln(i:4,j-LastCnt:12,j:15,(now-T0)*86.6e3:10:3,' s');
LastCnt := j;
LastCnt := j;
inc(i);
inc(i);
Line 1,136: Line 1,135:
End.</lang>
End.</lang>
{{out}}
{{out}}
<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120
<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120
Digits count total count
Digits count total count
1 9 9 0.000 s
1 9 9 0.000 s
2 36 45 0.000 s
2 36 45 0.000 s
3 95 140 0.000 s
3 95 140 0.000 s
4 197 337 0.000 s
4 197 337 0.000 s
5 356 693 0.000 s
5 356 693 0.001 s
6 579 1272 0.000 s
6 579 1272 0.001 s
7 882 2154 0.000 s
7 882 2154 0.001 s
8 1272 3426 0.000 s
8 1272 3426 0.001 s
9 1767 5193 0.000 s
9 1767 5193 0.001 s
10 2381 7574 0.000 s
10 2381 7574 0.001 s
11 3113 10687 0.000 s
11 3113 10687 0.001 s
12 3984 14671 0.000 s
12 3984 14671 0.001 s
13 5002 19673 0.000 s
13 5002 19673 0.001 s
14 6187 25860 0.000 s
14 6187 25860 0.002 s
15 7545 33405 0.000 s
15 7545 33405 0.002 s
16 9081 42486 0.000 s
16 9081 42486 0.003 s
17 10815 53301 0.000 s
17 10815 53301 0.003 s
18 12759 66060 0.001 s
18 12759 66060 0.004 s
19 14927 80987 0.001 s
19 14927 80987 0.004 s
20 17323 98310 0.001 s
20 17323 98310 0.005 s
21 19960 118270 0.001 s
21 19960 118270 0.006 s
22 22853 141123 0.001 s
22 22853 141123 0.007 s
23 26015 167138 0.002 s
23 26015 167138 0.008 s
24 29458 196596 0.002 s
24 29458 196596 0.009 s
25 33188 229784 0.002 s
25 33188 229784 0.009 s
26 37222 267006 0.002 s
26 37222 267006 0.010 s
27 41568 308574 0.003 s
27 41568 308574 0.011 s
28 46245 354819 0.003 s
28 46245 354819 0.011 s
29 51254 406073 0.004 s
29 51254 406073 0.012 s
30 56618 462691 0.004 s
30 56618 462691 0.013 s
31 62338 525029 0.005 s
31 62338 525029 0.014 s
32 68437 593466 0.006 s
32 68437 593466 0.015 s
33 74917 668383 0.006 s
33 74917 668383 0.016 s
34 81793 750176 0.006 s
34 81793 750176 0.018 s
35 89083 839259 0.007 s
35 89083 839259 0.019 s
36 96786 936045 0.007 s
36 96786 936045 0.021 s
37 104926 1040971 0.008 s
37 104926 1040971 0.022 s
38 113511 1154482 0.009 s
38 113511 1154482 0.025 s
39 122546 1277028 0.009 s
39 122546 1277028 0.027 s
40 132054 1409082 0.010 s
40 132054 1409082 0.028 s
41 142038 1551120 0.010 s
41 142038 1551120 0.031 s
42 152515 1703635 0.011 s
42 152515 1703635 0.033 s
43 163497 1867132 0.012 s
43 163497 1867132 0.036 s
44 174986 2042118 0.013 s
44 174986 2042118 0.039 s
45 187004 2229122 0.014 s
45 187004 2229122 0.042 s
46 199565 2428687 0.015 s
46 199565 2428687 0.045 s
47 212675 2641362 0.016 s
47 212675 2641362 0.050 s
48 226346 2867708 0.017 s
48 226346 2867708 0.053 s
49 240590 3108298 0.018 s
49 240590 3108298 0.056 s
50 255415 3363713 0.019 s
50 255415 3363713 0.061 s
51 270843 3634556 0.021 s
51 270843 3634556 0.065 s
52 286880 3921436 0.022 s
52 286880 3921436 0.070 s
53 303533 4224969 0.024 s
53 303533 4224969 0.076 s
54 320821 4545790 0.026 s
54 320821 4545790 0.081 s
55 338750 4884540 0.027 s
55 338750 4884540 0.087 s
56 357343 5241883 0.030 s
56 357343 5241883 0.094 s
57 376599 5618482 0.031 s
57 376599 5618482 0.100 s
58 396533 6015015 0.033 s
58 396533 6015015 0.106 s
59 417160 6432175 0.035 s
59 417160 6432175 0.113 s
60 438492 6870667 0.037 s
60 438492 6870667 0.122 s
61 460533 7331200 0.040 s
61 460533 7331200 0.130 s
62 483307 7814507 0.043 s
62 483307 7814507 0.137 s
63 506820 8321327 0.045 s
63 506820 8321327 0.148 s
64 531076 8852403 0.048 s
64 531076 8852403 0.156 s
65 556104 9408507 0.050 s
65 556104 9408507 0.165 s
66 581902 9990409 0.054 s
66 581902 9990409 0.177 s
67 608483 10598892 0.057 s
67 608483 10598892 0.186 s
68 635864 11234756 0.060 s
68 635864 11234756 0.197 s
69 664053 11898809 0.064 s
69 664053 11898809 0.210 s
70 693065 12591874 0.068 s
70 693065 12591874 0.222 s
71 722911 13314785 0.073 s
71 722911 13314785 0.235 s
72 753593 14068378 0.077 s
72 753593 14068378 0.250 s
73 785141 14853519 0.081 s
73 785141 14853519 0.262 s
74 817554 15671073 0.085 s
74 817554 15671073 0.275 s
75 850847 16521920 0.091 s
75 850847 16521920 0.292 s
76 885037 17406957 0.096 s
76 885037 17406957 0.305 s
77 920120 18327077 0.102 s
77 920120 18327077 0.320 s
78 956120 19283197 0.108 s
78 956120 19283197 0.338 s
79 993058 20276255 0.113 s
79 993058 20276255 0.354 s
80 1030928 21307183 0.119 s
80 1030928 21307183 0.370 s
81 1069748 22376931 0.127 s
81 1069748 22376931 0.391 s
82 1109528 23486459 0.134 s
82 1109528 23486459 0.409 s
83 1150287 24636746 0.142 s
83 1150287 24636746 0.428 s
84 1192035 25828781 0.150 s
84 1192035 25828781 0.451 s
85 1234774 27063555 0.158 s
85 1234774 27063555 0.470 s
86 1278527 28342082 0.165 s
86 1278527 28342082 0.490 s
87 1323301 29665383 0.175 s
87 1323301 29665383 0.516 s
88 1369106 31034489 0.183 s
88 1369106 31034489 0.538 s
89 1415956 32450445 0.192 s
89 1415956 32450445 0.559 s
90 1463862 33914307 0.201 s
90 1463862 33914307 0.582 s
91 1512840 35427147 0.213 s
91 1512840 35427147 0.612 s
92 1562897 36990044 0.223 s
92 1562897 36990044 0.636 s
93 1614050 38604094 0.233 s
93 1614050 38604094 0.662 s
94 1666302 40270396 0.245 s
94 1666302 40270396 0.694 s
95 1719669 41990065 0.255 s
95 1719669 41990065 0.721 s
96 1774166 43764231 0.265 s
96 1774166 43764231 0.748 s
97 1829805 45594036 0.279 s
97 1829805 45594036 0.785 s
98 1886590 47480626 0.290 s
98 1886590 47480626 0.815 s
99 1944540 49425166 0.301 s
99 1944540 49425166 0.845 s
100 2003661 51428827 0.315 s
100 2003661 51428827 0.884 s
⚫
101 2063972 53492799 0.916 s
Total number of humble numbers found: 51428827
102 2125486 55618285 0.948 s
Running time: 315 ms
103 2188204 57806489 0.991 s
104 2252146 60058635 1.026 s
105 2317319 62375954 1.062 s
106 2383733 64759687 1.110 s
107 2451413 67211100 1.147 s
108 2520360 69731460 1.186 s
109 2590584 72322044 1.237 s
110 2662102 74984146 1.278 s
.. shortened
120 3450981 105831533 1.795 s
130 4382079 145340170 2.450 s
140 5467187 194997130 3.298 s
150 6718091 256407329 4.318 s
170 9764417 421496245 7.055 s
⚫
180 11583420 528974086 8.822 s
190 13615367 655803459 10.972 s
200 15872045 804178604 13.424 s
⚫
300 53391941 4039954757 66.882 s
⚫
400 126350163 12719142480 207.622 s
⚫
500 246533493 30980806733 503.269 s
600 425728730 64142692268 1039.928 s
⚫
700 675722681 118701223590 1920.325 s
⚫
800 1008302151 202331504969 3265.469 s
..
..
876 1323548095 290737888948 4690.230 s
Digits count total count
877 1328082553 292065971501 4709.931 s
1 9 9 0.000 s
</pre>
⚫
100 2003661 51428827 0.319 s
⚫
200 15872045 804178604 5.428 s
⚫
300 53391941 4039954757 27.791 s
⚫
400 126350163 12719142480 87.721 s
⚫
500 246533493 30980806733 214.313 s
⚫
700 675722681 118701223590 821.831 s
⚫
800 1008302151 202331504969 1402.278 s
900 1435253916 323887320467 2244.679 s
1000 1968364785 493401133939 3416.992 s
Total number of humble numbers found: 493401133939
Running time: 3417049 ms</pre>


=={{header|Perl}}==
=={{header|Perl}}==
Retrieved from "https://rosettacode.org/wiki/Humble_numbers"