RE : crazy run-time fluctuations (mostly super-slow) -- a bit more data

> -----Message d'origine-----
> De?: maxima-bounces at math.utexas.edu [mailto:maxima-bounces at math.utexas.edu] De la part de
> Oliver Kullmann
> Envoy??: samedi 22 octobre 2011 14:25
> ??: Maxima at math.utexas.edu
> Objet?: Re: [Maxima] crazy run-time fluctuations (mostly super-slow) -- a bit more data
> 
> Just a bit more data (additional to the data from my previous e-mail,
> which I've copied below):
> 
>  - The machine is an Intel i5 running with constant 2.4 GHz (monitored)
>    and 4GB.
>  - The initialisation-file contains "showtime : true;" and other settings.
>  - Running the same example with CLISP in the installation as provided by
>    Suse Linux 11.4:
> 
> kullmann-0:~> maxima
> Maxima 5.25.1 http://maxima.sourceforge.net
> using Lisp CLISP 2.49 (2010-07-07)
> Distributed under the GNU Public License. See the file COPYING.
> Dedicated to the memory of William Schelter.
> The function bug_report() provides bug reporting information.
> (%i1) showtime : true;
> Evaluation took 0.0000 seconds (0.0000 elapsed) using 56 bytes.
> (%o1)                                true
> (%i2) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> Evaluation took 151.1170 seconds (151.4321 elapsed) using 9397.813 MB.
> (%o2) [[2, 1], [7, 1], [107, 1], [1679641, 1], [8255453, 1],
>                      [152778774688461206737, 1], [315114064590027073770947, 1]]
> (%i3) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> Evaluation took 17.4313 seconds (17.4833 elapsed) using 871.713 MB.
> (%o3) [[2, 1], [7, 1], [107, 1], [1679641, 1], [8255453, 1],
>                      [152778774688461206737, 1], [315114064590027073770947, 1]]
> (%i4) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> Evaluation took 211.2639 seconds (211.7062 elapsed) using 12557.245 MB.
> (%o4) [[2, 1], [7, 1], [107, 1], [1679641, 1], [8255453, 1],
>                      [152778774688461206737, 1], [315114064590027073770947, 1]]
> (%i5) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> Evaluation took 265.6916 seconds (266.2212 elapsed) using 16512.327 MB.
> (%o5) [[2, 1], [7, 1], [107, 1], [1679641, 1], [8255453, 1],
>                      [152778774688461206737, 1], [315114064590027073770947, 1]]
> 
> As you can see, it can do it in 17s, but most of the time it takes much longer.
> There seems to be a clear memory-management problem.
> 
> And there are now two Lisp's with that behaviour (Ecl and CLisp).
> 
> Oliver
> 
> > Maxima 5.25.1 http://maxima.sourceforge.net
> > using Lisp ECL 11.1.1
> > (%i1) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> > Evaluation took 12.9080 seconds (12.9520 elapsed)
> > (%o1) [[2,1],[7,1],[107,1],[1679641,1],[8255453,1],[152778774688461206737,1],
> >        [315114064590027073770947,1]]
> > (%i2) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> > Evaluation took 121.3250 seconds (121.5850 elapsed)
> > (%o2) [[2,1],[7,1],[107,1],[1679641,1],[8255453,1],[152778774688461206737,1],
> >        [315114064590027073770947,1]]
> > (%i3) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> > Evaluation took 26.7130 seconds (26.7670 elapsed)
> > (%o3) [[2,1],[7,1],[107,1],[1679641,1],[8255453,1],[152778774688461206737,1],
> >        [315114064590027073770947,1]]
> > (%i4) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> > Evaluation took 64.2590 seconds (64.3860 elapsed)
> > (%o4) [[2,1],[7,1],[107,1],[1679641,1],[8255453,1],[152778774688461206737,1],
> >        [315114064590027073770947,1]]
> >
> > Maxima 5.25.1 http://maxima.sourceforge.net
> > using Lisp ECL 11.1.1
> > (%i1) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> > Evaluation took 62.0850 seconds (62.2240 elapsed)
> > (%o1) [[2,1],[7,1],[107,1],[1679641,1],[8255453,1],[152778774688461206737,1],
> >        [315114064590027073770947,1]]
> > (%i2) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> > Evaluation took 48.7650 seconds (48.8580 elapsed)
> > (%o2) [[2,1],[7,1],[107,1],[1679641,1],[8255453,1],[152778774688461206737,1],
> >        [315114064590027073770947,1]]
> > (%i3) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> > Evaluation took 115.2030 seconds (115.4290 elapsed)
> > (%o3) [[2,1],[7,1],[107,1],[1679641,1],[8255453,1],[152778774688461206737,1],
> >        [315114064590027073770947,1]]
> >
> > Maxima 5.25.1 http://maxima.sourceforge.net
> > using Lisp ECL 11.1.1
> > (%i1) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> > Evaluation took 6.0920 seconds (6.1730 elapsed)
> > (%o1) [[2,1],[7,1],[107,1],[1679641,1],[8255453,1],[152778774688461206737,1],
> >        [315114064590027073770947,1]]
> > (%i2) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> > Evaluation took 70.7340 seconds (70.9190 elapsed)
> > (%o2) [[2,1],[7,1],[107,1],[1679641,1],[8255453,1],[152778774688461206737,1],
> >        [315114064590027073770947,1]]
> > (%i3) ifactors(1000000000000000000000000000000000000000000000000000000000007-1);
> > Evaluation took 103.8050 seconds (104.0320 elapsed)
> > (%o3) [[2,1],[7,1],[107,1],[1679641,1],[8255453,1],[152778774688461206737,1],
> >        [315114064590027073770947,1]]
> >

Hi,

I don't know more about the algorithms to factor integer but it seems Pollard's rho, Pollard's
p-1 and elliptic curve algorithms use some kind of random search. Then it seems not so much
surprising if computation time can change.
Taking a look at ifactor.lisp it seems there is an undocumented switch save_primes.
Maybe this can help you to speed up the things.
Probably the function ifactor is not a good one to check "stability" of the underlying lisp.

Hope This help.

Laurent.

> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima