[Q]: Recursion help
Dirt
I have to write a recursive function which calculates a number to
an exponent such as (ex 2 3 ). (answer 8 ) I am only allowed to use
the lisp multiplication function. I started to write this, code below
(yes it doesnt work) but before I fix my code. Is this possible to do
without using the Lisp minus function as well?
Thanks,
Dirt
( defun ex ( b e )
( cond
( ( eq b 0 ) 0 ) ; Base is 0 all done
( ( eq e 0 ) 1 ) ; Answer is 1
( ( eq b 1 ) b ) ; All done
( ( eq e 1 ) b ) ; All done
( ( ex ( * b b ) ( - e 1 ) ) )
( t nil )
)
)
Dirt
I think I have my code corrected;
( defun ex ( b e )
( cond
( ( eq b 0 ) 0 ) ; Base is 0 all done
( ( eq e 0 ) 1 ) ; Answer is 1
( ( eq b 1 ) b ) ; All done
( ( eq e 1 ) b ) ; All done
( t ( * b ( ex b ( - e 1 ) ) ) ) ; Call again
( t nil )
)
)
However, as instructed in my homework, I am to do this only by using
the LISP multiplication function and recursion. In my code, I use the
minus function. I can't think of a way to do this without using minus
to keep track of the current iteration. Can this be done as requested?
Thanks,
Dirt
On Sat, 22 Jan 2000 00:33:01 GMT, Barry Margolin
<bar...@bbnplanet.com> wrote:
>In article <u4th8sodb1o55fmcq...@4ax.com>,
>Dirt <pi...@inam3.com> wrote:
>>Hiya,
>> I have to write a recursive function which calculates a number to
>>an exponent such as (ex 2 3 ). (answer 8 ) I am only allowed to use
>>the lisp multiplication function. I started to write this, code below
>>(yes it doesnt work) but before I fix my code. Is this possible to do
>>without using the Lisp minus function as well?
>
>You have two problems:
>
>1) The recursive clause of the cond should be the "t" clause.
>
>2) You have a math error: ex(b, e) = b*ex(b, e-1), not ex(b*b, e-1)
Robert Monfera
Hi Dirt,
Here is a quote from the Hyperspec. If you find where it is (besides my
hard drive), you'll find references to things you may want to consider.
"An implementation is permitted to make 'copies' of characters and
numbers at any time. The effect is that Common Lisp makes no guarantee
that eq is true even when both its arguments are 'the same thing' if
that thing is a character or number."
Here's how it looks like with common Lisp spacing:
(defun ex (base exponent)
(cond ((eq base 0) 0)
((eq exponent 0) 1)
((eq base 1) base)
((eq exponent 1) base)
(t (* base (ex base (- exponent 1))))
(t nil)))
This is only formatting and naming - I haven't changed functions. Other
than these, isn't the last T condition redundant?
Also, I guess the assignment specifies it is only supposed to work with
positive integers as exponents - you could check it and signal an error
with this: (error "Exponent is not a positive integer.")
After these all, you can tell your teacher there is zero error in it :-)
Robert
Dirt
Yes, my mistake. The last t is redundant. I forgot to take it out as
it was part of a condition checking for valid numbers, however, it is
now assumed valid numbers are entered.
Dirt
On Fri, 21 Jan 2000 22:32:30 -0500, Robert Monfera <mon...@fisec.com>
wrote:
Barry Margolin
Dirt <pi...@inam3.com> wrote:
>Hiya,
> I have to write a recursive function which calculates a number to
>an exponent such as (ex 2 3 ). (answer 8 ) I am only allowed to use
>the lisp multiplication function. I started to write this, code below
>(yes it doesnt work) but before I fix my code. Is this possible to do
>without using the Lisp minus function as well?
You have two problems:
1) The recursive clause of the cond should be the "t" clause.
2) You have a math error: ex(b, e) = b*ex(b, e-1), not ex(b*b, e-1)
>
>Thanks,
> Dirt
>
>( defun ex ( b e )
>
> ( cond
>
> ( ( eq b 0 ) 0 ) ; Base is 0 all done
> ( ( eq e 0 ) 1 ) ; Answer is 1
> ( ( eq b 1 ) b ) ; All done
> ( ( eq e 1 ) b ) ; All done
> ( ( ex ( * b b ) ( - e 1 ) ) )
>
> ( t nil )
> )
>
>)
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, 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.
dauc...@hotmail.com
Dirt <pi...@inam3.com> wrote:
[snip your corrected code]
>
> However, as instructed in my homework, I am to do this only by using
> the LISP multiplication function and recursion. In my code, I use the
> minus function. I can't think of a way to do this without using minus
> to keep track of the current iteration. Can this be done as requested?
Dear Dirt, it's worse than you think: you're also using the cond and
eq functions. I think your answer is sufficient to the task (and the
instructions you were given were not correct). Turn it in and don't
worry about it, or, if you wish to stir up some stuff, us CL's loop
facility and teach your professor what's happened with Lisp in the last
15 or so years. Ask some questions about covariance and the Meta-
Object Protocol while you're at it.
<rant>
I hope this is an extra-credit/optional problem. I hate it when profs
say, "You can only use X, Y, and Z of the language." Doesn't the world
impose enough limits without us throwing some extra ones on top?
</rant>
Sincerely,
Douglas M. Auclair
Sent via Deja.com http://www.deja.com/
Before you buy.
Stig Hemmer
> Is this possible to do
> without using the Lisp minus function as well?
Well, there are two functions 1- and DECF that you could use, but I
doubt that is what you teacher had in mind.
What she was probably thinking was to count upwards using + instead of
downwards using -.
You will have to remember how far you should count by passing an extra
parameter to the recursive function. This means that your recursive
function cannot be EX, but some other function, e.g. EX-HELPER.
You should also take note of what Robert Montfera was saying about
comparing numbers using EQ. It will work perfectly well on most Lisp
implementations, but isn't _guaranteed_ to do so.
Numbers are best compared using the function =. (Common Lisp has many
different equality/equivalence testing functions. Often you can use
more than one. In this case, EQL, EQUAL and EQUALP would all have
worked, but = is still the predicate of choice for numbers)
Stig Hemmer,
Jack of a Few Trades.
Dirt
>You should also take note of what Robert Montfera was saying about
>comparing numbers using EQ. It will work perfectly well on most Lisp
>implementations, but isn't _guaranteed_ to do so.
Ok, Ill change it over to =.
>Numbers are best compared using the function =. (Common Lisp has many
>different equality/equivalence testing functions. Often you can use
>more than one. In this case, EQL, EQUAL and EQUALP would all have
>worked, but = is still the predicate of choice for numbers)
So, it is safe to recommend to my professor that we should be taught
to use '=' to compare numbers rather than 'eq'?
Thanks,
Dirt
Marco Antoniotti
Dirt <pi...@inam3.com> writes:
> >You should also take note of what Robert Montfera was saying about
> >comparing numbers using EQ. It will work perfectly well on most Lisp
> >implementations, but isn't _guaranteed_ to do so.
>
> Ok, Ill change it over to =.
On the other end EQL works for numbers of the same type.
> >Numbers are best compared using the function =. (Common Lisp has many
> >different equality/equivalence testing functions. Often you can use
> >more than one. In this case, EQL, EQUAL and EQUALP would all have
> >worked, but = is still the predicate of choice for numbers)
>
> So, it is safe to recommend to my professor that we should be taught
> to use '=' to compare numbers rather than 'eq'?
Yep. As you should be thought about FIRST and REST instead of CAR and
CDR.
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
Robert Monfera
Dirt wrote:
> [...] we should be taught
> to use '=' to compare numbers rather than 'eq'?
Yes. As Stig said, eq works on most implementations - provided both
numbers map into one 32-bit word. This is usually true for fixnums
(check most-positive-fixnum and most-negative-fixnum) and maybe other
32-bit data in an optimized setting. This is an accidental and
non-guaranteed side effect of eq working simply by comparing 2 32-bit
values (which are expected to be addresses), because two immediate
values (usually fixnums) that = will have the same bits.
Here's something to try for you with your implementation:
> (eq 7391827918273091 7391827918273091)
NIL
> (eq 2.0 2.0)
NIL
>
Robert
Dirt
>
>Here's something to try for you with your implementation:
>
>> (eq 7391827918273091 7391827918273091)
>NIL
>> (eq 2.0 2.0)
>NIL
>>
Yea, I tried that out and it didn't work just like you said. Thanks
for pointing this out to me guys.
Dirt
Tim Bradshaw
> So, it is safe to recommend to my professor that we should be taught
> to use '=' to compare numbers rather than 'eq'?
Yes! in fact EQ may not work for numbers:
(eq (expt 2 100) (expt 2 100)) -> nil
on all the implementations I've tried (Allegro, genera, gcl, clisp).
--tim
Janos Blazi
was that you must not use LISP's exponentiation as the problem is trivial
then.
J.B.
<dauc...@hotmail.com> schrieb in im Newsbeitrag:
86b9sm$5g3$1...@nnrp1.deja.com...
-----------== Posted via Newsfeeds.Com, Uncensored Usenet News ==----------
http://www.newsfeeds.com The Largest Usenet Servers in the World!
------== Over 73,000 Newsgroups - Including Dedicated Binaries Servers ==-----
Andreas Eder
a) you should reverse the first two clause in your cond
>( ( eq b 0 ) 0 ) ; Base is 0 all done
> ( ( eq e 0 ) 1 ) ; Answer is 1
( ( eq b 0 ) 0 ) ; Base is 0 all done
b) iinstead of counting down from n to 0 you could just count up
and thus avoid the minus
--
Wherever I lay my .emacs, thereć„€ my $HOME.
Dirt
>Two things:
>a) you should reverse the first two clause in your cond
> >( ( eq b 0 ) 0 ) ; Base is 0 all done
> > ( ( eq e 0 ) 1 ) ; Answer is 1
>to
> ( ( eq e 0 ) 1 ) ; Answer is 1
> ( ( eq b 0 ) 0 ) ; Base is 0 all done
>because 0^0 = 1 = (ex 0 0) as well.
>
>b) iinstead of counting down from n to 0 you could just count up
>and thus avoid the minus
Im sorry. This just isn't clicking. If I count up, wont I have to use
the '+' function then?
Andrew Cooke
Dirt <pi...@inam3.com> wrote:
> Hiya,
> I have to write a recursive function which calculates a number to
> an exponent such as (ex 2 3 ). (answer 8 ) I am only allowed to use
> the lisp multiplication function. I started to write this, code below
> without using the Lisp minus function as well?
Assuming that you can use other operators (just not exponentiation) (as
others on this thread have argued), there's probably a more efficient
(less multiplication - I have no idea what a sufficiently large value of
n is required for it to run more quickly) solution that I haven't seen
mentioned:
x^n = (x^n/2) * (x^n/2)
when n is even (and, of course, you only calculate x^n/2 once.
When n is odd you can reduce it to the even case by taking out a factor
of x.
Obviously, this assumes n is a positive integer (as you are doing
already).
Andrew
Erik Naggum
| So, it is safe to recommend to my professor that we should be taught
| to use '=' to compare numbers rather than 'eq'?
your professor should never teach EQ in the first place. EQ should be
discovered by good students on their own. novices should always use EQL
for typeless object comparison, and try not to think about EQ.
= signals an error for non-numbers. this is often a major pain. EQL
yields false if the objects are of different types. this can sometimes
be exactly what you want. = yields true for _numeric_ equality, which
can sometimes be very expensive to compute, but is often worth the cost,
except when you control the types of both objects and you would have to
be a real klutz to introduce that cost wantonly. therefore, EQL will
tell you about suboptimal programming practices if it yields false on two
numbers that appear "alike", and this fact alone will teach most students
better programming practices.
#:Erik
Erik Naggum
Tim Bradshaw
> In article <u4th8sodb1o55fmcq...@4ax.com>,
> x^n = (x^n/2) * (x^n/2)
And indeed this gives you a way of doing the calculation without using
- (or / or ODDP). You do need ASH, LOGBITP, and * though. Whether
that's the solution the person was looking for I don't know!
--tim
Dirt
our first assignment with LISP so I highly doubt that using
"ASH, LOGBITP, and *"
is the intended solution. ( I Hope not at least) Like others have
suggested in this thread, I think the point was to make it recursive
and NOT use the exponent function.
Dirt
Tim Bradshaw
> Ill let you guys know what my professor was thinking tomorrow. This is
> our first assignment with LISP so I highly doubt that using
> "ASH, LOGBITP, and *"
> is the intended solution. ( I Hope not at least) Like others have
> suggested in this thread, I think the point was to make it recursive
> and NOT use the exponent function.
For what it's worth, the too-clever solution is:
(defun x-to-the-n (x n)
(declare (type (integer 0) n)
(type number x))
(if (= n 1)
x
(let ((half (x-to-the-n x (ash n -1))))
(if (logbitp 0 n)
(* half half x)
(* half half)))))
Stig Hemmer
(defun ex (b e)
(apply #'* (make-list e :initial-element b)))
What this does is to make a list of e elements, each element being b.
Then it multiplies all these numbers together.
E.g. (ex 3 4) --> (apply #'* (3 3 3 3)) --> (* 3 3 3 3) --> 81
Note that (*) returns 1, so this code works for e=0.
#'* is short-hand for "the function *" as opposed to "the varable *".
Barry Margolin
Since it's not recursive, it clearly doesn't fit the parameters of the
homework assignment.
>(defun ex (b e)
> (apply #'* (make-list e :initial-element b)))
It would be better to use REDUCE than APPLY. Your solution may not work
when E > CALL-ARGUMENTS-LIMIT.
Dirt
previous post with my corrected function is acceptable. She just
didn't want us to use lisp's exponent function. That is excusable to
me, however, I am new to lisp and usually follow instructions to a T
when I am new to something. And this can lead to confusion in some
cases.
I also mentioned to my professor that using "eq" to compare two
numbers wasn't such a good idea. she admitted that she may have wrote
the incorrect thing on the board to me in private, however, she never
brought it up in class to note the correction that should be made = (
Thanks for all the help,
Dirt
On 24 Jan 2000 19:20:34 +0100, Stig Hemmer <st...@pvv.ntnu.no> wrote:
>Another "too clever" solution: [not recursive]
>
>(defun ex (b e)
> (apply #'* (make-list e :initial-element b)))
>
Robert Posey
Dirt wrote:
>
> <snip>
>
> >
> >Here's something to try for you with your implementation:
> >
> >> (eq 7391827918273091 7391827918273091)
> >NIL
> >> (eq 2.0 2.0)
> >NIL
> >>
>
> Yea, I tried that out and it didn't work just like you said. Thanks
> for pointing this out to me guys.
>
> Dirt
You might try and write a version of what I did to help me begin to
learn the difference between 'eq 'eql 'equal and '=. There are definite
differences, and '= at least will blow up if you give it anything that
is not a number in Halequin Lispworks.
(defun equal_test ( x y)
(format T "Input Is ~A ~A ~%" `x `y)
(format T "X = ~A Y= ~A ~% ~%" x y)
(if (eq x y)
(format T "(eq x y) Returns TRUE or T ~% ~%")
(format T "(eq x y) Returns FALSE or NIL ~% ~%")
)
(if (eql x y)
(format T "(eql x y) Returns TRUE or T ~% ~%")
(format T "(eql x y) Returns FALSE or NIL ~%~%")
)
(if (equal x y)
(format T "(equal x y) Returns TRUE or T ~% ~%")
(format T "(equal x y) Returns FALSE or NIL ~% ~%")
)
(if (and (numberp x) (numberp y))
(if (= x y)
(format T "(= x y) Returns TRUE or T ~% ~%")
(format T "(= x y) Returns FALSE or NIL ~% ~% ~%")
)
(block MY_BLOCK
(format T "(= x y) ERROR ~% ")
(format T "One of the inputs is not a number, = takes numbers only ~%~%~%")
)
)
)
Then run a bunch of different test values like
(setf x 5.0)
(EQUAL_TEST x 5.0)
(EQUAL_TEST x 'x)
and so on.
It works here, but I won't promise there aren't mistakes.
Muddy
Christopher R. Barry
> Hiya,
> I have to write a recursive function which calculates a number to
> an exponent such as (ex 2 3 ). (answer 8 )
I don't think anyone yet posted the trivial solution. x^n may be
defined recursively as:
n
x = x (when x = 1)
n n-1
x = x * x (when x > 1)
Thus,
(defun rec-expt (x n)
(if (= n 1)
x
(* x (rec-expt x (1- n)))))
Christopher
[Still playing catchup.]
Christopher R. Barry
> n
> x = x (when x = 1)
^
> n n-1
> x = x * x (when x > 1)
^
Those should of course be n instead of x. Why one minute after posting
that error suddenly flashed through my head instead of me catching it
immediately, we'll never know....
Christopher
Barry Margolin
Christopher R. Barry <cba...@2xtreme.net> wrote:
>I don't think anyone yet posted the trivial solution. x^n may be
>defined recursively as:
The original poster did so in his reply to my message on Friday.
> (defun rec-expt (x n)
> (if (= n 1)
> x
> (* x (rec-expt x (1- n)))))
Your function doesn't handle x^0 = 1. The original poster's revised code
does. Score 1 for the newbie!
Coby Beck
> > (if (= n 1)
> > x
> > (* x (rec-expt x (1- n)))))
>
> Your function doesn't handle x^0 = 1. The original poster's revised code
> does. Score 1 for the newbie!
>
There are of course negative powers to be handled!
(defun rec-expt(base power)
(cond
((< power 0 ) (rec-expt (/ 1 base) (abs power)))
((= power 0) 1)
(t (* base (rec-expt base (1- power))))))
I'll leave it to someone else to handle non-integer powers (translation: i
don't know how... :-(
Coby
Thomas A. Russ
> I'll leave it to someone else to handle non-integer powers (translation: i
> don't know how... :-(
Well, I don't know how to handle the non-integer powers recursively, but
one method would use natural logs (and the EXP function, which might be
considered cheating...)
(defun non-integer-expt (b e)
(exp (* e (log b))))
--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu