This page gives a collection of simple Lisp programs that have traditionally been used for benchmarking Lisp systems. Most of them are recursive, and some of them have no other obvious practical use beyond acting as a benchmark.
A classic benchmark for comparing implementations of Lisp is this variant of the Takeuchi function, originally used by Ikuo Takeuchi of Japan, and described in the book Performance and Evaluation of Lisp Systems :
(defun tak (x y z) (if (not (< y x)) z (tak (tak (1- x) y z) (tak (1- y) z x) (tak (1- z) x y))))
A good set of parameters, giving execution times in the range 30 to 90 secs for typical uLisp platforms, is:
(tak 18 12 6)
On an Arduino Mega 2560 (tak 18 12 6) takes 49 secs to return the answer 7.
On 32-bit platforms, or 16-bit platforms that take less than approximately 30 seconds, you can return the time in milliseconds using:
(for-millis () (print (tak 18 12 6)))
The Fibonacci sequence is:
1, 1, 2, 3, 5, 8, 13, 21 ...
where the first two terms are 1, and each subsequent term is the sum of the two previous terms. The following recursive function finds the nth term, counting from 0:
(defun fib (n) (if (< n 3) 1 (+ (fib (- n 1)) (fib (- n 2)))))
On an Arduino Mega 2560 (fib 23) takes 28 secs to return the answer 28657.
Hofstadter Q sequence
This is one of several recursive sequences described in Douglas Hofstadter's book "Gödel, Escher, Bach: an Eternal Golden Braid". It is defined as follows:
(defun q (n) (if (<= n 2) 1 (+ (q (- n (q (- n 1)))) (q (- n (q (- n 2)))))))
It is related to the Fibonacci sequence, except that in this case the two preceding terms specify how far to go back in the sequence to find the two terms to be summed.
On an Arduino Mega 2560 (q 21) takes 52 secs to return the answer 12.
Two-dimensional recursive function Q2
This function Q2 is my two-dimensional extension of the Hofstadter Q sequence :
(defun q2 (x y) (if (or (< x 1) (< y 1)) 1 (+ (q2 (- x (q2 (1- x) y)) y) (q2 x (- y (q2 x (1- y)))))))
It's a time-consuming function to calculate. For example, it takes about 40 seconds to calculate (q2 7 8) on an Adafruit ItsyBitsy M0:
> (for-millis () (print (q2 7 8))) 31 40239
This function takes a simple approach to finding the least prime factor of a number:
(defun factor (n) (let ((d 2) (i 1)) (loop (when (> (* d d) n) (return n)) (when (zerop (mod n d)) (return d)) (incf d i) (setq i 2))))
If the number is prime, factor will print the number itself.
For example, on a 32-bit platform to find the least prime factor of 2142142141 (it's a prime), and time how long it takes:
> (for-millis () (print (factor 2142142141))) 2142142141 5696
> (for-millis () (print (factor 2146654199))) 46327 5752
You can use the above factor function as the basis for a simple recursive routine to factorize a number into a list of its prime factors:
(defun factorize (n) (let ((f (factor n))) (if (= n f) (list n) (cons f (factorize (/ n f))))))
> (factorize 731731731) (3 17 43 333667)
Calculates a CRC-32 Cyclic Redundancy Check. This requires 32-bit integer arithmetic:
(defun crc32 (str) (let ((crc #xFFFFFFFF)) (dotimes (k (length str)) (let* ((c (char str k)) (n (char-code c))) (dotimes (i 8) (setq crc (if (oddp (logxor n crc)) (logxor (logand (ash crc -1) #x7FFFFFFF) #xEDB88320) (logand (ash crc -1) #x7FFFFFFF))) (setq n (ash n -1))))) (logxor crc #xFFFFFFFF)))
> (crc32 "The quick brown fox jumps over the lazy dog") 1095738169