I implemented Ackerman's function in LISP.
There seems to be a couple of variations. This is the one defined as:
Acker(m,n) = n1+ if m=0
Acker(m-1,1) if m>0 and n=0
Acker(m-1,Acker(m,n-1)) if m>0 and n > 0
Anyway, I can get my C and Java based versions to run values like Acker 3 7 or even 3 11 quite easily.
My self-built CLISP, says the newbie, seems to run out of stack arond Acker 3 6. I know the LISP code is at least accurate, because it gets the right
answer until it dies with stack problems. The LISP implementation (I have it at home) is about as crushingly simple as you could get -- ordinary
recursive function with minimal "IF" type logic. My C and Java ones are much more elaborate (e.g. instrumentation, etc.).
Is there some simple setting I have wrong, either at build or run time? This is clearly not a performance issue per se, but rather a space issue.
Larry
Larry Loen <······@rchland.vnet.ibm.com> writes:
> Is there some simple setting I have wrong, either at build or run time?
> This is clearly not a performance issue per se, but rather a space issue.
Did you compile your function?
On a laptop with Celeron 550 and 192M of RAM here, (ackermann 3 11) took
150+ sec in CLISP, and 20+ sec in CMU Common Lisp (18c+).
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun ackermann (m n)
(declare (fixnum m n) (optimize (speed 3) (safety 0)))
(cond
((zerop m) (1+ n))
((zerop n) (ackermann (1- m) 1))
(t (ackermann (1- m) (ackermann m (1- n))))))
(time (ackermann 3 11))
;;; - huaiyuan
No, I didn't realize it affected stack capacity as well as speed.
When I did a naive compile, I immediately ran (acker 3 8) which hadn't run before. And, that was without your obvious-to-this-newbie improvments
below.
Huaiyuan wrote:
> Larry Loen <······@rchland.vnet.ibm.com> writes:
>
> > Is there some simple setting I have wrong, either at build or run time?
> > This is clearly not a performance issue per se, but rather a space issue.
>
> Did you compile your function?
>
> On a laptop with Celeron 550 and 192M of RAM here, (ackermann 3 11) took
> 150+ sec in CLISP, and 20+ sec in CMU Common Lisp (18c+).
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> (defun ackermann (m n)
> (declare (fixnum m n) (optimize (speed 3) (safety 0)))
> (cond
> ((zerop m) (1+ n))
> ((zerop n) (ackermann (1- m) 1))
> (t (ackermann (1- m) (ackermann m (1- n))))))
>
> (time (ackermann 3 11))
>
> ;;; - huaiyuan
A quick-and-diry experiment shows that the thing that makes Huaiyuan's code sing (nearly twice as fast as mine) is the use of cond rather than the
naive "if" clauses I was using. Instructive for such a simple case!
Also instructive is that compile bought back all the value in terms of increasing the effectively available stack. In terms of calculating larger
values of Ackermann's function, it was all about compiling; cond was faster but not "deeper" if you get my drift.
Larry Loen wrote:
> No, I didn't realize it affected stack capacity as well as speed.
>
> When I did a naive compile, I immediately ran (acker 3 8) which hadn't run before. And, that was without your obvious-to-this-newbie improvments
> below.
>
> Huaiyuan wrote:
>
> > Larry Loen <······@rchland.vnet.ibm.com> writes:
> >
> > > Is there some simple setting I have wrong, either at build or run time?
> > > This is clearly not a performance issue per se, but rather a space issue.
> >
> > Did you compile your function?
> >
> > On a laptop with Celeron 550 and 192M of RAM here, (ackermann 3 11) took
> > 150+ sec in CLISP, and 20+ sec in CMU Common Lisp (18c+).
> >
> > ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> > (defun ackermann (m n)
> > (declare (fixnum m n) (optimize (speed 3) (safety 0)))
> > (cond
> > ((zerop m) (1+ n))
> > ((zerop n) (ackermann (1- m) 1))
> > (t (ackermann (1- m) (ackermann m (1- n))))))
> >
> > (time (ackermann 3 11))
> >
> > ;;; - huaiyuan
Larry
In article <·················@rchland.vnet.ibm.com>,
Larry Loen <······@rchland.vnet.ibm.com> wrote:
>A quick-and-diry experiment shows that the thing that makes Huaiyuan's
>code sing (nearly twice as fast as mine) is the use of cond rather than
>the
>naive "if" clauses I was using. Instructive for such a simple case!
I don't think that should make a significant difference in compiled code.
I would expect equivalent COND and IF expressions to compile to almost
identical code. In fact, it's likely that one is defined as a macro that
expands into the other. In the interpreter it makes a difference because
it expands the macro each time it executes it (although the interpreter is
permitted to pre-expand macros, most don't).
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Larry Loen <······@rchland.vnet.ibm.com> writes:
> No, I didn't realize it affected stack capacity as well as speed.
Wow.
There's a misperception we as a community should work harder to make sure
does not happen...
Kent M Pitman <······@world.std.com> writes:
> There's a misperception we as a community should work harder to make sure
> does not happen...
Maybe it would be good for the community if all lisps had (by default)
a "compiling evaluator" like MCL has...
--
(espen)
Espen Vestre <·····@*do-not-spam-me*.vestre.net> writes:
> Kent M Pitman <······@world.std.com> writes:
>
> > There's a misperception we as a community should work harder to make sure
> > does not happen...
>
> Maybe it would be good for the community if all lisps had (by default)
> a "compiling evaluator" like MCL has...
Uh, not that I have a problem with MCL doing this, but from a conceptual
standpoint, that would perpetuate the confusion. The MCL thing is NOT
an intepreter.
Kent M Pitman <······@world.std.com> writes:
> Uh, not that I have a problem with MCL doing this, but from a conceptual
> standpoint, that would perpetuate the confusion. The MCL thing is NOT
> an intepreter.
But then you could respond: "Lisp interpreter? Which lisp interpreter?"
every time you get those boring statements about "lisp is an interpreted
language" ;-)
--
(espen)
In article <··············@wallace.ws.nextra.no>,
Espen Vestre <·····@*do-not-spam-me*.vestre.net> wrote:
>Kent M Pitman <······@world.std.com> writes:
>> Uh, not that I have a problem with MCL doing this, but from a conceptual
>> standpoint, that would perpetuate the confusion. The MCL thing is NOT
>> an intepreter.
>But then you could respond: "Lisp interpreter? Which lisp interpreter?"
>every time you get those boring statements about "lisp is an interpreted
>language" ;-)
MCL actually does have an interpreter. It's just that the interpreter
doesn't have much to do unless you set *COMPILE-DEFINITIONS* to NIL.
--
Dave Seaman ·······@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://www.amnestyusa.org/abolish/reports/mumia/>
Kent M Pitman wrote:
> Larry Loen <······@rchland.vnet.ibm.com> writes:
>
> > No, I didn't realize it affected stack capacity as well as speed.
>
> Wow.
>
> There's a misperception we as a community should work harder to make sure
> does not happen...
You can start by telling me how it is wrong.
When I run it under CLISP, it dies at a around (Acker 3 6) uncompiled and runs to at least (Acker 3 10) compiled.
This is the same program (my version).
This isn't a speed question -- it is a "how much room will it take before exhausing storage" question. Or, if it isn't, how is it not?
Now, if you're talking about correctly discussing bytecodes versus some sort of interpretation or whatever, then I am a little less interested, though
I suppose I should pay attention to that as well.
But, whatever (compile 'x) does, it does seem to increase the available stack and/or heap space on at least one occassion!
Larry
"Larry Loen" <······@rchland.vnet.ibm.com> wrote in message ······················@rchland.vnet.ibm.com...
> Kent M Pitman wrote:
>
> > Larry Loen <······@rchland.vnet.ibm.com> writes:
> >
> > > No, I didn't realize it affected stack capacity as well as speed.
> >
> > Wow.
> >
> > There's a misperception we as a community should work harder to make sure
> > does not happen...
>
> You can start by telling me how it is wrong.
>
> When I run it under CLISP, it dies at a around (Acker 3 6) uncompiled and runs to at least (Acker 3 10) compiled.
>
> This is the same program (my version).
>
> This isn't a speed question -- it is a "how much room will it take before exhausing storage" question. Or, if it isn't, how is it
not?
>
> Now, if you're talking about correctly discussing bytecodes versus some sort of interpretation or whatever, then I am a little
less interested, though
> I suppose I should pay attention to that as well.
>
> But, whatever (compile 'x) does, it does seem to increase the available stack and/or heap space on at least one occassion!
>
>
To make very short work of this, the interpreter uses the stack to keep track
of what it's doing as well. Since it's not doing the dog work with a compiled
function, less stack gets used, more space is available for the function.
It seems to me that one of the great strengths of Lisp, interaction with the
listener in an interpretive phase, is also such a pitfall for people.
Mock conversation:
"Lisp is slower and didn't get as far as language X."
"Did you compile it?"
"Say what?"
*SIGH* (much nashing of teeth)
Cheers,
Geoff
In article <·················@rchland.vnet.ibm.com>,
Larry Loen <······@rchland.vnet.ibm.com> wrote:
>But, whatever (compile 'x) does, it does seem to increase the available
>stack and/or heap space on at least one occassion!
When the interpreter is used, stack frames are used by the interpreter
itself, which reduces the stack space available to the application.
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
On Tue, 12 Jun 2001 19:17:30 -0500, Larry Loen
<······@rchland.vnet.ibm.com> wrote:
acker 3 11 works fine for me in corman lisp:
(defun ackermann (m n)
(declare (fixnum m n) )
(cond
((zerop m) (1+ n))
((zerop n) (ackermann (1- m) 1))
(t (ackermann (1- m) (ackermann m (1- n))))))
ACKERMANN
( ackermann 3 11)
16381
From: Sam Steingold
Subject: Re: Ackermans' function in LISP dies early
Date:
Message-ID: <u3d94l8h0.fsf@xchange.com>
> * In message <·················@rchland.vnet.ibm.com>
> * On the subject of "Ackermans' function in LISP dies early"
> * Sent on Tue, 12 Jun 2001 19:17:30 -0500
> * Honorable Larry Loen <······@rchland.vnet.ibm.com> writes:
>
> Acker(m,n) = n1+ if m=0
> Acker(m-1,1) if m>0 and n=0
> Acker(m-1,Acker(m,n-1)) if m>0 and n > 0
>
> Anyway, I can get my C and Java based versions to run values like
> Acker 3 7 or even 3 11 quite easily.
not a big deal:
A(3,x) = 2^(x+3)-3 = (- (expt 2 (+ x 3)) 3) = (- (ash 1 (+ x 3)) 3)
:-)
> Is there some simple setting I have wrong, either at build or run
> time?
1. compile your function (this affects both execution speed and stack
use).
2. increase stack space (ulimit on Unix, editbin on win32)
3. use memoization and/or formulas for A(1,x), A(2,x) and A(3,x) (this
is probably cheating :-)
(defun ackermann (m n)
(declare (fixnum m n) (optimize (speed 3) (safety 0)))
(let ((memo (make-hash-table :test #'equal))
(ncal 0) (nhit 0))
(labels ((ack (aa bb)
(incf ncal)
(cond ((zerop aa) (1+ bb))
((= 1 aa) (+ 2 bb))
((= 2 aa) (+ 3 (* 2 bb)))
((= 3 aa) (- (ash 1 (+ 3 bb)) 3))
((let* ((key (cons aa bb))
(val (gethash key memo)))
(cond (val (incf nhit) val)
(t (setq val (if (zerop bb)
(ack (1- aa) 1)
(ack (1- aa) (ack aa (1- bb)))))
(setf (gethash key memo) val)
val)))))))
(let ((ret (ack m n)))
(format t "A(~d,~d)=~:d (~:d calls, ~:d cache hits)~%"
m n ret ncal nhit)
(values ret memo)))))
this will compute up to A(4,2).
I don't think there are A(4,3) particles in the Universe.
--
Sam Steingold (http://www.podval.org/~sds)
Just because you're paranoid doesn't mean they AREN'T after you.