Fibbo K

One of the oldest most visited problems in any computer science course the Fibonacci series a very good explanation including sample algorithms can be found in the almighty Wikipedia

This program presents a slight extension in that you can calculate series formed by the sum of the k prior elements. All you have to do is change the size of the array that stores the k prior numbers.

There is just a little trick to work out in which element of the array will the nth element be stored.


;working array of only two el elements
;If the array is initialised to k the program will calculate series or order k
;That is f(i)=f(i-1)+...+f(i-k) when k=2 its the Fibonacci series
(setq arr (make-array 2))

;initialising the array
; builds the first array for k as (0 ... k)
(dotimes (i (array-dimension arr 0))
(setf (aref arr i ) i )
)

;function summing all the elements in the array
(defun sum (vect)
(setq temp 0)
(dotimes (i (array-dimension arr 0))
(setq temp (+ temp (aref vect i )))
)
(setq sum temp)
)

;function calculating the fibbonaci-k series without recursion
(defun fib(pos)
(setq buffSize (array-dimension arr 0 ))
(dotimes (i pos)
(setq j (mod i buffSize))
(setf (aref arr j) (sum arr))
)
(setq extract (mod (- pos 1) (array-dimension arr 0)))
(setq fib (aref arr extract))
)

(print '(I will calculate for you the nth fibonacci number n= ) )
(setq num (read))
(print '(using k=))
(print (array-dimension arr 0))

(setq res (fib num))

(print res)
;(print arr)


This is one of the typical algorithms that gains alot from being de-recursified. Like this the memory footprint is low, the computation time also, as we only add a modulus operation, and everyone is happy.