154 lines
3.2 KiB
ObjectPascal
154 lines
3.2 KiB
ObjectPascal
program MianChowla;
|
|
//compiling with /usr/lib/fpc/3.2.0/ppcx64.2 -MDelphi -O4 -al "%f"
|
|
{$CODEALIGN proc=8,loop=4 }
|
|
uses
|
|
sysutils;
|
|
const
|
|
deltaK = 100;
|
|
maxCnt = 1000;
|
|
type
|
|
tElem = Uint32;
|
|
tpElem = pUint32;
|
|
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;
|
|
|
|
maxIdx,
|
|
maxN,
|
|
max_SumIdx : NativeUInt;
|
|
|
|
procedure Init;
|
|
var
|
|
i : NativeInt;
|
|
begin
|
|
maxIdx := 1;
|
|
maxN := 1;
|
|
n[maxIdx] := maxN;
|
|
max_SumIdx := 1;
|
|
n_sum_all[max_SumIdx] := 2*maxN;
|
|
|
|
For i := 0 to maxCnt do
|
|
n_LastPos[i] := 1;
|
|
end;
|
|
|
|
procedure InsertNew_sum(NewValue:NativeUint);
|
|
//insertion already knowning the positions
|
|
var
|
|
pElem :tpElem;
|
|
InsIdx,chkIdx,oldIdx,newIdx : nativeInt;
|
|
Begin
|
|
newIdx := maxIdx;
|
|
oldIdx := max_SumIdx;
|
|
//append new value
|
|
inc(maxIdx);
|
|
n[maxIdx] := NewValue;
|
|
//extend sum_
|
|
inc(max_SumIdx,maxIdx);
|
|
//heighest value already known
|
|
InsIdx := max_SumIdx;
|
|
n_sum_all[InsIdx] := 2*NewValue;
|
|
//stop mark
|
|
n_sum_all[InsIdx+1] := High(tElem);
|
|
pElem := @n_sum_all[0];
|
|
dec(InsIdx);
|
|
//n_LastPos[newIdx]+newIdx-1 == InsIdx
|
|
repeat
|
|
//move old bigger values
|
|
chkIdx := n_LastPos[newIdx]+newIdx-1;
|
|
while InsIdx > chkIdx do
|
|
Begin
|
|
pElem[InsIdx] := pElem[oldIdx];
|
|
dec(InsIdx);
|
|
dec(oldIdx);
|
|
end;
|
|
//insert new value
|
|
pElem[InsIdx] := NewValue+n[newIdx];
|
|
dec(InsIdx);
|
|
dec(newIdx);
|
|
//all inserted
|
|
until newIdx <= 0;
|
|
//new minimum search position one behind, oldidx is one to small
|
|
inc(oldidx,2);
|
|
For newIdx := 1 to maxIdx do
|
|
n_LastPos[newIdx] := oldIdx;
|
|
end;
|
|
procedure FindNew;
|
|
var
|
|
pSumAll,pn : tpElem;
|
|
i,LastCheckPos,newValue,newSum : NativeUint;
|
|
TestRes : boolean;
|
|
begin
|
|
//start value = last inserted value
|
|
newValue := n[maxIdx];
|
|
pSumAll := @n_sum_all[0];
|
|
pn := @n[0];
|
|
repeat
|
|
//try next number
|
|
inc(newValue);
|
|
LastCheckPos := n_LastPos[1];
|
|
i := 1;
|
|
//check if sum = new is already n all_sum
|
|
repeat
|
|
newSum := newValue+pn[i];
|
|
IF LastCheckPos < n_LastPos[i] then
|
|
LastCheckPos := n_LastPos[i];
|
|
while pSumAll[LastCheckPos] < newSum do
|
|
inc(LastCheckPos);
|
|
//memorize LastCheckPos;
|
|
n_LastPos[i] := LastCheckPos;
|
|
TestRes:= pSumAll[LastCheckPos] = newSum;
|
|
IF TestRes then
|
|
BREAK;
|
|
inc(i);
|
|
until i>maxIdx;
|
|
//found?
|
|
If not(TestRes) then
|
|
BREAK;
|
|
until false;
|
|
InsertNew_sum(newValue);
|
|
end;
|
|
|
|
var
|
|
T1,T0: Int64;
|
|
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;
|
|
|
|
k := deltaK;
|
|
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
|
|
write(n[i],' ');
|
|
writeln;
|
|
writeln;
|
|
writeln('The terms 91 - 100 of the Mian-Chowla sequence are');
|
|
For i := 91 to 100 do
|
|
write(n[i],' ');
|
|
writeln;
|
|
END.
|