Re: side-note (bench (length (ack4 3 8000))) (32-bit Cygwin) 0.070 sec

## Advertising

(bench (length (trampoline ack/t 3 8000))) (32-bit Cygwin) 2.010 sec (bench (length (trampoline ack/t 3 8000))) (64-bit Ersatz on Java 8, before =0 and length invocation removal) 9.625 sec (bench (length (trampoline ack/t 3 8000))) (64-bit Ersatz on Java 8, after =0 invocation removal) 4.981 sec (bench (length (trampoline ack/t 3 8000))) (64-bit Ersatz on Java 8, after =0 and length invocation removal) 0.123 sec I therefore conclude that ack/t was programmed badly. My fault. Also, efficient programming in Ersatz apparently _relies_ on things that might speed up a little. Trampolines are still fun, though. New version: (de ack/t (M N R S) (default R '()) (if R (unless S (setq M (pop 'R) ) ) (push 'R M) ) (cond ((not R) (done N) ) ((= M 0) (continue ack/t M (+ N 1) R) ) ((= M 1) (continue ack/t M (+ N 2) R) ) ((= M 2) (continue ack/t M (+ (* N 2) 3) R) ) ((= N 0) (continue ack/t (- M 1) 1 R T) ) (T (push 'R (- M 1) ) (continue ack/t M (- N 1) R T) ) ) ) Thanks for the comments! P.S. For the sake of context and gratuitous post-scripts, most of my work is done using Ersatz PicoLisp with LispIDE / Notepad++ on Windows workstations that run pre-release Java 8 and 108-tab Firefox. Again, thanks! Samuel Dennis R. Borlongan On Thu, May 16, 2013 at 7:33 PM, Alexander Burger <a...@software-lab.de>wrote: > Hi all, > > I didn't bother with trampolines so far, but add some comments to > > On Thu, May 16, 2013 at 12:00:20AM +0800, Samuel Dennis Borlongan wrote: > > ... > > > http://stackoverflow.com/questions/12186672/how-can-i-prevent-my-ackerman-function-from-overflowing-the-stack > > ... > > The bad thing with overflowing your stack is ... well, overflowing your > stack. > > But you may as well overflow your heap, so nothing is gained. > > As it is recommended for PicoLisp anyway to set 'ulimit -s unlimited', > the stack will use as much memory as is physically available, like the > heap. > > The recursive version is usually faster than the one using an explicit > stack, but uses perhaps a little bit more memory because each recursion > level takes several stack lokations. > > > Let's take the standard Ackermann function > > (de ack (M N) > (cond > ((=0 M) (inc N)) > ((=0 N) (ack (dec M) 1)) > (T (ack (dec M) (ack M (dec N)))) ) ) > > Eliminating tail-recursion gives > > (de ack2 (M N) > (loop > (T (=0 M) (inc N)) > (NIL (=0 N) (ack (dec M) (ack M (dec N)))) > (dec 'M) > (one N) ) ) > > Both functions show roughly the same speed, > > : (bench (ack 4 1)) > 249.465 sec > -> 65533 > > : (bench (ack2 4 1)) > 252.487 sec > -> 65533 > > though the less-recursive function is slightly slower (as expected). > > > If we go - as usually recommended - for the iterative version with an > explict stack, > > (de ack3 (M N) > (for (Stack (cons M) Stack) > (if (=0 (setq M (pop 'Stack))) > (inc 'N) > (push 'Stack (dec M)) > (if (=0 N) > (one N) > (push 'Stack M) > (dec 'N) ) ) ) ) > > things get significantly slower: > > : (bench (ack3 4 1)) > 312.028 sec > -> 65533 > > > The fastest is - as expected and described - the "cheating" > version: > > (de ack4 (M N) > (for (Stack (cons M) Stack) > (cond > ((=0 (setq M (pop 'Stack))) (inc 'N)) > ((= 1 M) (inc 'N 2)) > ((= 2 M) (setq N (+ 3 (* 2 N)))) > (T > (push 'Stack (dec M)) > (if (=0 N) > (one N) > (push 'Stack M) > (dec 'N) ) ) ) ) ) > > With that we get > > : (bench (ack4 4 1)) > 0.000 sec > -> 65533 > > : (bench (length (ack4 4 2))) > 0.981 sec > -> 19729 > > > > (de ack/t (M N R S) > > (default R '()) > > (if (> (length R) 0) > > (unless S > > (setq M (pop 'R) ) ) > > (push 'R M) ) > > (cond ((=0 (length R) ) (done N) ) > > ((= M 0) (continue ack/t M (+ N 1) R) ) > > ((= M 1) (continue ack/t M (+ N 2) R) ) > > ((= M 2) (continue ack/t M (+ (* N 2) 3) R) ) > > ((= N 0) (continue ack/t (- M 1) 1 R T) ) > > (T > > (push 'R (- M 1) ) > > (continue ack/t M (- N 1) R T) ) ) ) > > > > Honestly, I hate my Ackermann implementation, not because its performance > > is bad ( (trampoline ack/t 3 8000) takes 1.970 sec and 10.287 sec in > 32-bit > > and ersatz, respectively) > > Are you sure? Here I get > > : (bench (length (ack4 3 8000))) > 0.018 sec > -> 2410 > > and even on my humble Netbook with a slow Atom CPU (pil32): > > : (bench (length (ack4 3 8000))) > 0.213 sec > -> 2410 > > ♪♫ Alex > > > Side note (though this doesn't really matter for the speed): It is never > wise to use 'length' to detect short lists. Better replace > > (if (=0 (length R)) ..) with (if R ..) > > or > > (if (>= (length R) 3) ..) with (if (cddr R) ..) > > to avoid possibly counting along long lists. > -- > UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe >