#1315 PFACTORANY takes a very long time in some cases

open
nobody
Lisp Core (471)
5
2012-11-18
2007-12-25
No

The simulated annealing code posted on the mailing list circa 2007-12-23 tickles a bug in PFACTORANY or one of its callees. The code calls $SIGN on an exponential expression, which eventually calls PFACTORANY, which, for some randomly generated examples, takes a very long time. Here is an example.

(let ((*checkagain nil)) (declare (special *checkagain)) (pfactorany '(#:|%e^(2^(33/50)*5^(33/50)/14039)16000| 1295 5682 0 -10201)))

I believe PFACTORANY or one of its callees is making progress, but slowly.

5.13.0 $SIGN calls PFACTORANY eventually, and (maybe) 5.14.0 does not, so the problem might not be triggered by 5.14.0 (not sure about that). However in 5.14.0 the PFACTORANY problem is still there, from what I can tell.

Here is the simulated annealing code for reference.

kill(all);

load("distrib");

minimize_sa(funname,vars,init,scales,maxiters,t0) :=

block([curval:ev(funname,map("=",vars,init)),
bestval:0,
bestpos:init, curpos:init, temp:t0,
tempfactor:1/100^(1/maxiters)
],
bestval:curval,
for i:1 thru maxiters do
block([nextval:curval,
nextpos:curpos +
map(random_normal,makelist(0,i,1,length(vars)),scales),
randnum:random(1.0)],
(nextval:ev(funname,map("=",vars,nextpos)),
print(nextval, " at ",nextpos),
if(nextval < curval or randnum < exp(-(nextval-curval)/temp))
then
(curpos:nextpos, curval:nextval,
if(nextval < bestval) then
(bestpos:nextpos,bestval:nextval)),
temp:temp*tempfactor)),
map("=",vars,bestpos));

minimize_sa(x^2+y^2,[x,y],[1,3],[.2,.2],200,1);

Discussion

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks