hermann on Tue, 12 Mar 2024 09:06:28 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Avoid using "listput()" if possible?


Yesterday I was happy to have working "SquaresRepresentations(n,k)" using "for(...foreach(...listput(..)))".

...
for(b=a,m,foreach(SquaresRepresentations(n-b^2,k-1,b),s,listput(R,concat([b],s))));
  Vec(R);
}


Today I learned that I do not need listput():

SquaresRepresentations(n,k,a=0)={
  my(m=sqrtint(n\k));
  if(k==1,return(if(m>=a&&n==m^2,[m],[])));
  [concat([b],s)|b<-[a..m];s<-SquaresRepresentations(n-b^2,k-1,b)];
}

This works because the recursive call returns empty vector if things don't sum up.

pi@raspberrypi5:~ $ gp -q SquaresRepresentations.2.gp
? SquaresRepresentations(13*17,4)
[[0, 0, 5, 14], [0, 0, 10, 11], [0, 3, 4, 14], [0, 4, 6, 13], [0, 6, 8, 11], [2, 3, 8, 12], [2, 6, 9, 10], [4, 5, 6, 12], [6, 6, 7, 10]]
?

I see that "listput()" is definitely needed in some scenarios. Question is, whether using lists should be avoided if possible as above? Without list above looks nicer to me; is a general statement about runtimes with/without list on big inputs possible?


Regards,

Hermann.