Compute arithmetic sum of a constant difference sequence

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)))

I notice three things about your code:

• 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 loop¹.

• 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).

• 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)))

¹ Or in scheme :p

StackExchange Code Review Q#1318, answer score: 2