Anonymous user
Mian-Chowla sequence: Difference between revisions
m
→{{header|Pascal}}: finished 25000
m (→{{header|Pascal}}: small improvement, known where to insert.Show runtime behavier of this implementation) |
m (→{{header|Pascal}}: finished 25000) |
||
Line 804:
keep sum of all sorted.Memorizing the compare positions speeds up.
<BR>
<pre>const▼
▲<pre>
maxCnt = 25000;
Using
tElem = Uint64;
t_n_sum_all = array of tElem; //dynamic array
n mian-chowla[n]
250 317739 1270 429 ms// runtime setlength of 2.35 GB ~ 400ms
500 2085045 7055 589 ms
750 6265086 16632 1053 ms
..
1500 43205712 67697 6669 ms
..
3000 303314913 264489 65040 ms //2xn -> runtime x9,75
..
6000 2189067236 1019161 719208 ms //2xn -> runtime x11,0
6250 2451223363 1047116 825486 ms
..
12000 15799915996 3589137 8180177 ms //2xn -> runtime x11,3
12250 16737557137 3742360 8783711 ms
12500 17758426186 4051041 9455371 ms
..
24000 115709049568 13738671 99959526 ms //2xn -> runtime x12
24250 119117015697 13492623 103691559 ms
24500 122795614247 14644721 107758962 ms
24750 126491059919 14708578 111875949 ms
25000 130098289096 14414457 115954691 ms //dt = 4078s ->16s/per number
real 1932m34,698s => 1d8h12m35</pre>
<lang pascal>program MianChowla;
//compiling with /usr/lib/fpc/3.2.0/ppcx64.2 -MDelphi -O4 -al "%f"
Line 824 ⟶ 841:
deltaK = 100;
maxCnt = 1000;
▲ deltaK = 540;
type
tElem = Uint32;
Line 859 ⟶ 872:
procedure InsertNew_sum(NewValue:NativeUint);
//insertion already knowning the positions
var
pElem :tpElem;
Line 974 ⟶ 987:
writeln;
END.
</lang>
{{Out}}
|