Hi,
I have started programming lisp... yesterday :)
I got ackerman to work and this is my implimentation.
(defun ackerman (x y)
(cond
((< x 0) "Error: X too small")
((< y 0) "Error: Y too small")
((= x 0) (+ y 1))
((= y 0) (ackerman (- x 1) 1))
(t (ackerman (- x 1) (ackerman x (- y 1))))
)
)
it works (As far as I can test it) but for (ackerman 4 4) give the
following:
---<lisp output>---
[7]> (ackerman 4 4)
*** - Program stack overflow. RESET
---</lisp output>---
I am using clisp on Windows 2000. I start clisp with "-m 80MB". Is
there another way I can set up the stack to be bigger?
Regards
Pieter
From: Joe Marshall
Subject: Re: stack overflow for ackerman
Date:
Message-ID: <brp418ud.fsf@comcast.net>
·······@lynxgeo.com (Pieter) writes:
> Hi,
>
> I have started programming lisp... yesterday :)
>
> I got ackerman to work and this is my implimentation.
>
> (defun ackerman (x y)
> (cond
> ((< x 0) "Error: X too small")
> ((< y 0) "Error: Y too small")
> ((= x 0) (+ y 1))
> ((= y 0) (ackerman (- x 1) 1))
> (t (ackerman (- x 1) (ackerman x (- y 1))))
> )
> )
>
> it works (As far as I can test it) but for (ackerman 4 4) give the
> following:
> ---<lisp output>---
> [7]> (ackerman 4 4)
>
> *** - Program stack overflow. RESET
> ---</lisp output>---
>
> I am using clisp on Windows 2000. I start clisp with "-m 80MB". Is
> there another way I can set up the stack to be bigger?
Have you estimated the depth of stack needed?
--
~jrm
Joe Marshall <·············@comcast.net> wrote in message news:<············@comcast.net>...
> Have you estimated the depth of stack needed?
I am not completely sure that I understand what you are asking. :( I
know that (ackerman 4 4)'s answer is HUGE and that the stack must be
VERY big. I know this because of other implimentations though.
Pieter
From: Joe Marshall
Subject: Re: stack overflow for ackerman
Date:
Message-ID: <65fbopyu.fsf@ccs.neu.edu>
·······@lynxgeo.com (Pieter) writes:
> Joe Marshall <·············@comcast.net> wrote in message news:<············@comcast.net>...
>
>> Have you estimated the depth of stack needed?
>
> I am not completely sure that I understand what you are asking. :( I
> know that (ackerman 4 4)'s answer is HUGE and that the stack must be
> VERY big. I know this because of other implimentations though.
I'm just asking if you have an idea of exactly how big ``VERY big''
is. I think you have underestimated it.
Joe Marshall <···@ccs.neu.edu> writes:
> I'm just asking if you have an idea of exactly how big ``VERY big''
> is. I think you have underestimated it.
in case the OP doesn't know about this resource: you can find A(4,4)
at the Online Encyclopedia of Integer Sequences:
http://www.research.att.com/~njas/sequences/
see sequence number A046859.
--
Chris Jeris ······@oinvzer.net Apply (1 6 2 4)(3 7) to domain to reply.
Joe Marshall <···@ccs.neu.edu> writes:
> ·······@lynxgeo.com (Pieter) writes:
>
> > Joe Marshall <·············@comcast.net> wrote in message news:<············@comcast.net>...
> >
> >> Have you estimated the depth of stack needed?
> >
> > I am not completely sure that I understand what you are asking. :( I
> > know that (ackerman 4 4)'s answer is HUGE and that the stack must be
> > VERY big. I know this because of other implimentations though.
>
> I'm just asking if you have an idea of exactly how big ``VERY big''
> is. I think you have underestimated it.
Isn't the Ackerman function one of those things that to estimate the
stack used by its computation you need to estimate the result?
Cheers,
mwh
--
Exam invigilation - it doesn't come much harder than that, esp if
the book you're reading turns out to be worse than expected.
-- Dirk Bruere, sci.physics.research
From: Joe Marshall
Subject: Re: stack overflow for ackerman
Date:
Message-ID: <3cac8clu.fsf@comcast.net>
Michael Hudson <···@python.net> writes:
> Joe Marshall <···@ccs.neu.edu> writes:
>
>> ·······@lynxgeo.com (Pieter) writes:
>>
>> > Joe Marshall <·············@comcast.net> wrote in message news:<············@comcast.net>...
>> >
>> >> Have you estimated the depth of stack needed?
>> >
>> > I am not completely sure that I understand what you are asking. :( I
>> > know that (ackerman 4 4)'s answer is HUGE and that the stack must be
>> > VERY big. I know this because of other implimentations though.
>>
>> I'm just asking if you have an idea of exactly how big ``VERY big''
>> is. I think you have underestimated it.
>
> Isn't the Ackerman function one of those things that to estimate the
> stack used by its computation you need to estimate the result?
One shouldn't be afraid of recursion, especially when considering
Ackermann's function.
You can estimate the stack necessary for the single call to
(ackermann 4 4) without running the program.
--
~jrm
·······@lynxgeo.com (Pieter) wrote in message news:<····························@posting.google.com>...
> Joe Marshall <·············@comcast.net> wrote in message news:<············@comcast.net>...
>
> > Have you estimated the depth of stack needed?
>
> I am not completely sure that I understand what you are asking. :( I
> know that (ackerman 4 4)'s answer is HUGE and that the stack must be
> VERY big. I know this because of other implimentations though.
What makes you think that bignum integers are stored on the stack?
They are usually represented as references to heap-allocated bit
strings. The stack frame contains just these references, not the bit
strings themselves. The references are tiny scalar quantities that
typically fit in a machine register: 32 bits or maybe 64 these days.
Kaz Kylheku wrote:
> ·······@lynxgeo.com (Pieter) wrote in message news:<····························@posting.google.com>...
> > Joe Marshall <·············@comcast.net> wrote in message news:<············@comcast.net>...
> >
> > > Have you estimated the depth of stack needed?
> >
> > I am not completely sure that I understand what you are asking. :( I
> > know that (ackerman 4 4)'s answer is HUGE and that the stack must be
> > VERY big. I know this because of other implimentations though.
>
> What makes you think that bignum integers are stored on the stack?
What makes you think he thinks that bignum integers are stored
on the stack?
--
Gareth McCaughan
.sig under construc
·······@lynxgeo.com (Pieter) wrote in message news:<····························@posting.google.com>...
> it works (As far as I can test it) but for (ackerman 4 4) give the
> following:
> ---<lisp output>---
> [7]> (ackerman 4 4)
> *** - Program stack overflow. RESET
> ---</lisp output>---
Do you have any idea how big this number is, by the way? What exactly
do you expect to happen?
> I am using clisp on Windows 2000. I start clisp with "-m 80MB". Is
> there another way I can set up the stack to be bigger?
Do you really think that the stack depth is all that stands in your
way? The value you are trying to compute involves numbers like
65536
2
2
have you tried evaluating (expt 2 (expt 2 65536))? On the same Lisp
implementation that you are using, I get:
*** overflow during multiplication of large numbers
Skill testing question: in the straightforward binary representation,
how many bits of storage would the number (expt 2 (expt 2 65536))
require?
Also, there are two N's in Ackermann, by the way.
For more than you ever wanted to know about large numbers see the chain of
pages beginning with:
http://home.earthlink.net/~mrob/pub/math/largenum.html
and in particular:
http://home.earthlink.net/~mrob/pub/math/largenum-3.html
Page 2 is interesting too.
Oh, there's also this:
http://home.earthlink.net/~mrob/pub/perl/hypercalc.txt
It would be interesting to translate hypercalc into Lisp for comparison.
E.
In article <····························@posting.google.com>,
···@ashi.footprints.net (Kaz Kylheku) wrote:
> ·······@lynxgeo.com (Pieter) wrote in message
news:<····························@posting.google.com>...
>
> > it works (As far as I can test it) but for (ackerman 4 4) give the
> > following:
> > ---<lisp output>---
> > [7]> (ackerman 4 4)
> > *** - Program stack overflow. RESET
> > ---</lisp output>---
>
> Do you have any idea how big this number is, by the way? What exactly
> do you expect to happen?
>
> > I am using clisp on Windows 2000. I start clisp with "-m 80MB". Is
> > there another way I can set up the stack to be bigger?
>
> Do you really think that the stack depth is all that stands in your
> way? The value you are trying to compute involves numbers like
>
> 65536
> 2
> 2
>
> have you tried evaluating (expt 2 (expt 2 65536))? On the same Lisp
> implementation that you are using, I get:
>
> *** overflow during multiplication of large numbers
>
> Skill testing question: in the straightforward binary representation,
> how many bits of storage would the number (expt 2 (expt 2 65536))
> require?
>
> Also, there are two N's in Ackermann, by the way.
> Do you have any idea how big this number is, by the way? What exactly
> do you expect to happen?
More manners to start with...
In my mind I was testing the suitability for doing cryptographic (RSA)
programming with Lisp. I haven't worked with lisp before but I heard
about this feature called "bignum"'s i thought RSA might be easier in
it than in something like C. I thought using AckermanN (which is easy
enough to program in a new/unfamiliar language) would give a big
enough number to test this with. If it can handle ackermann then
Cryptography would be peanuts.
> Do you really think that the stack depth is all that stands in your
> way? The value you are trying to compute involves numbers like
>
> 65536
> 2
> 2
>
> have you tried evaluating (expt 2 (expt 2 65536))? On the same Lisp
> implementation that you are using, I get:
>
> *** overflow during multiplication of large numbers
> Skill testing question: in the straightforward binary representation,
> how many bits of storage would the number (expt 2 (expt 2 65536))
> require?
>
> Also, there are two N's in Ackermann, by the way.
back-of-the-envelope like: 3.1859808040601742833346296624825e+3946
I really see the point that you are making. I am not being difficult,
maybe uninformed.
Is it now required of me to impliment a /proper/ bignum package
(similar to the one which the GNU people implimented for C/C++ and is
used in GPG). And; How would I go about it?
Trying to use the result of (ackermann 4 4) IS NOT bright. Afterwards
I thought of testing it with some published prime numbers. (I think
they were in the order of 200 decimal digits) doing an exponent of two
of them:
(mod
(expt <200digits> <200digits>)
<200digits>
)
also gave me an overflow... I KNOW this number is (very) big too.
Would I then have to impliment a loop that does a multiplication, then
a mod, then a multiplication and then a mod (for RSA) to get the
factor of the two primes?
What I thought after hearing about bignums is that I can just about
chuck anything at it, and the Lisp interpreter (or compiler or
whatever) would handle this bignum on its own. Is this not so?
However. Thank you for your response which was quite informative.
Regards
Pieter
From: Tim Bradshaw
Subject: Re: stack overflow for ackerman
Date:
Message-ID: <ey3zncbnbfp.fsf@cley.com>
* Pieter wrote:
>> 65536
>> 2
>> 2
> Is it now required of me to impliment a /proper/ bignum package
> (similar to the one which the GNU people implimented for C/C++ and is
> used in GPG). And; How would I go about it?
I think you haven't realised what this number means: you don't have
enough memory to represent it exactly.
In article <···············@cley.com>, Tim Bradshaw <···@cley.com> wrote:
> * Pieter wrote:
>
> >> 65536
> >> 2
> >> 2
>
> > Is it now required of me to impliment a /proper/ bignum package
> > (similar to the one which the GNU people implimented for C/C++ and is
> > used in GPG). And; How would I go about it?
>
> I think you haven't realised what this number means: you don't have
> enough memory to represent it exactly.
Of course you do, you just have to use a representation different from the
usual one. (In fact, that number is represented exactly in this very
post, and without knowing what kind of machine you're using to read this I
venture to say that this post is not coming anywhere close to exhausting
your available memory.)
See http://home.earthlink.net/~mrob/pub/perl/hypercalc.txt for an actual
implementation of a representation that can handle numbers vastly larger
than the one above.
E.
From: Tim Bradshaw
Subject: Re: stack overflow for ackerman
Date:
Message-ID: <ey365ez8xcq.fsf@cley.com>
* Erann Gat wrote:
> Of course you do, you just have to use a representation different from the
> usual one.
Damn! I was going to add a caveat like that, I should have known I'd
need to (:-). I think what I
need is some kind of careful statement which comes down to `you don't
have enough memory to represent it exactly assuming you use some
obvious representation which is likely to be efficient for general
machine calculation and has been discovered and also no one is allowed
to disagree'.
> (In fact, that number is represented exactly in this very
> post, and without knowing what kind of machine you're using to read this I
> venture to say that this post is not coming anywhere close to exhausting
> your available memory.)
Now come on, surely you know I read news on a dodgy z80 connected via an
acoustic coupler at 1200/75. It doesn't take much to exhau$%^&*((((((((((((9(
NO CARRIER
·········@jpl.nasa.gov (Erann Gat) writes:
> In article <···············@cley.com>, Tim Bradshaw <···@cley.com> wrote:
>
> > * Pieter wrote:
> >
> > >> 65536
> > >> 2
> > >> 2
> >
> > > Is it now required of me to impliment a /proper/ bignum package
> > > (similar to the one which the GNU people implimented for C/C++ and is
> > > used in GPG). And; How would I go about it?
> >
> > I think you haven't realised what this number means: you don't have
> > enough memory to represent it exactly.
>
> Of course you do, you just have to use a representation different from the
> usual one. (In fact, that number is represented exactly in this very
> post, and without knowing what kind of machine you're using to read this I
> venture to say that this post is not coming anywhere close to exhausting
> your available memory.)
>
> See http://home.earthlink.net/~mrob/pub/perl/hypercalc.txt for an actual
> implementation of a representation that can handle numbers vastly larger
> than the one above.
Wow, that's cool, but ... is anyone else disturbed by the fact that
this was implemented in a language where it's legal to add 12 to
"bannanas"?
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Hi Thomas F. Burdick,
>> See http://home.earthlink.net/~mrob/pub/perl/hypercalc.txt for an actual
>> implementation of a representation that can handle numbers vastly larger
>> than the one above.
>
> Wow, that's cool, but ... is anyone else disturbed by the fact that
> this was implemented in a language where it's legal to add 12 to
> "bannanas"?
I'm still disturbed by the fact that it's legal to add 12 hours to 12
metres in all our languages!
Have fun,
Adam
* Adam Warner
| I'm still disturbed by the fact that it's legal to add 12 hours to 12
| metres in all our languages!
So 12 p.m. really means �12 per meter�? Yay, I can make sense of the
Imperial ways, yet.
--
Erik Naggum | Oslo, Norway 2004-026
Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
Erik Naggum <····@naggum.no> wrote in message news:<·······················@naggum.no>...
> * Adam Warner
> | I'm still disturbed by the fact that it's legal to add 12 hours to 12
> | metres in all our languages!
>
> So 12 p.m. really means �12 per meter�? Yay, I can make sense of the
> Imperial ways, yet.
As you mentioned in another thread, understanding the historic context of
(in that thread) the code is important (and can take a lot of time).
And so it is I think with Imperial measurements. Yes, they're lossage for
many things when compared to metric. But there are reasons for the way
they are (and I'm not saying the reasons are necessarily good ones!)
;-)
-Duncan
Adam Warner <······@consulting.net.nz> writes:
> Hi Thomas F. Burdick,
> >
> > Wow, that's cool, but ... is anyone else disturbed by the fact that
> > this was implemented in a language where it's legal to add 12 to
> > "bannanas"?
>
> I'm still disturbed by the fact that it's legal to add 12 hours to 12
> metres in all our languages!
It ain't "legal"[*] in my language:
[1]> (defgeneric add (a b))
#<GENERIC-FUNCTION ADD>
[2]> (defclass hours () ((n :initarg :n)))
#<STANDARD-CLASS HOURS>
[3]> (defclass metres () ((n :initarg :n)))
#<STANDARD-CLASS METRES>
[4]> (add (make-instance 'hours :n 12) (make-instance 'metres :n 12))
*** - NO-APPLICABLE-METHOD: When calling #<GENERIC-FUNCTION ADD> with arguments (#<HOURS #x203088A1> #<METRES #x2030A7CD>), no method is applicable.
1. Break [5]>
[*] Unless I decide that it should be, of course.
Adam Warner <······@consulting.net.nz> wrote:
> I'm still disturbed by the fact that it's legal to add 12 hours to 12
> metres in all our languages!
I've written a library that can check for these kinds of 'unit errors'.
This has helped me a lot with implementing and verifying physics and
biology formulas.
Here's a small sample session with your example:
;; You can't add hours and meters.
UNITS 19 > (+ (quantity 12 'hour) (quantity 12 'meter))
Error: Unit mismatch between 43200 sec and 12 m.
1 (abort) Return to level 0.
2 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
UNITS 20 : 1 > :c 2
;; Multiplying hours and meters is no problem.
UNITS 21 > (* (quantity 12 'hour) (quantity 12 'meter))
518400 m sec
Here's a slightly more complicated session:
UNITS 16 > (defconstant +gas-constant+
(quantity 8.315 '(joule (mole -1) (kelvin -1))))
+GAS-CONSTANT+
UNITS 17 > (defun gas-pressure (gas-density temperature molecular-weight)
(check-units gas-density '(kg (m -3)))
(check-units temperature 'kelvin)
(check-units molecular-weight '(kg (mole -1)))
(check-units (/ (* gas-density +gas-constant+ temperature)
molecular-weight)
'pascal))
GAS-PRESSURE
UNITS 18 > (gas-pressure (quantity 2 '(kg (meter -3)))
(quantity 295 'kelvin)
(quantity 32 '(gram (mole -1))))
153307.81249999997 kg m-1 sec-2
UNITS 19 > (gas-pressure (quantity 2 '(kg (meter -1)))
(quantity 295 'kelvin)
(quantity 32 '(gram (mole -1))))
Error: The quantity 2 kg m-1 should have units (KG (M -3)).
1 (abort) Return to level 0.
2 Return to top loop level 0.
--
Arthur Lemmens
From: Joe Marshall
Subject: Re: stack overflow for ackerman
Date:
Message-ID: <k73fopzm.fsf@comcast.net>
·······@lynxgeo.com (Pieter) writes:
> In my mind I was testing the suitability for doing cryptographic (RSA)
> programming with Lisp. I haven't worked with lisp before but I heard
> about this feature called "bignum"'s I thought RSA might be easier in
> it than in something like C. I thought using AckermanN (which is easy
> enough to program in a new/unfamiliar language) would give a big
> enough number to test this with. If it can handle ackermann then
> Cryptography would be peanuts.
It definitely would.
The reason I was cryptic before is twofold: Ackermann's function is
often used in homework problems or in employment tests.
(See http://www.itasoftware.com/careers/programmers-archive.php)
The second reason is that figuring out (Ack 4 4) involves a lot of
interesting thinking. I got a kick out of it and I didn't want to
spoil it. (Gee, this is big...really big...DAMN!)
> back-of-the-envelope like: 3.1859808040601742833346296624825e+3946
Where did you get *that* envelope?
Actually, I think your estimate is a little low. The log of (ack 4 4)
has about 39400 digits.
> Is it now required of me to impliment a /proper/ bignum package
> (similar to the one which the GNU people implimented for C/C++ and is
> used in GPG). And; How would I go about it?
Lisp has a proper bignum package.
> Trying to use the result of (ackermann 4 4) IS NOT bright. Afterwards
> I thought of testing it with some published prime numbers. (I think
> they were in the order of 200 decimal digits) doing an exponent of two
> of them:
>
> (mod
> (expt <200digits> <200digits>)
> <200digits>
> )
>
> also gave me an overflow... I KNOW this number is (very) big too.
You got an overflow because (expt <200 digits> <200 digits>) won't fit
in the machine even though
(mod (expt <200 digits> <200 digits>) <200 digits>) will.
If you compute it like this, though:
(defun expmod (base exponent mod)
(cond ((zerop exponent) 1)
((evenp exponent) (mod (let ((x (expmod base (/ exponent 2) mod)))
(* x x))
mod))
(t (mod (* base (expmod base (1- exponent) mod))
mod))))
You'll have no problems.
(expmod 640785284696442065785559134003308932264708355179002798538113
671286301850793527622248679786362012411973295201562077406347
541607700526106309999871171548445806906603126622271198261079)
=> 184927654951560197998922671105024055618160643054333015564836
--
~jrm
Joe Marshall <·············@comcast.net> writes:
> ·······@lynxgeo.com (Pieter) writes:
>
>> Trying to use the result of (ackermann 4 4) IS NOT bright. Afterwards
>> I thought of testing it with some published prime numbers. (I think
>> they were in the order of 200 decimal digits) doing an exponent of two
>> of them:
>>
>> (mod
>> (expt <200digits> <200digits>)
>> <200digits>
>> )
>>
>> also gave me an overflow... I KNOW this number is (very) big too.
>
> You got an overflow because (expt <200 digits> <200 digits>) won't fit
> in the machine even though
> (mod (expt <200 digits> <200 digits>) <200 digits>) will.
>
> If you compute it like this, though [... elided ...]
So as a quality of implementation issue, might it not be argued that
it would be good if implementations recognized the
(mod (expt ...) ...)
idiom, and compiled it to code that only overflows if it needs to?
Christophe
--
http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)
From: Joe Marshall
Subject: Re: stack overflow for ackerman
Date:
Message-ID: <7jzfom81.fsf@comcast.net>
Christophe Rhodes <·····@cam.ac.uk> writes:
> So as a quality of implementation issue, might it not be argued that
> it would be good if implementations recognized the
> (mod (expt ...) ...)
> idiom, and compiled it to code that only overflows if it needs to?
It *might* be, but that seems to me to be a rather `ad-hoc'
optimization. You only run into that pattern when doing number
theoretical stuff like RSA.
--
~jrm