From: Elvin Peterson <elvin_peterson@ya...>  20040729 02:43:03

 "Pascal J.Bourguignon" wrote: > > Elvin Peterson writes: > > > > (defun threen (n m) > > > > (cond > > > > ((= n 1) m) > > > > ((oddp n) (threen (1+ (* 3 n)) (1+ m))) > > > > (t (threen (/ n 2) (1+ m))))) > > > > > > > > This is what I get too. I have the following > code: > > > > (defun maxcyclelen (n m) > > (let ((maxlen 0)) > > (dotimes (i ( m n) maxlen) > > (setf maxlen (max (threen (+ i n) 1) > > maxlen))))) > > > > Since this is purely iterative, shouldn't the > memory > > requirements be constant? However, I cannot run > this > > for values greater than 1,00,000, as it takes a > lot of > > time and space. > > Did you try to evaluate the complexity of threen? > There is even yet no proof that it will terminate > for all integer input! Indeed there is no proof. I think it is an example problem in "A Gentle Introduction to Lisp". However, it has been verified for very large numbers, and in this case the limit is 1,000,000. > > > > This is a problem I found on this site: > > http://acm.uva.es/p/v1/100.html > > And they have stated that C/C++ solutions run in > time > > 0.00 for values of n,m close to 1,000,000. > > Same here in clisp: > > CLUSER> (time (maxcyclelen 1000000 1000010)) > > Real time: 0.001348 sec. > Run time: 0.0 sec. > Space: 0 Bytes > 259 > It will be much longer if you actually want to find the maximum length, i.e., (maxcyclelen 1 1000000) Thanks. __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com 