Jump to content

Mian-Chowla sequence: Difference between revisions

Mian-Chowla sequence (view source)

Revision as of 00:48, 26 March 2019

2,041 bytes added ,  5 years ago
m
→‎{{header|Pascal}}: small improvement, known where to insert.Show runtime behavier of this implementation
(Added Kotlin)
m (→‎{{header|Pascal}}: small improvement, known where to insert.Show runtime behavier of this implementation)
Line 803:
{{works with|Free Pascal}}
keep sum of all sorted.Memorizing the compare positions speeds up.
<BR>
10 min for n = 5818 1998652370. The cost of inserting 5818 values into sum_all array takes about 9 seconds.
Calculating runtime to expect.
That is not relevant.
<pre>
n-> 2x n ~>
average distance between d = mian[n]-mian[n-1] d ~ 4x d
runtime t-> >10x t. ->
n mian[n] avg dist runtime
2700 225432491 195419 43411 ms
5400 1613654038 766839 471468 ms
</pre>
So calculating mian[25000] = mian[5940*(2**2,0733)]
runtime minimum > 10.86**2.0733 *471.5s = 66251 s and round about 2.5 Gbyte for Uint64.
One or two days should be enough.
<lang pascal>program MianChowla;
//compiling with /usr/lib/fpc/3.2.0/ppcx64.2 -MDelphi -O4 -al "%f"
{$CODEALIGN proc=8,loop=4 }
uses
sysutils;
const
maxCntdeltaK = 100;
maxCnt = 1000;
{
deltaK = 540;
maxCnt = (5966 DIV deltaK)*deltaK;
*}
type
tElem = Uint32;
tpElem = ^tElempUint32;
t_n = array[0..maxCnt+1] of tElem;
t_n_sum_all = array[0..(maxCnt+1)*(maxCnt+2) DIV 2] of tElem;
 
var
n_LastPos,
n : t_n;
 
n_sum_all : t_n_sum_all;
n,
n_LastPos : t_n; //memorize compare positions :-)
 
maxIdx,
Line 832 ⟶ 853:
max_SumIdx := 1;
n_sum_all[max_SumIdx] := 2*maxN;
 
For i := 1 to maxCnt do
For i := 0 to maxCnt do
n_LastPos[i] := 1;
end;
 
procedure InsertNew_sum(NewValue:NativeUint);
//insertionsort
var
pElem :tpElem;
InsIdx,chkIdx,oldIdx,newIdx,nextValue : nativeInt;
Begin
write(#13,MaxIdx:10,NewValue:10);
newIdx := maxIdx;
oldIdx := max_SumIdx;
Line 849 ⟶ 871:
//extend sum_
inc(max_SumIdx,maxIdx);
 
//heighest value already known
InsIdx := max_SumIdx;
n_sum_all[max_SumIdx] := 2*NewValue;
n_sum_all[InsIdx] := 2*NewValue;
 
//stop mark
pElem := @n_sum_all[max_SumIdx-1];
n_sum_all[InsIdx+1] := High(tElem);
nextValue := NewValue+n[newIdx];
pElem := @n_sum_all[0];
dec(InsIdx);
//n_LastPos[newIdx]+newIdx-1 == InsIdx
repeat
//move old bigger values
while n_sum_all[oldIdx] > nextValue do
chkIdx := n_LastPos[newIdx]+newIdx-1;
while InsIdx > chkIdx do
Begin
pElem^[InsIdx] := n_sum_allpElem[oldIdx];
dec(InsIdx);
dec(oldIdx);
dec(pElem);
end;
pElem^//insert :=new nextValue;value
dec(pElem)[InsIdx] := NewValue+n[newIdx];
dec(InsIdx);
dec(newIdx);
//all inserted
IF newIdx = 0 then
until newIdx <= BREAK0;
//new minimum search position one behind, oldidx is one to small
nextValue := NewValue+n[newIdx];
inc(oldidx,2);
until newIdx < 0;
For newIdx := 1 to maxIdx do
n_LastPos[newIdx] := oldIdx;
end;
 
procedure FindNew;
var
pSumAll,pn : tpElem;
i,LastCheckPos,Ofs,newVal : NativeUint;
i,LastCheckPos,newValue,newSum : NativeUint;
TestRes : boolean;
begin
//start value = last inserted value
ofs := n[maxIdx]+1;
For inewValue := 1 to n[maxIdx+1 do];
pSumAll := n_LastPos@n_sum_all[i0] := 1;
pn := @n[0];
repeat
LastCheckPos//try :=next 1;number
inc(newValue);
LastCheckPos := n_LastPos[1];
i := 1;
For//check iif sum := 1new is toalready maxIdxn doall_sum
Beginrepeat
newValnewSum := ofsnewValue+npn[i];
IF LastCheckPos < n_LastPos[i] then
LastCheckPos := n_LastPos[i];
while n_sum_allpSumAll[LastCheckPos] < newValnewSum do
Begin
inc(LastCheckPos);
if//memorize LastCheckPos >= max_SumIdx then;
n_LastPos[i] := BREAKLastCheckPos;
TestRes:= pSumAll[LastCheckPos] = newSum;
end;
TestRes:= n_sum_all[LastCheckPos] = newVal;
IF TestRes then
BREAK;
//memorize LastCheckPosinc(i);
until i>maxIdx;
n_LastPos[i] := LastCheckPos-1;
end;
//found?
If not(TestRes) then
BREAK;
inc(ofs);
until false;
InsertNew_sum(ofsnewValue);
end;
 
var
i T1,T0: NativeIntInt64;
i,k : NativeInt;
 
procedure Out_num(k:NativeInt);
Begin
T1 := GetTickCount64;
// k n[k] average dist last deltak total time
writeln(k:6,n[k]:12,(n[k]-n[k-deltaK+1]) DIV deltaK:8,T1-T0:8,' ms');
end;
 
BEGIN
writeln('Allocated memory ',2*SizeOf(t_n)+Sizeof(t_n_sum_all));
T0 := GetTickCount64;
while t0 = GetTickCount64 do;
T0 := GetTickCount64;
Init;
 
For i := 1 to maxCnt do
k := FindNewdeltaK;
i := 1;
repeat
repeat
FindNew;
inc(i);
until i=k;
Out_num(k);
k := k+deltaK;
until k>maxCnt;
writeln;
writeln(#13,'The first 30 terms of the Mian-Chowla sequence are');
For i := 1 to 30 do
Line 918 ⟶ 969:
writeln;
writeln;
writeln('The terms 9091 - 100 of the Mian-Chowla sequence are');
For i := 9091 to 100 do
write(n[i],' ');
writeln;
END.
{#####
{https://oeis.org/A005282/b005282.txt
deltaK = 540;
*
maxCnt = (5966 DIV deltaK)*deltaK;
5816 1998326307
Allocated memory 70650384
5817 1998387406
540 2574622 4767 234 ms
5818 1998652370
1080 17315247 27269 2084 ms
*
1620 53808559 67542 7876 ms
...
2160 119743492 121877 20367 ms
5818 1998652370
2700 225432491 195419 43411 ms
3240 377659559 281283 80801 ms
3780 585851493 384664 137472 ms
4320 853722843 494787 217026 ms
4860 1198603744 637443 328136 ms
5400 1613654038 766839 471468 ms
5940 2124053407 944624 659681 ms
 
real 9m5510m59,050s682s
}
</lang>
{{Out}}
<pre>Allocated memory 2014024
<pre>The first 30 terms of the Mian-Chowla sequence are
100 27219 272 0.002 s
1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312
200 172922 1443 0.011 s
300 514644 3404 0.037 s
400 1144080 6197 0.090 s
500 2085045 9398 0.179 s
600 3375910 12689 0.311 s
700 5253584 18705 0.520 s
800 7600544 23438 0.801 s
900 10441056 28339 1.160 s
1000 14018951 35611 1.640 s
The first 30 terms of the Mian-Chowla sequence are
1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312
 
The terms 9091 - 100 of the Mian-Chowla sequence are
21948 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219 </pre>
 
real 0m0,002s
</pre>
 
=={{header|Perl}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/288754"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information