## Benchmarks

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.

### Takeuchi function

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

### Fibonacci sequence

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.

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

### Factor

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
```
To find the least prime factor of 2146654199 (46327 x 46337):
```> (for-millis () (print (factor 2146654199)))

46327
5752```

### Factorize

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

For example:

```> (factorize 731731731)
(3 17 43 333667)```

### CRC-32

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

For example:

```> (crc32 "The quick brown fox jumps over the lazy dog")
1095738169
```
It takes about 40 ms on an Arduino Due, 64 ms on an Arduino Zero, and 207 ms on a BBC Micro Bit.

1. ^ Performance and Evaluation of Lisp Systems, Richard P. Gabriel, MIT Press, PDF on rpgpoet.com.
2. ^ An erratic two-dimensional recursive function Q2 on Lispology.