[metapost] recursion in MP/MF

Larry Siebenmann laurent at math.toronto.edu
Thu Jan 20 06:41:23 CET 2005



Hans writes:

 > that [parameter] stack is now 300

What is the unit?

How can we print out our various capacity limits
and learn what the printout means?

My *parameter* stack size is reported to be 150
when Jackowski's test (below) fails to sort 31 elements
So Hans should get up to about 60. Correct?

But Knuth's simpler example (following) fails 
at about n=60 because  my *input* stack size limit is 60.
Hans what is your *input* stack size limit?

Taco replied:

 > The 'bad' test is pretty huge:
 > 
 >    257 + hash_size + 14 + 1 + (3 * param_size) < max_halfword
 > 
 > Since max_halfword is 268435455 in web2c, there is some room for
 > extension ;-)
 > (but it would still be pre-allocated memory).

It would be nice to know how far it has been extended in 
existing compilations.  So, if anyone takes the time to run 
the tests below, do please post your results. 

Cheers

Laurent Siebenmann


% --- --- --- --- --- 
vardef quicksort@#(expr i,j)=
% sorts numeric array |@#[i..j]| 
%using Tony Hoare's ``quick sort'' method;
% B. Jackowski's test
 if i<j:
  save k,l,sort_cell;
  sort_cell:=@#[i];
  l:=i;
  for k:=i+1 upto j:
   if @#[k]<sort_cell:
     @#[l]:=@#[k]; @#[k]:=@#[l+1];
    l:=l+1;
   fi
  endfor
  @#[l]:=sort_cell;
  quicksort@#(i,l-1); quicksort@#(l+1,j);
 fi
enddef;

n:=30; % SUCCESS LS (OzTeX) 
n:=31; % FAILURE LS (OzTeX) param stack size 150

for i:=1 upto n: A[i]:=n-i; endfor

quicksort A(1,n); showvariable A;

end.
% --- --- --- --- ---

%%%%% (Knuth)
def recurse=
  n:=n+1; message decimal n;
  %if n< 59: recurse; fi; %% SUCCESS 
  if n< 60: recurse; fi; 
    %% FAILURE LS (OzTeX) input stack size 60
enddef;

n:=0; recurse;

end
%%%%%



More information about the metapost mailing list