Re: side-note
(bench (length (ack4 3 8000))) (32-bit Cygwin)
0.070 sec
(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 <[email protected]>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:[email protected]?subject=Unsubscribe
>