MSasu Posted June 24, 2011 Share Posted June 24, 2011 Recursion See "Recursion" An interesting article on recursion. Regards, Mircea Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted June 24, 2011 Share Posted June 24, 2011 Very interesting indeed! Thanks for sharing Quote Link to comment Share on other sites More sharing options...
MSasu Posted June 24, 2011 Author Share Posted June 24, 2011 (edited) My workstation (P4, 4.3GHz, 2GB RAM) is still computing the AutoLISP version - was started before posted the above. Will post the result later. (defun fib_rec( n ) (if (< n 2) n (+ (fib_rec (- n 2)) (fib_rec (- n 1))) ) ) Regards, Mircea Edited June 24, 2011 by MSasu code added Quote Link to comment Share on other sites More sharing options...
MSasu Posted June 24, 2011 Author Share Posted June 24, 2011 Is done! It took 1657 seconds (27 minutes and 37 second) on a P4, 4.3GHz, 2GB RAM. Regards, Mircea Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted June 24, 2011 Share Posted June 24, 2011 I really like his method to use the binary representation of 'n' and successively square the matrix, in LISP this might be: (defun fib_mat ( n / l a b c ) (while (< 0 n) (setq l (cons (rem n 2) l) n (/ n 2)) ) (setq a 1. b 0. c 1.) (foreach x l (mapcar 'set '(a b c) (list (+ (* a a) (* b b)) (+ (* a b) (* b c)) (+ (* b b) (* c c))) ) (if (< 0 x) (setq a b b c c (+ b a))) ) b ) Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted June 24, 2011 Share Posted June 24, 2011 I suppose the simplest iterative way would be: (defun fib ( n / a b c) (setq a 0. b 1. c 1.) (repeat (- n 2) (setq a b b c c (+ a c))) c ) Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted June 24, 2011 Share Posted June 24, 2011 Benchmarking the obvious performance improvements of log2(n) iterations over (n-2) iterations: _$ (Benchmark '((fib 100) (fib_mat 100))) Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s): (FIB_MAT 100).....1591 / 1.22 <fastest> (FIB 100).........1934 / 1 <slowest> _$ (Benchmark '((fib 1000) (fib_mat 1000))) Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s): (FIB_MAT 1000).....1014 / 7.28 <fastest> (FIB 1000).........7379 / 1 <slowest> Quote Link to comment Share on other sites More sharing options...
MSasu Posted June 30, 2011 Author Share Posted June 30, 2011 Interesting solutions, Lee! I'm sure that you will enjoy this article also. Regards, Mircea Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted June 30, 2011 Share Posted June 30, 2011 Interesting solutions, Lee!I'm sure that you will enjoy this article also. Thanks Mircea, I really enjoyed writing them That looks like another interesting article, I shall have a read. Lee Quote Link to comment Share on other sites More sharing options...
Lee Mac Posted July 12, 2011 Share Posted July 12, 2011 I'm sure that you will enjoy this article also. Got a chance to read that article the other day, a very interesting read indeed! The majority of his comments are absolutely spot on - especially the part regarding the public perception of mathematicians. Thanks for sharing it. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.