Parallel Prime Number Detection in Lisp

Prime Number Detection

There is a simple method to determine if a natural number is prime. If a number is divisible by 2 (other than 2 itself), it is an even number. If it is divisible by any odd number greater than 3, it is a composite number and not a prime. This check is performed up to the square root of the natural number. If it is not divisible by any of these, it is a prime number. The Lisp code to achieve this is as follows:

(defun primep (n)
    (cond ((= n 2) t)
          ((= (mod n 2) 0) nil)
          (t (coprimep n 3 (isqrt n)))))

(defun coprimep (n s e)
    (cond ((> s e) t)
          ((= (mod n s) 0) nil)
          (t (coprimep n (+ s 2) e))))

Parallel Computing

This straightforward method requires a lot of computation. By distributing this calculation in parallel, computation time can be reduced. I tackled this in Easy-ISLisp. A parallel construct called mp-exec, which is a multi-process version of progn, is available. However, this construct evaluates all arguments.

(mp-exec (foo1) (foo2) (foo3) (foo4) (foo5))

In prime number detection, if any of the divided calculations determines that the number is not prime, the remaining calculations are unnecessary. Knowing it is a composite number, it is a waste of time to continue the calculations. Therefore, I introduced a parallel construct called mp-part, which stands for partial-execution.

(mp-part (foo1) (foo2) (foo3) (foo4) (foo5))

Using Signals

In implementing mp-part, Unix signals were used. The parent Lisp requests the divided calculations from the child Lisp processes. The child Lisp processes return the results sequentially as they complete, and send a signal to the parent Lisp. The parent Lisp receives this signal and obtains the results from the child Lisp.

If the result is nil, the parent Lisp sends a ctrl+c signal to the child Lisp processes that are still calculating. The child Lisp processes stop their calculations upon receiving this signal.

Prime Number Detection Using Parallel Constructs

The code for prime number detection using mp-part is as follows:

(defun primep* (n)
    (cond ((= n 2) t)
          ((= (mod n 2) 0) nil)
          (t (let* ((limit (isqrt n))
                   (span (div limit 5)))
                 (mp-part (coprimep n 3 span)
                          (coprimep n (near-odd span) (* 2 span ))
                          (coprimep n (near-odd (* 2 span)) (* 3 span))
                          (coprimep n (near-odd (* 3 span)) (* 4 span))
                          (coprimep n (near-odd (* 4 span)) limit))))))

(defun near-odd (n)
    (if (= (mod n 2) 0)
        (- n 1)
        n))


(defun coprimep (n s e)
    (cond ((> s e) t)
          ((= (mod n s) 0) nil)
          (t (coprimep n (+ s 2) e))))

Easy-ISLisp performs tail recursion optimization in its compiler. I compiled and ran the calculations. This was done on a 6-core machine with an AMD Ryzen processor.

For large prime number detection, the effect of parallelism is evident. The execution time is reduced to approximately one-fifth.

The Era of Parallelism

Current CPUs from Intel, AMD, and others are multi-core. Even affordable machines come with 6 cores. High-end gaming machines now feature up to 20 cores. It would be a waste not to utilize these high-performance CPUs. I believe it is beneficial to actively use parallelism in Lisp as well.

Easy-ISLisp is open-source and available on GitHub.