Compute arithmetic sum of a constant difference sequence

Question

3.1

Write a program that computes the arithmetic sum of a constant difference sequence:

D0 = A
Dn+1 = Cdn + B

Run the following values and compare to the closed form solution:

Maximum index = 10,000, a = 1:0; c = 5; b = 2^-15

I am not sure I perfectly understand the problem above or how to confirm that I have the correct answer, but I wrote the following short program and I would appreciate any feedback.

(defun d-n-plus-1 (d-n c b) (+ (* d-n c) b))
(defun d-depth (depth d-n c b a)
 (if (equal depth 0) (d-n-plus-1 d-n c b)
 (d-depth (1- depth) 
 (if (null d-n) a (d-n-plus-1 d-n c b)) 
 c b a)))
(format t "result: ~a ~%" (d-depth 10000 nil 5 (expt 2 -15) 1))

In addition, I wrote a version that just uses a loop. I'm not crazy about "loop for x from 1 to depth" or that I used setq in this version. Can you think of a better way? Any other suggestions for this version are also welcome.

(defun d_n+1 (d_n c b) (+ (* d_n c) b)) 
(defun d-depth (depth d_n c b)
 (loop for x from 0 to depth do 
 (setq d_n (d_n+1 d_n c b))) 
 d_n)
(format t "result: ~a ~%" (d-depth 10000 1 5 (expt 2 -15)))

Answer 1

I notice three things about your code:

1. You're relying on tail-recursion. This is okay if you know your program will only ever run on implementations that perform tail call optimization, but you should be aware that the Common Lisp standard does not require TCO (and more practically speaking some implementations do indeed not offer it). So if you want your program to be portable, you should rewrite it using a loop1.
2. Your d-depth function takes d-n and a as parameters, but only uses a in place of d-n if d-n is nil. It'd make more sense to me to remove the a parameter and instead pass in the a value as the initial value for d-n (instead of nil).
3. I would also write d_n instead of d-n to emphasize that n is an index, which is usually written using an underscore in ASCII. Also I'd call d-n-plus-1 d_n+1 instead, there's no reason to spell out "plus" in lisp.

---

In response to your update:

I'm not crazy about "loop for x from 1 to depth" or that I used setq in this version. Can you think of a better way?

for x from 1 to depth is equivalent to repeat depth (unless you actually use x, which you don't). However in your code you're actually starting at 0, not 1 so you'd need repeat (+ 1 x) to get the same number of iterations.

The setq can be replaced using the for var = start then replacement-form syntax. The result would be something like this:

(defun d-depth (depth a c b)
 (loop repeat (+ 1 depth) 
 for d_n = a then (d_n+1 d_n c b)
 finally (return d_n)))

---

1 Or in scheme :p

• jaresty: If I want to get started with scheme on OSX, do you have any software recommendations?
• sepp2k: @jaresty: I was mostly kidding about switching to scheme. That being said, if you do want to take a look at scheme, racket seems to be the most popular implementation currently and is available on OSX.
• Inaimathi: +1 for starting with Racket. Their docs/tutorials are amazing, and their libraries/package system are fairly extensive (they still have a gap in document generation; last I checked my own v0.001 postscript library is the only semi-helpful module in that vein). Though I have to point out, as a former Racketeer, I'm somewhat biased.
• jaresty: What are the advantages/disadvantages of learning Common Lisp vs. Scheme?
• sepp2k: @jaresty: This answer contains a good summary of the differences between the two (though it's possibly a bit biased given the source that has been quoted).