From: Elvin P. <elv...@ya...> - 2004-07-28 16:59:38
|
Hello, One of the stated advantages is tail recursion is that it can be optmized automatically into loops. (defun three-n (n m) (cond ((= n 1) m) ((oddp n) (three-n (1+ (* 3 n)) (1+ m))) (t (three-n (/ n 2) (1+ m))))) This function remains unoptimized even after I call compile. Is there any command to force such optimization? TIA. __________________________________ Do you Yahoo!? New and Improved Yahoo! Mail - Send 10MB messages! http://promotions.yahoo.com/new_mail |
From: Pascal J.B. <pj...@in...> - 2004-07-28 17:55:14
|
Elvin Peterson writes: > Hello, > One of the stated advantages is tail recursion is > that it can be optmized automatically into loops. > > (defun three-n (n m) > (cond > ((= n 1) m) > ((oddp n) (three-n (1+ (* 3 n)) (1+ m))) > (t (three-n (/ n 2) (1+ m))))) > > This function remains unoptimized even after I call > compile. Is there any command to force such > optimization? I see it optimized: CL-USER> (defun three-n (n m) (cond ((= n 1) m) ((oddp n) (three-n (1+ (* 3 n)) (1+ m))) (t (three-n (/ n 2) (1+ m))))) THREE-N CL-USER> (compile 'three-n) THREE-N NIL NIL CL-USER> (disassemble 'three-n) Disassembly of function THREE-N (CONST 0) = 1 (CONST 1) = 3 (CONST 2) = 1/2 2 required arguments 0 optional arguments No rest parameter No keyword parameters 22 byte-code instructions: 0 L0 0 (LOAD&PUSH 2) 1 (CONST&PUSH 0) ; 1 2 (CALLSR&JMPIF 1 45 L22) ; = 6 (LOAD&PUSH 2) 7 (CALLS2&JMPIF 148 L25) ; ODDP 10 (CONST&PUSH 2) ; 1/2 11 (LOAD&PUSH 3) 12 (CALLSR 2 55) ; * 15 L15 15 (PUSH) 16 (LOAD&INC&PUSH 2) 18 (JMPTAIL 2 5 L0) 22 L22 22 (LOAD 1) 23 (SKIP&RET 3) 25 L25 25 (CONST&PUSH 1) ; 3 26 (LOAD&PUSH 3) 27 (CALLSR&PUSH 2 55) ; * 30 (CALLS2 150) ; 1+ 32 (JMP L15) NIL CL-USER> (lisp-implementation-version) "2.33.1 (2004-05-22) (built 3297451256) (memory 3297451635)" CL-USER> -- __Pascal Bourguignon__ http://www.informatimago.com/ There is no worse tyranny than to force a man to pay for what he does not want merely because you think it would be good for him. -- Robert Heinlein |
From: Elvin P. <elv...@ya...> - 2004-07-28 18:17:22
|
--- "Pascal J.Bourguignon" wrote: > Elvin Peterson writes: > > Hello, > > One of the stated advantages is tail recursion > is > > that it can be optmized automatically into loops. > > > > (defun three-n (n m) > > (cond > > ((= n 1) m) > > ((oddp n) (three-n (1+ (* 3 n)) (1+ m))) > > (t (three-n (/ n 2) (1+ m))))) > > > > This function remains unoptimized even after I > call > > compile. Is there any command to force such > > optimization? > > I see it optimized: > > > CL-USER> (defun three-n (n m) > (cond > ((= n 1) m) > ((oddp n) (three-n (1+ (* 3 n)) (1+ m))) > (t (three-n (/ n 2) (1+ m))))) > THREE-N > CL-USER> (compile 'three-n) > THREE-N > NIL > NIL > CL-USER> (disassemble 'three-n) > > > Disassembly of function THREE-N > (CONST 0) = 1 > (CONST 1) = 3 > (CONST 2) = 1/2 > 2 required arguments > 0 optional arguments > No rest parameter > No keyword parameters > 22 byte-code instructions: > 0 L0 > 0 (LOAD&PUSH 2) > 1 (CONST&PUSH 0) ; 1 > 2 (CALLSR&JMPIF 1 45 L22) ; = > 6 (LOAD&PUSH 2) > 7 (CALLS2&JMPIF 148 L25) ; ODDP > 10 (CONST&PUSH 2) ; 1/2 > 11 (LOAD&PUSH 3) > 12 (CALLSR 2 55) ; * > 15 L15 > 15 (PUSH) > 16 (LOAD&INC&PUSH 2) > 18 (JMPTAIL 2 5 L0) > 22 L22 > 22 (LOAD 1) > 23 (SKIP&RET 3) > 25 L25 > 25 (CONST&PUSH 1) ; 3 > 26 (LOAD&PUSH 3) > 27 (CALLSR&PUSH 2 55) ; * > 30 (CALLS2 150) ; 1+ > 32 (JMP L15) > NIL This is what I get too. I have the following code: (defun max-cycle-len (n m) (let ((max-len 0)) (dotimes (i (- m n) max-len) (setf max-len (max (three-n (+ i n) 1) max-len))))) 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. 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. TIA. __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com |
From: Pascal J.B. <pj...@in...> - 2004-07-28 20:51:11
|
Elvin Peterson writes: > > > (defun three-n (n m) > > > (cond > > > ((= n 1) m) > > > ((oddp n) (three-n (1+ (* 3 n)) (1+ m))) > > > (t (three-n (/ n 2) (1+ m))))) > > > > > This is what I get too. I have the following code: > > (defun max-cycle-len (n m) > (let ((max-len 0)) > (dotimes (i (- m n) max-len) > (setf max-len (max (three-n (+ i n) 1) > max-len))))) > > 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 three-n? There is even yet no proof that it will terminate for all integer input! > 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: CL-USER> (time (max-cycle-len 1000000 1000010)) Real time: 0.001348 sec. Run time: 0.0 sec. Space: 0 Bytes 259 -- __Pascal Bourguignon__ http://www.informatimago.com/ There is no worse tyranny than to force a man to pay for what he does not want merely because you think it would be good for him. -- Robert Heinlein |
From: Elvin P. <elv...@ya...> - 2004-07-29 02:43:03
|
--- "Pascal J.Bourguignon" wrote: > > Elvin Peterson writes: > > > > (defun three-n (n m) > > > > (cond > > > > ((= n 1) m) > > > > ((oddp n) (three-n (1+ (* 3 n)) (1+ m))) > > > > (t (three-n (/ n 2) (1+ m))))) > > > > > > > > This is what I get too. I have the following > code: > > > > (defun max-cycle-len (n m) > > (let ((max-len 0)) > > (dotimes (i (- m n) max-len) > > (setf max-len (max (three-n (+ i n) 1) > > max-len))))) > > > > 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 three-n? > 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: > > CL-USER> (time (max-cycle-len 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., (max-cycle-len 1 1000000) Thanks. __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com |
From: Pascal J.B. <pj...@in...> - 2004-07-29 04:36:03
|
Elvin Peterson writes: > > > 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: > > > > CL-USER> (time (max-cycle-len 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., > > (max-cycle-len 1 1000000) But 1 is not close to 1000000, at least by my undestanding of close. Do you believe that max_cycle_len(1,1000000) would take only 0 second in C? (While still giving you correct results on a 32bit processor?) -- __Pascal Bourguignon__ http://www.informatimago.com/ There is no worse tyranny than to force a man to pay for what he does not want merely because you think it would be good for him. -- Robert Heinlein |
From: Edi W. <ed...@ag...> - 2004-07-29 06:16:32
|
On Thu, 29 Jul 2004 06:35:56 +0200, Pascal J.Bourguignon <pj...@in...> wrote: > Do you believe that max_cycle_len(1,1000000) would take only 0 > second in C? (While still giving you correct results on a 32bit > processor?) You can try yourself: <http://online-judge.uva.es/problemset/data/p100.c.html> Of course, it doesn't complete in 0.0 seconds - I killed the program after it had consumed 100% of my CPU (PIII 1200) for about five minutes. And of course, as Sam Steingold has pointed out, this "solution" fails miserably as soon as the numbers involved don't fit into 32 bits anymore while a Lisp program will yield correct results. Cheers, Edi. |
From: Elvin P. <elv...@ya...> - 2004-07-29 14:53:10
|
--- Edi Weitz wrote: > On Thu, 29 Jul 2004 06:35:56 +0200, Pascal > J.Bourguignon wrote: > > > Do you believe that max_cycle_len(1,1000000) would > take only 0 > > second in C? (While still giving you correct > results on a 32bit > > processor?) > > You can try yourself: > > > <http://online-judge.uva.es/problemset/data/p100.c.html> > > Of course, it doesn't complete in 0.0 seconds - I > killed the program > after it had consumed 100% of my CPU (PIII 1200) for > about five > minutes. And of course, as Sam Steingold has pointed > out, this > "solution" fails miserably as soon as the numbers > involved don't fit > into 32 bits anymore while a Lisp program will yield > correct results. Ack! If you can't trust a random site on the Internet, who can you trust? However, in their results page, they had the top 20 people finishing with time 0.00. Thanks again to all those who replied. __________________________________ Do you Yahoo!? Read only the mail you want - Yahoo! Mail SpamGuard. http://promotions.yahoo.com/new_mail |
From: Edi W. <ed...@ag...> - 2004-07-29 17:15:01
|
On Thu, 29 Jul 2004 07:53:03 -0700 (PDT), Elvin Peterson <elv...@ya...> wrote: > Ack! If you can't trust a random site on the Internet, who can you > trust? However, in their results page, they had the top 20 people > finishing with time 0.00. To make this clear: The C program took more than five minutes for the input that you proposed. That doesn't mean it couldn't perform in 0.0 seconds for other input. I think the contest site only posted the timing results but not the input that was used. Edi. |
From: Sam S. <sd...@gn...> - 2004-07-28 21:31:13
|
> * Elvin Peterson <ryiva_crgrefba@lnubb.pbz> [2004-07-28 11:17:13 -0700]: > > (defun max-cycle-len (n m) > (let ((max-len 0)) > (dotimes (i (- m n) max-len) > (setf max-len (max (three-n (+ i n) 1) > max-len))))) > > 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. let us investigate: (defun cycle-length (n &optional (len 1) (top 0)) (cond ((= n 1) (values len top)) ((evenp n) (cycle-length (ash n -1) (1+ len) (max top n))) (t (let ((next (1+ (* 3 n)))) (cycle-length next (1+ len) (max top next)))))) (defun max-cycle-length (n m) (loop :with arg :and len = 0 :and top :for i :from n :to m :do (multiple-value-bind (le to) (cycle-length i) (when (> le len) (setq arg i len le top to))) :finally (return (values arg len top)))) thus we are getting not just the max cycle-length, but also the number for which this maximum is achieved and the top intermediate number in the sequence whose length is the cycle-length. then let us see what data is actually allocated: (ext:times (max-cycle-length 1000000 4000000)) Permanent Temporary Class instances bytes instances bytes ----- --------- --------- --------- --------- BIGNUM 1 16 13346541 160531616 ----- --------- --------- --------- --------- Total 1 16 13346541 160531616 Real time: 269.785242 sec. Run time: 254.7262784 sec. Space: 160566840 Bytes GC: 18, GC time: 0.1702448 sec. 3732423 ; 597 ; 294475592320 so, the max cycle-length is 597, it is achieved on 3732423 and the maximum number in the cycle is 294475592320 -- which is a bignum! that's what you see in the TIMES output: there were 13346541 temporary BIGNUMs allocated (for all the numbers in the cycles of all the integers between 1000000 and 4000000) and a single permanent bignum for the return value. So the code operates in fixed stack space but it has to cons up some bignums. Note that (integer-length 294475592320) ==> 39 i.e. 32-bit integers are insufficient to perform the above calculations (contrary to http://acm.uva.es/p/v1/100.html). E.g., (defun max-cycle-length (n m) (loop :with arg :and len = 0 :and top :for i :from n :to m :do (multiple-value-bind (le to) (cycle-length i) (when (> (integer-length to) 32) (format t "~:D --> ~:D, ~:D~%" i le to)) (when (> le len) (setq arg i len le top to))) :finally (return (values arg len top)))) (max-cycle-length 500000 1000000) 502,441 --> 333, 24,414,590,536 504,057 --> 196, 17,202,377,752 538,271 --> 178, 17,202,377,752 540,542 --> 408, 24,648,077,896 540,543 --> 408, 24,648,077,896 559,785 --> 165, 4,711,755,904 565,247 --> 328, 24,414,590,536 567,065 --> 191, 17,202,377,752 577,230 --> 390, 24,648,077,896 577,231 --> 390, 24,648,077,896 581,883 --> 204, 6,973,568,800 608,111 --> 403, 24,648,077,896 626,331 --> 509, 7,222,283,188 629,759 --> 160, 4,711,755,904 630,527 --> 240, 8,501,092,072 637,948 --> 186, 17,202,377,752 637,949 --> 186, 17,202,377,752 637,950 --> 186, 17,202,377,752 640,641 --> 416, 24,648,077,896 649,385 --> 385, 24,648,077,896 654,619 --> 199, 6,973,568,800 655,359 --> 292, 5,516,201,896 656,415 --> 292, 12,601,065,832 665,215 --> 442, 52,483,285,312 669,921 --> 336, 24,414,590,536 687,871 --> 380, 20,077,607,536 689,639 --> 212, 6,973,568,800 704,511 --> 243, 56,991,483,520 704,623 --> 504, 7,222,283,188 717,694 --> 181, 17,202,377,752 717,695 --> 181, 17,202,377,752 720,722 --> 411, 24,648,077,896 720,723 --> 411, 24,648,077,896 730,559 --> 380, 24,648,077,896 736,447 --> 194, 6,973,568,800 747,291 --> 248, 8,501,092,072 753,662 --> 331, 24,414,590,536 753,663 --> 331, 24,414,590,536 756,086 --> 194, 17,202,377,752 756,087 --> 194, 17,202,377,752 763,675 --> 318, 10,296,265,264 769,641 --> 393, 24,648,077,896 780,391 --> 331, 23,996,686,912 807,407 --> 176, 17,202,377,752 810,814 --> 406, 24,648,077,896 810,815 --> 406, 24,648,077,896 822,139 --> 344, 23,996,686,912 829,087 --> 194, 13,428,962,944 833,775 --> 357, 5,697,379,672 839,678 --> 163, 4,711,755,904 839,679 --> 163, 4,711,755,904 840,702 --> 243, 8,501,092,072 840,703 --> 243, 8,501,092,072 847,871 --> 326, 24,414,590,536 850,596 --> 189, 17,202,377,752 850,597 --> 189, 17,202,377,752 850,598 --> 189, 17,202,377,752 854,191 --> 419, 24,648,077,896 859,135 --> 313, 10,296,265,264 865,846 --> 388, 24,648,077,896 865,847 --> 388, 24,648,077,896 872,825 --> 202, 6,973,568,800 886,953 --> 445, 52,483,285,312 901,119 --> 251, 4,494,683,032 906,175 --> 445, 8,368,783,432 912,167 --> 401, 24,648,077,896 917,161 --> 383, 20,077,607,536 919,518 --> 215, 6,973,568,800 919,519 --> 215, 6,973,568,800 920,559 --> 308, 5,516,201,896 924,907 --> 339, 23,996,686,912 937,599 --> 339, 5,618,306,500 939,497 --> 507, 7,222,283,188 944,639 --> 158, 4,711,755,904 945,791 --> 238, 8,501,092,072 956,924 --> 184, 17,202,377,752 956,925 --> 184, 17,202,377,752 956,926 --> 184, 17,202,377,752 960,962 --> 414, 24,648,077,896 960,963 --> 414, 24,648,077,896 974,078 --> 383, 24,648,077,896 974,079 --> 383, 24,648,077,896 975,015 --> 321, 7,597,578,112 981,929 --> 197, 6,973,568,800 983,039 --> 290, 5,516,201,896 984,623 --> 290, 12,601,065,832 997,823 --> 440, 52,483,285,312 837,799 ; 525 ; 2,974,984,576 note that max LEN and max TOP are achieved on different arguments! -- Sam Steingold (http://www.podval.org/~sds) running w2k <http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/> <http://www.mideasttruth.com/> <http://www.honestreporting.com> When we write programs that "learn", it turns out we do and they don't. |
From: Elvin P. <elv...@ya...> - 2004-07-29 02:53:49
|
--- Sam Steingold wrote: > > * Elvin Peterson <ryiva_crgrefba@lnubb.pbz> > [2004-07-28 11:17:13 -0700]: > > > > (defun max-cycle-len (n m) > > (let ((max-len 0)) > > (dotimes (i (- m n) max-len) > > (setf max-len (max (three-n (+ i n) 1) > > max-len))))) > > > > 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. > > let us investigate: > > (defun cycle-length (n &optional (len 1) (top 0)) > (cond ((= n 1) (values len top)) > ((evenp n) (cycle-length (ash n -1) (1+ len) > (max top n))) > (t (let ((next (1+ (* 3 n)))) > (cycle-length next (1+ len) (max top > next)))))) > > (defun max-cycle-length (n m) > (loop :with arg :and len = 0 :and top :for i :from > n :to m :do > (multiple-value-bind (le to) (cycle-length i) > (when (> le len) (setq arg i len le top to))) > :finally (return (values arg len top)))) > > thus we are getting not just the max cycle-length, > but also the number > for which this maximum is achieved and the top > intermediate number in > the sequence whose length is the cycle-length. > > then let us see what data is actually allocated: > > (ext:times (max-cycle-length 1000000 4000000)) > > > Permanent Temporary > Class instances > bytes instances bytes > ----- --------- > --------- --------- --------- > BIGNUM 1 > 16 13346541 160531616 > ----- --------- > --------- --------- --------- > Total 1 > 16 13346541 160531616 > > Real time: 269.785242 sec. > Run time: 254.7262784 sec. > Space: 160566840 Bytes > GC: 18, GC time: 0.1702448 sec. > 3732423 ; > 597 ; > 294475592320 > > so, the max cycle-length is 597, it is achieved on > 3732423 and the > maximum number in the cycle is 294475592320 -- which > is a bignum! > > that's what you see in the TIMES output: there were > 13346541 temporary > BIGNUMs allocated (for all the numbers in the cycles > of all the integers > between 1000000 and 4000000) and a single permanent > bignum for the > return value. > > So the code operates in fixed stack space but it has > to cons up some > bignums. Does this mean that the output of times is not the actual maximum memory that is used by the function? > > Note that > > (integer-length 294475592320) ==> 39 > > i.e. 32-bit integers are insufficient to perform the > above calculations > (contrary to http://acm.uva.es/p/v1/100.html). So the performance problem is purely due to BIGNUM allocation? I suppose then the code will run very fast on a machine with 64 bit integers. > > E.g., > > (defun max-cycle-length (n m) > (loop :with arg :and len = 0 :and top :for i :from > n :to m :do > (multiple-value-bind (le to) (cycle-length i) > (when (> (integer-length to) 32) > (format t "~:D --> ~:D, ~:D~%" i le to)) > (when (> le len) (setq arg i len le top to))) > :finally (return (values arg len top)))) > > (max-cycle-length 500000 1000000) > 502,441 --> 333, 24,414,590,536 > 504,057 --> 196, 17,202,377,752 > 538,271 --> 178, 17,202,377,752 > 540,542 --> 408, 24,648,077,896 > 540,543 --> 408, 24,648,077,896 > 559,785 --> 165, 4,711,755,904 > 565,247 --> 328, 24,414,590,536 > 567,065 --> 191, 17,202,377,752 > 577,230 --> 390, 24,648,077,896 > 577,231 --> 390, 24,648,077,896 > 581,883 --> 204, 6,973,568,800 > 608,111 --> 403, 24,648,077,896 > 626,331 --> 509, 7,222,283,188 > 629,759 --> 160, 4,711,755,904 > 630,527 --> 240, 8,501,092,072 > 637,948 --> 186, 17,202,377,752 > 637,949 --> 186, 17,202,377,752 > 637,950 --> 186, 17,202,377,752 > 640,641 --> 416, 24,648,077,896 > 649,385 --> 385, 24,648,077,896 > 654,619 --> 199, 6,973,568,800 > 655,359 --> 292, 5,516,201,896 > 656,415 --> 292, 12,601,065,832 > 665,215 --> 442, 52,483,285,312 > 669,921 --> 336, 24,414,590,536 > 687,871 --> 380, 20,077,607,536 > 689,639 --> 212, 6,973,568,800 > 704,511 --> 243, 56,991,483,520 > 704,623 --> 504, 7,222,283,188 > 717,694 --> 181, 17,202,377,752 > 717,695 --> 181, 17,202,377,752 > 720,722 --> 411, 24,648,077,896 > 720,723 --> 411, 24,648,077,896 > 730,559 --> 380, 24,648,077,896 > 736,447 --> 194, 6,973,568,800 > 747,291 --> 248, 8,501,092,072 > 753,662 --> 331, 24,414,590,536 > 753,663 --> 331, 24,414,590,536 > 756,086 --> 194, 17,202,377,752 > 756,087 --> 194, 17,202,377,752 > 763,675 --> 318, 10,296,265,264 > 769,641 --> 393, 24,648,077,896 > 780,391 --> 331, 23,996,686,912 > 807,407 --> 176, 17,202,377,752 > 810,814 --> 406, 24,648,077,896 > 810,815 --> 406, 24,648,077,896 > 822,139 --> 344, 23,996,686,912 > 829,087 --> 194, 13,428,962,944 > 833,775 --> 357, 5,697,379,672 > 839,678 --> 163, 4,711,755,904 > 839,679 --> 163, 4,711,755,904 > 840,702 --> 243, 8,501,092,072 > 840,703 --> 243, 8,501,092,072 > 847,871 --> 326, 24,414,590,536 > 850,596 --> 189, 17,202,377,752 > 850,597 --> 189, 17,202,377,752 > 850,598 --> 189, 17,202,377,752 > 854,191 --> 419, 24,648,077,896 > 859,135 --> 313, 10,296,265,264 > 865,846 --> 388, 24,648,077,896 > 865,847 --> 388, 24,648,077,896 > 872,825 --> 202, 6,973,568,800 > 886,953 --> 445, 52,483,285,312 > 901,119 --> 251, 4,494,683,032 > 906,175 --> 445, 8,368,783,432 > 912,167 --> 401, 24,648,077,896 > 917,161 --> 383, 20,077,607,536 > 919,518 --> 215, 6,973,568,800 > 919,519 --> 215, 6,973,568,800 > 920,559 --> 308, 5,516,201,896 > 924,907 --> 339, 23,996,686,912 > 937,599 --> 339, 5,618,306,500 > 939,497 --> 507, 7,222,283,188 > 944,639 --> 158, 4,711,755,904 > 945,791 --> 238, 8,501,092,072 > 956,924 --> 184, 17,202,377,752 > 956,925 --> 184, 17,202,377,752 > 956,926 --> 184, 17,202,377,752 > 960,962 --> 414, 24,648,077,896 > 960,963 --> 414, 24,648,077,896 > 974,078 --> 383, 24,648,077,896 > 974,079 --> 383, 24,648,077,896 > 975,015 --> 321, 7,597,578,112 > 981,929 --> 197, 6,973,568,800 > 983,039 --> 290, 5,516,201,896 > 984,623 --> 290, 12,601,065,832 > 997,823 --> 440, 52,483,285,312 > > 837,799 ; > 525 ; > 2,974,984,576 > > note that max LEN and max TOP are achieved on > different arguments! This makes sense in light of the earlier explanation. Thanks for all the help! __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com |
From: Sam S. <sd...@gn...> - 2004-07-29 13:44:42
|
> * Elvin Peterson <ryiva_crgrefba@lnubb.pbz> [2004-07-28 19:53:38 -0700]: > > --- Sam Steingold wrote: > >> >> So the code operates in fixed stack space but it has to cons up some >> bignums. > > Does this mean that the output of times is not the > actual maximum memory that is used by the function? both EXT:TIMES and TIME print the total memory allocated. (not the maximum memory used) >> Note that >> >> (integer-length 294475592320) ==> 39 >> >> i.e. 32-bit integers are insufficient to perform the >> above calculations >> (contrary to http://acm.uva.es/p/v1/100.html). > > So the performance problem is purely due to BIGNUM allocation? no, it's not just allocations, it's also calculations. the larger the numbers, the longer the cycle and the more expensive is the cycle-length computation because bignum operations are more expensive for larger bignums. > I suppose then the code will run very fast on a machine with 64 bit > integers. as long as everything fits into fixnums, performance is better. unfortunately, even on a 64 bit machine, fixnums are rarely large (32 bits on CLISP right now, see <https://sourceforge.net/tracker/?func=detail&atid=351355&aid=999750&group_id=1355>). -- Sam Steingold (http://www.podval.org/~sds) running w2k <http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/> <http://www.mideasttruth.com/> <http://www.honestreporting.com> Booze is the answer. I can't remember the question. |
From: Elvin P. <elv...@ya...> - 2004-07-29 14:41:17
|
--- Sam Steingold wrote: > > * Elvin Peterson <ryiva_crgrefba@lnubb.pbz> > > >> Note that > >> > >> (integer-length 294475592320) ==> 39 > >> > >> i.e. 32-bit integers are insufficient to perform > the > >> above calculations > >> (contrary to http://acm.uva.es/p/v1/100.html). > > > > So the performance problem is purely due to BIGNUM > allocation? > > no, it's not just allocations, it's also > calculations. > > the larger the numbers, the longer the cycle and the > more expensive is > the cycle-length computation because bignum > operations are more > expensive for larger bignums. > > > > I suppose then the code will run very fast on a > machine with 64 bit > > integers. > > as long as everything fits into fixnums, performance > is better. > unfortunately, even on a 64 bit machine, fixnums are > rarely large > (32 bits on CLISP right now, see Looks like it will take a lot of effort to implement 64 bit in clisp. But it may be a long time before systems are 64 bit by default (I know several Solaris installations which are still 32 bit, lowest common denominator and everything). __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com |
From: Raymond T. <ray...@er...> - 2004-07-29 16:26:14
|
>>>>> "Elvin" == Elvin Peterson <elv...@ya...> writes: Elvin> Looks like it will take a lot of effort to implement Elvin> 64 bit in clisp. But it may be a long time before Elvin> systems are 64 bit by default (I know several Solaris Elvin> installations which are still 32 bit, lowest common Elvin> denominator and everything). What kind of Sun machines are they running? Ultra 2 slower than 170 MHz? Or maybe they're still running Solaris 2.5? All Ultra machines are 64-bit, but I don't think Solaris became 64-bit until 2.6 or 2.7. (Could be wrong, though.) Ray |
From: Elvin P. <elv...@ya...> - 2004-07-29 16:46:38
|
--- Raymond Toy <ray...@er...> wrote: > >>>>> "Elvin" == Elvin Peterson > <elv...@ya...> writes: > > Elvin> Looks like it will take a lot of effort > to implement > Elvin> 64 bit in clisp. But it may be a long > time before > Elvin> systems are 64 bit by default (I know > several Solaris > Elvin> installations which are still 32 bit, > lowest common > Elvin> denominator and everything). > > What kind of Sun machines are they running? Ultra 2 > slower than 170 > MHz? Or maybe they're still running Solaris 2.5? > All Ultra machines > are 64-bit, but I don't think Solaris became 64-bit > until 2.6 or 2.7. > (Could be wrong, though.) Only a few of them were older OSes, but going 64 bit would cause a lot of administrative overhead with the binaries (on NFS) for different machines. __________________________________ Do you Yahoo!? Yahoo! Mail - 50x more storage than other providers! http://promotions.yahoo.com/new_mail |
From: Raymond T. <ray...@er...> - 2004-07-29 16:56:23
|
>>>>> "Elvin" == Elvin Peterson <elv...@ya...> writes: Elvin> Only a few of them were older OSes, but going 64 bit Elvin> would cause a lot of administrative overhead with the Elvin> binaries (on NFS) for different machines. Don't see how that follows. I only run 32-bit apps on the 64-bit Sun boxes at work. I have no need for 64-bit apps, and I don't we have any anywhere either. :-) But this no longer has anything to do with clisp, so.... Ray |
From: Raymond T. <ray...@er...> - 2004-07-29 15:08:15
|
>>>>> "Sam" == Sam Steingold <sd...@gn...> writes: Sam> as long as everything fits into fixnums, performance is better. Sam> unfortunately, even on a 64 bit machine, fixnums are rarely large Sam> (32 bits on CLISP right now, see Sam> <https://sourceforge.net/tracker/?func=detail&atid=351355&aid=999750&group_id=1355>). Do you mean running a 32-bit lisp on a 64-bit machine? Then yes, you're right. But a 64-bit lisp on a 64-bit machine would presumably have fixnum that are close to 60 bits in length. I'm pretty sure that 64-bit ACL uses 60-bit fixnums. I suspect cmucl and sbcl will have 60-bit fixnums if the amd64 port ever gets done. Ray |