The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Which way
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 23 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Aug 8 2007, 10:58 pm
Newsgroups: comp.lang.lisp
From: case.learn...@gmail.com
Date: Wed, 08 Aug 2007 19:58:14 -0700
Local: Wed, Aug 8 2007 10:58 pm
Subject: Which way
Hi everyone,

I'm kind of new to Lisp. I'm doing this Newton method problem (not a
homework problem; I'm learning programming myself). These are two
different ways of coding the same solution:

(defun good-enough (n guess)
(< (abs (- (square guess) n)) 0.0001))

(defun square (x)
(* x x))

(defun improve-guess (n guess)
(/ (+ guess (/ n guess)) 2))

FIRST:

(defun newton-sqrt (n)
(newton-sqrt-aux n 1.0))

(defun newton-sqrt-aux (n guess)
(cond ((good-enough n guess) guess)
(t (newton-sqrt-aux n (improve-guess n guess)))))

SECOND:

(defun newton-sqrt (n)
(let ((guess 1.0))
(loop
(cond ((good-enough n guess) (return guess)))
(setq guess (improve-guess n guess)))))

The what is really the difference between the two, and how I should

Thank you.

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 8 2007, 11:44 pm
Newsgroups: comp.lang.lisp
From: Ken Tilton <kennytil...@optonline.net>
Date: Wed, 08 Aug 2007 23:44:32 -0400
Local: Wed, Aug 8 2007 11:44 pm
Subject: Re: Which way

Lisp has flet, labels, and lambda so you never need to create a
standalone function needed only by one caller. Your desired aux func
calls itself, so you need labels.

Using cond to code if is pretty scary, btw.

> SECOND:

> (defun newton-sqrt (n)
>   (let ((guess 1.0))
>     (loop
>      (cond ((good-enough n guess) (return guess)))
>      (setq guess (improve-guess n guess)))))

Ouch. Untested:

(loop for guess = 1.0 then (improve-guess n guess)
when (good-enough n guess) return guess)

> The what is really the difference between the two, and how I should

(a) nothing, so (b) you should think about the program you are trying to
write, not this.

You might also think that Lisp is huge enough to give you lotsa ways to
implement the same thing. As one brilliant wag once said (paraphrasing)
(1- lotsa) of them are wrong. How to choose? The question is not how you
should think about the code solutions, the question is how do you think
about the problem? Write the code the same way. Sure, one may well think
about the problem the wrong way, but if so no computer language rules of
thumb will help.

kt

"Algebra is the metaphysics of arithmetic." - John Ray

"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts

"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz

"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 10:04 am
Newsgroups: comp.lang.lisp
From: Slobodan Blazeski <slobodan.blaze...@gmail.com>
Date: Thu, 09 Aug 2007 07:04:29 -0700
Local: Thurs, Aug 9 2007 10:04 am
Subject: Re: Which way
On Aug 9, 5:44 am, Ken Tilton <kennytil...@optonline.net> wrote:

1. I'm dreaming
2. I'm halucinating
3. Aliens abducted Kenny  and replace him with some hybrid who
4. Kenny is actully being nice & helpfull to a newbie.

Hm... 3
Get our old Kenny back you alien scumbag or we're starting an
intergalactical war of the worlds ?

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 10:20 am
Newsgroups: comp.lang.lisp
From: case.learn...@gmail.com
Date: Thu, 09 Aug 2007 07:20:06 -0700
Local: Thurs, Aug 9 2007 10:20 am
Subject: Re: Which way
On Aug 8, 9:44 pm, Ken Tilton <kennytil...@optonline.net> wrote:

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 10:20 am
Newsgroups: comp.lang.lisp
From: case.learn...@gmail.com
Date: Thu, 09 Aug 2007 07:20:29 -0700
Local: Thurs, Aug 9 2007 10:20 am
Subject: Re: Which way
On Aug 9, 8:04 am, Slobodan Blazeski <slobodan.blaze...@gmail.com>
wrote:

I have no idea what you're talking about.

Mark.

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 10:31 am
Newsgroups: comp.lang.lisp
From: Slobodan Blazeski <slobodan.blaze...@gmail.com>
Date: Thu, 09 Aug 2007 14:31:23 -0000
Local: Thurs, Aug 9 2007 10:31 am
Subject: Re: Which way
On Aug 9, 4:20 pm, case.learn...@gmail.com wrote:

Shut up and get your laser pistol. I'll explain you on the way. We
have aliens to fight.

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 10:45 am
Newsgroups: comp.lang.lisp
From: Slobodan Blazeski <slobodan.blaze...@gmail.com>
Date: Thu, 09 Aug 2007 14:45:04 -0000
Local: Thurs, Aug 9 2007 10:45 am
Subject: Re: Which way
On Aug 9, 4:58 am, case.learn...@gmail.com wrote:

By the way you could define square as macro to gain some speed, if you
don't plan to use it as argument, for better explanation search
Grahams On Lisp for Computation at compile-time (chapter 13) freely
available at http://www.paulgraham.com/onlisp.html

(defmacro square (x)
`(* ,x ,x))

2nd Sometimes is better to keep functions as global, in order to reuse
them as utilities.
See On Lisp - Programming Bottom-Up and Utilities.

3rd cond looks better than nested if's , but avoid using cond in
situations where if or even when/unless will suffice.

have a nice lisping

bobi

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 10:55 am
Newsgroups: comp.lang.lisp
From: Tamas Papp <tkp...@gmail.com>
Date: Thu, 09 Aug 2007 16:55:06 +0200
Local: Thurs, Aug 9 2007 10:55 am
Subject: Re: Which way

Slobodan Blazeski <slobodan.blaze...@gmail.com> writes:
> By the way you could define square as macro to gain some speed, if you
> don't plan to use it as argument, for better explanation search
> Grahams On Lisp for Computation at compile-time (chapter 13) freely
> available at http://www.paulgraham.com/onlisp.html

> (defmacro square (x)
>   `(* ,x ,x))

This gives negligible speed improvement and is unsafe.  See
http://www.gigamonkeys.com/book/macros-defining-your-own.html,
"Plugging the leaks."

For speed improvements, use declarations or compiler macros (Mark, you
can ignore compiler macros for now).

> 2nd Sometimes is better to keep functions as global, in order to reuse
> them as utilities.
> See On Lisp - Programming Bottom-Up and Utilities.

Except that in this program, the helper functions are very specific so
there is no point in doing that.

BTW, On Lisp is not something I would recommend for newbies.

Tamas

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 10:57 am
Newsgroups: comp.lang.lisp
From: Slobodan Blazeski <slobodan.blaze...@gmail.com>
Date: Thu, 09 Aug 2007 14:57:48 -0000
Local: Thurs, Aug 9 2007 10:57 am
Subject: Re: Which way
On Aug 9, 4:45 pm, Slobodan Blazeski <slobodan.blaze...@gmail.com>
wrote:

This is more stylistic but adding documentation string and proper
naming would be very nice. Lispers have tradition of very-long-and-
from

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 11:10 am
Newsgroups: comp.lang.lisp
From: Slobodan Blazeski <slobodan.blaze...@gmail.com>
Date: Thu, 09 Aug 2007 15:10:31 -0000
Local: Thurs, Aug 9 2007 11:10 am
Subject: Re: Which way
On Aug 9, 4:55 pm, Tamas Papp <tkp...@gmail.com> wrote:

> Slobodan Blazeski <slobodan.blaze...@gmail.com> writes:
> > By the way you could define square as macro to gain some speed, if you
> > don't plan to use it as argument, for better explanation search
> > Grahams On Lisp for Computation at compile-time (chapter 13) freely
> > available athttp://www.paulgraham.com/onlisp.html

> > (defmacro square (x)
> >   `(* ,x ,x))

> This gives negligible speed improvement and is unsafe.  Seehttp://www.gigamonkeys.com/book/macros-defining-your-own.html,
> "Plugging the leaks."

Tend to disagreee , for other opinion see cl-statistics.

> For speed improvements, use declarations or compiler macros (Mark, you
> can ignore compiler macros for now).

Mark can ignore the whole optimization staff for now.

> > 2nd Sometimes is better to keep functions as global, in order to reuse
> > them as utilities.
> > See On Lisp - Programming Bottom-Up and Utilities.

> Except that in this program, the helper functions are very specific so
> there is no point in doing that.

newton-sqrt-aux  should be labeled , but  square is a  general purpose
function/ macro that I end up writing or including a lot for the
other decide for yourself.

> BTW, On Lisp is not something I would recommend for newbies.

Chapter 1. The Extensible Language 1 consisted of
1.1. Design by Evolution 1
1.2. Programming Bottom-Up 3
1.3. Extensible Software 5
1.4. Extending Lisp 6
1.5. Why Lisp (or When

Is a great read even for a newbie and even if you decide to continue
with the rest of the book later in your journey. Especially 1-4 are
real eye opener for a new lisp programmer.

Bobi

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 11:43 am
Newsgroups: comp.lang.lisp
From: Zach Beane <x...@xach.com>
Date: Thu, 09 Aug 2007 11:43:32 -0400
Local: Thurs, Aug 9 2007 11:43 am
Subject: Re: Which way

Slobodan Blazeski <slobodan.blaze...@gmail.com> writes:
> On Aug 9, 4:55 pm, Tamas Papp <tkp...@gmail.com> wrote:
>> Slobodan Blazeski <slobodan.blaze...@gmail.com> writes:
>> > By the way you could define square as macro to gain some speed, if you
>> > don't plan to use it as argument, for better explanation search
>> > Grahams On Lisp for Computation at compile-time (chapter 13) freely
>> > available athttp://www.paulgraham.com/onlisp.html

>> > (defmacro square (x)
>> >   `(* ,x ,x))

>> This gives negligible speed improvement and is unsafe.  Seehttp://www.gigamonkeys.com/book/macros-defining-your-own.html,
>> "Plugging the leaks."

> Tend to disagreee , for other opinion see cl-statistics.

Its usage in cl-statistics is just as ill-advised. This is not an idea
to copy for SQUARE.

Zach

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 11:58 am
Newsgroups: comp.lang.lisp
From: "andrew.ba...@gmail.com" <andrew.ba...@gmail.com>
Date: Thu, 09 Aug 2007 15:58:40 -0000
Local: Thurs, Aug 9 2007 11:58 am
Subject: Re: Which way
On Aug 9, 11:43 am, Zach Beane <x...@xach.com> wrote:

Just to elaborate for OP's benefit: if you do (defmacro square
(x) ...) then as Slobodan noted, you can't use square as a function
argument to lots of lisp's incredibly useful functions.  For example,
you might want to do (mapcar #'square '(1 2 3 4)) and get (1 4 9 16).
Not possible if square is a macro.  Since square is not used this way
in your program, I think that Slobodan was taking a no-harm no-foul
approach.  I'd prefer the function to the macro though.

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 12:02 pm
Newsgroups: comp.lang.lisp
From: Tamas Papp <tkp...@gmail.com>
Date: Thu, 09 Aug 2007 18:02:45 +0200
Local: Thurs, Aug 9 2007 12:02 pm
Subject: Re: Which way

Slobodan Blazeski <slobodan.blaze...@gmail.com> writes:
> On Aug 9, 4:55 pm, Tamas Papp <tkp...@gmail.com> wrote:
>> Slobodan Blazeski <slobodan.blaze...@gmail.com> writes:
>> > By the way you could define square as macro to gain some speed, if you
>> > don't plan to use it as argument, for better explanation search
>> > Grahams On Lisp for Computation at compile-time (chapter 13) freely
>> > available athttp://www.paulgraham.com/onlisp.html

>> > (defmacro square (x)
>> >   `(* ,x ,x))

>> This gives negligible speed improvement and is unsafe.  Seehttp://www.gigamonkeys.com/book/macros-defining-your-own.html,
>> "Plugging the leaks."

> Tend to disagreee , for other opinion see cl-statistics.

Look at this:

(defun square (x)
(* x x))

(defmacro square-macro (x)
;; unsafe
`(* ,x ,x))

(declaim (inline square-inline))
(defun square-inline (x)
;; inlined version
(* x x))

(defparameter *n* 1000000)

(time (let ((sum 0))
(dotimes (i *n*)
(incf sum (square (/ i *n*))))))

(time (let ((sum 0))
(dotimes (i *n*)
(incf sum (square-macro (/ i *n*))))))

(time (let ((sum 0))
(dotimes (i *n*)
(incf sum (square-inline (/ i *n*))))))

Now the evaluation times:

; plain vanilla
; /tmp/file86RiQF.fasl written
; compilation finished in 0:00:00
Evaluation took:
9.636 seconds of real time
9.358577 seconds of user run time
0.086987 seconds of system run time
[Run times include 0.441 seconds GC run time.]
0 calls to %EVAL
0 page faults and
725,466,656 bytes consed.
; compiling file "/tmp/fileg05YV9.lisp" (written 09 AUG 2007 05:52:58 PM):

; /tmp/fileg05YV9.fasl written
; compilation finished in 0:00:00
Evaluation took:
9.945 seconds of real time
9.629536 seconds of user run time
0.093985 seconds of system run time
[Run times include 0.465 seconds GC run time.]
0 calls to %EVAL
0 page faults and
741,483,296 bytes consed.
; compiling file "/tmp/filehj4WOX.lisp" (written 09 AUG 2007 05:53:11 PM):

; inlined version
; /tmp/filehj4WOX.fasl written
; compilation finished in 0:00:00
Evaluation took:
9.596 seconds of real time
9.318584 seconds of user run time
0.088987 seconds of system run time
[Run times include 0.431 seconds GC run time.]
0 calls to %EVAL
0 page faults and
725,481,264 bytes consed.

The speed "improvement" provided by the macro is within the margin of
error (if you rerun, you get different slightly different times).

You have gained nothing, but got an unsafe macro on your hands.  Hint:

(defparameter *a* 1)
(square-macro (incf *a*))  ; => 6

Lessons learned:

- using macros for optimization is dubious at best
- most compilers are pretty smart, don't try to second-guess them

BTW, the above was done with SBCL.

>> For speed improvements, use declarations or compiler macros (Mark, you
>> can ignore compiler macros for now).
> Mark can ignore the whole optimization staff for now.

Poor optimization staff.  Imagine being hired explicitly for
optimization, then being ignored. ;-)

> Is a great read even for a newbie and even if you decide to continue
> with the rest of the book later in your journey. Especially 1-4 are
> real eye opener for a new lisp programmer.

I agree that On Lisp is a great book, but PCL and Graham's ANSI CL are
better as an introduction.

Tamas

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 12:05 pm
Newsgroups: comp.lang.lisp
From: Zach Beane <x...@xach.com>
Date: Thu, 09 Aug 2007 12:05:59 -0400
Local: Thurs, Aug 9 2007 12:05 pm
Subject: Re: Which way

"andrew.ba...@gmail.com" <andrew.ba...@gmail.com> writes:
>> Its usage in cl-statistics is just as ill-advised. This is not an idea
>> to copy for SQUARE.

>> Zach

> Just to elaborate for OP's benefit: if you do (defmacro square
> (x) ...) then as Slobodan noted, you can't use square as a function
> argument to lots of lisp's incredibly useful functions.  For example,
> you might want to do (mapcar #'square '(1 2 3 4)) and get (1 4 9 16).
> Not possible if square is a macro.  Since square is not used this way
> in your program, I think that Slobodan was taking a no-harm no-foul
> approach.  I'd prefer the function to the macro though.

There's an additional problem if the form X has any side-effects. If
SQUARE is a function, the form is evaluated once and the value is
passed to the function. With SQUARE as a macro as defined, the form is
evaluated twice, duplicating the side-effect.

Zach

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 12:44 pm
Newsgroups: comp.lang.lisp
From: Juho Snellman <jsn...@iki.fi>
Date: 9 Aug 2007 16:44:41 GMT
Local: Thurs, Aug 9 2007 12:44 pm
Subject: Re: Which way

Tamas Papp <tkp...@gmail.com> wrote:
> (defparameter *n* 1000000)

> (time (let ((sum 0))
>    (dotimes (i *n*)
>      (incf sum (square (/ i *n*))))))

While I don't disagree with the general sentiment (macros shouldn't be
used for optimization, when inlining does the same job), your
benchmark probably isn't a very good illustration of that. The
overhead of doing all the computations with ratios (due to the use of
/) is probably completely overwhelming any other effects.

Using for example ROUND instead of / will show the effects better:

(time (let ((sum 0))
(dotimes (i *n*)
(incf sum (square (round i *n*))))))

;;; etc for the other three loops

With this, the macro version should be slower than either of the
functions, since the ROUND is executed twice due to the buggy macro
definition.

--
Juho Snellman

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 2:43 pm
Newsgroups: comp.lang.lisp
From: mmcconnell17...@yahoo.com
Date: Thu, 09 Aug 2007 11:43:44 -0700
Local: Thurs, Aug 9 2007 2:43 pm
Subject: Re: Which way
In addition to the other replies, there is a whole story about whether
tail recursion is as efficient as iteration.  newton-sqrt-aux is tail-
recursive.  This means two things: it calls itself (the "recursive"
part), and the last thing the k-th call does is to return the result
of the (k+1)-st call (the "tail" part).  Sometimes tail-recursion will
be implemented as a jump from one part of the function back to near
the beginning.  That is likely what the second version, with loop,
does.  Other times, there is a stack of function calls.  The k-th call
to newton-sqrt-aux will create the (k+1)-st call to newton-sqrt-aux.
All the calls will remain on the stack until the deepest call
finishes, at which point they unwind in reverse order.

One danger of the stack-based approach is that the stack may fill up
after a few thousand calls, making the program crash.  This is not a
theoretical danger.  Even compiled, an intensely recursive program can
run out of space and crash.  (It's not just Lisp.  I've crashed Java
with tail-recursive functions, and I bet it could happen in most
languages.)

A newbie should note that many people feel tail recursion is
beautiful.  It is the right solution for many problems.  One of the
good things about Lisp is that it encourages this style.

Again for the sake of the newbie, I can't resist an example in Allegro
CL 8.0.

(defun ct (n)
"Count backwards tail-recursively from n to 0."
(if (<= n 0)
'done
(ct (1- n))))

(ct 1000000)
;; This crashes the interpreter.
;; And you'd expect it to!
;; Interpreted functions naturally use a stack.

(compile 'ct)
;; Change it to a compiled function.

(ct 1000000)
DONE
;; very fast

(disassemble 'ct) ;; look for jmp
;; disassembly of #<Function CT>
;; formals: N
;; constant vector:
0: DONE

;; code start: #x21d9ec74:
0: 55          pushl ebp
1: 8b ec       movl  ebp,esp
3: 56          pushl esi
4: 83 ec 2c    subl  esp,\$44
7: 83 f9 01    cmpl  ecx,\$1
10: 74 03       jz    15
12: ff 57 8b    call  *[edi-117]      ; SYS::TRAP-WNAERR
15: 80 7f cb 00 cmpb  [edi-53],\$0     ; SYS::C_INTERRUPT-PENDING
19: 74 03       jz    24
21: ff 57 87    call  *[edi-121]      ; SYS::TRAP-SIGNAL-HIT
24: 89 45 e4    movl  [ebp-28],eax    ; N
27: 33 d2       xorl  edx,edx
29: a8 03       testb al,\$3
31: 75 0d       jnz   46
33: 3b c2       cmpl  eax,edx
35: 7f 16       jnle  59
37: 8b 46 12    movl  eax,[esi+18]    ; DONE
40: f8          clc
41: c9          leave
42: 8b 75 fc    movl  esi,[ebp-4]
45: c3          ret
46: 8b 9f 97 fe movl  ebx,[edi-361]   ; EXCL::<=_2OP
ff ff
52: ff 57 27    call  *[edi+39]       ; SYS::TRAMP-TWO
55: 3b f8       cmpl  edi,eax
57: 75 ea       jnz   37
59: 33 d2       xorl  edx,edx
61: b2 04       movb  dl,\$4
63: 8b 5d e4    movl  ebx,[ebp-28]    ; N
66: f6 c3 03    testb bl,\$3
69: 75 08       jnz   79
71: 8b c3       movl  eax,ebx
73: 2b c2       subl  eax,edx
75: 70 02       jo    79
77: eb c0       jmp   15
79: 8b c3       movl  eax,ebx
81: 8b 9f df fd movl  ebx,[edi-545]   ; EXCL::-_2OP
ff ff
87: ff 57 27    call  *[edi+39]       ; SYS::TRAMP-TWO
90: eb b3       jmp   15

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 2:52 pm
Newsgroups: comp.lang.lisp
From: Tamas Papp <tkp...@gmail.com>
Date: Thu, 09 Aug 2007 20:52:24 +0200
Local: Thurs, Aug 9 2007 2:52 pm
Subject: Re: Which way

mmcconnell17...@yahoo.com writes:
> One danger of the stack-based approach is that the stack may fill up
> after a few thousand calls, making the program crash.  This is not a
> theoretical danger.  Even compiled, an intensely recursive program can
> run out of space and crash.  (It's not just Lisp.  I've crashed Java
> with tail-recursive functions, and I bet it could happen in most
> languages.)

I agree (and your example, which I cut from this reply, is
instructive).  But in the actual case, the OP is safe: Newton's method
either converges quickly or diverges wildly.  Sometimes it is possible
to demonstrate convergence analytically.

Best,

Tamas

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 4:15 pm
Newsgroups: comp.lang.lisp
From: "Steven E. Harris" <s...@panix.com>
Date: Thu, 09 Aug 2007 13:15:15 -0700
Local: Thurs, Aug 9 2007 4:15 pm
Subject: Re: Which way

Tamas Papp <tkp...@gmail.com> writes:
> But in the actual case, the OP is safe: Newton's method either
> converges quickly or diverges wildly.

This thread may be relevant here:

Floating point arithmetic (epsilon)

My participation in that thread dropped off before I could share my
eventual solution, as it took many more days of analysis and
experimentation to get it right.

--
Steven E. Harris

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2007, 6:03 pm
Newsgroups: comp.lang.lisp
From: t...@sevak.isi.edu (Thomas A. Russ)
Date: 09 Aug 2007 15:03:09 -0700
Local: Thurs, Aug 9 2007 6:03 pm
Subject: Re: Which way

Slobodan Blazeski <slobodan.blaze...@gmail.com> writes:
> By the way you could define square as macro to gain some speed,

I would guess the speed-up would be negligible compared to leaving it a
function and declaiming it to be inline.

> if you
> don't plan to use it as argument, for better explanation search

I don't understand what "don't plan to use it as argument" means.

> Grahams On Lisp for Computation at compile-time (chapter 13) freely
> available at http://www.paulgraham.com/onlisp.html

> (defmacro square (x)
>   `(* ,x ,x))

Ack!  This is incorrect code.  Don't copy it.  Consider:

(defparameter *count* 0)

(square (incf *count*))  =>  2
(square (incf *count*))  =>  6

The side effects will kill you.  The above was somewhat contrived, but
imagine you want to work with successive prime numbers and have a nice
function NEXT-PRIME that will give you the next prime number in
sequence.

(square (next-prime))

would produce the same evil results from being evaluated twice.  So you
would need to introduce a macro like

(defmacro square (x)
(let ((var (gensym)))
`(let ((,var ,x))
(* ,var ,var))))

At which point the macro may slow things down, since you would lose any
declarations such as in:

(let ((n 10))
(declare (fixnum n))
(square n))

So that means you now need to perhaps write a much more complicated
macro, perhaps something like:

(defmacro square (x)
(if (atom x)
`(* ,x ,x)
(let ((var (gensym)))
`(let ((,var ,x))
(* ,var ,var)))))

QUESTION:  Is this safe in the presence of symbol-macros?  I've never
really used them, so I don't know a lot about them.

Anyway, at this point the macro is getting a bit on the hairy side, so I
would suggest using an in-lined function and letting the compiler worry
about how to handle the argument evaluation.

--
Thomas A. Russ,  USC/Information Sciences Institute

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 10 2007, 3:16 am
Newsgroups: comp.lang.lisp
From: Nicolas Neuss <lastn...@mathematik.uni-karlsruhe.de>
Date: 10 Aug 2007 09:16:34 +0200
Local: Fri, Aug 10 2007 3:16 am
Subject: Re: Which way

Tamas Papp <tkp...@gmail.com> writes:
> I agree (and your example, which I cut from this reply, is instructive).
> But in the actual case, the OP is safe: Newton's method either converges
> quickly or diverges wildly.

You can easily construct problems with arbitrary slow convergence or cycles
of the Newton iterates.

> Sometimes it is possible to demonstrate convergence analytically.

For _every_ smooth and well-posed problem good convergence is guaranteed if
your starting guess is sufficiently close to the solution.

Nicolas

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 10 2007, 3:30 am
Newsgroups: comp.lang.lisp
From: Tamas Papp <tkp...@gmail.com>
Date: Fri, 10 Aug 2007 09:30:02 +0200
Local: Fri, Aug 10 2007 3:30 am
Subject: Re: Which way

Nicolas Neuss <lastn...@mathematik.uni-karlsruhe.de> writes:
> Tamas Papp <tkp...@gmail.com> writes:

>> I agree (and your example, which I cut from this reply, is instructive).
>> But in the actual case, the OP is safe: Newton's method either converges
>> quickly or diverges wildly.

> You can easily construct problems with arbitrary slow convergence or cycles
> of the Newton iterates.

>> Sometimes it is possible to demonstrate convergence analytically.

> For _every_ smooth and well-posed problem good convergence is guaranteed if
> your starting guess is sufficiently close to the solution.

The proof I know guarantees things for an epsilon neighborhood of the
root.  Nice result in analysis, but of little practical value, as
there is no way to find out that epsilon.

Tamas

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 10 2007, 3:59 am
Newsgroups: comp.lang.lisp
From: Nicolas Neuss <lastn...@mathematik.uni-karlsruhe.de>
Date: 10 Aug 2007 09:59:33 +0200
Local: Fri, Aug 10 2007 3:59 am
Subject: Re: Which way

Tamas Papp <tkp...@gmail.com> writes:
> The proof I know guarantees things for an epsilon neighborhood of the
> root.  Nice result in analysis, but of little practical value, as there
> is no way to find out that epsilon.

If you have control over first and second derivatives, you can easily find
an explicit formula for epsilon which can be of practical value.  Many
formulations of the Newton convergence theorem quantify this epsilon (the
usual convergence proof will spit it out).

Nicolas

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 10 2007, 12:52 pm
Newsgroups: comp.lang.lisp
From: "Steven E. Harris" <s...@panix.com>
Date: Fri, 10 Aug 2007 09:52:04 -0700
Local: Fri, Aug 10 2007 12:52 pm
Subject: Re: Which way

Tamas Papp <tkp...@gmail.com> writes:
> there is no way to find out that epsilon.

Have you looked at Erik Naggum's scaled-epsilon¹ function from the
thread I mentioned yesterday? I used that in my Newton's Method solver
to adapt epsilon to the root being searched. Regardless of the magnitude
of the root candidate, using this scaled-epsilon function can determine
whether the next delta is below the precision threshold.

--
Steven E. Harris

To post a message you must first join this group.
You do not have the permission required to post.
 End of messages
 « Back to Discussions « Newer topic Older topic »