Prime factors are prime numbers that multiply together to make a given number. The prime factors of 10 are 2 and 5. The prime factors of 120 are 2, 2, 2, 3, and 5.
This post presents a simple, brute-force algorithm for finding the prime factors of a number. The post implements the algorithm in Java 11 and in Common Lisp (SBCL 2.0.1). You'll see the Java code, the Common Lisp code, and you'll get an idea of how fast the two implementations run.
I'm writing this hoping that the post will help readers to better understand how both programming languages compare to one another in syntax as well as in performance.
Java has been around since 1996 (though there were betas before that). Java 11 has been around since 2018. Java compiles into byte-code that runs on the Java Virtual Machine (JVM).
Lisp has been around since the late 50's. Common Lisp has been around since about 1986. SBCL Common Lisp compiles directly into efficient machine code for the processor that the system is using. The compiled code runs natively on the processor. Nevertheless, unlike in Java, the compilation step is transparent to the Lisp programmer, so programming Lisp feels like programming an interpreter rather than a compiler.
The code for the Java implementation of prime-factors is spread across two files: Primes.java and main.java.
package com.sinistercode;
import java.util.ArrayList;
import java.util.List;
public class Primes {
public static boolean isPrime(Long n) {
if (n < 4L) {
return n == 2 || n == 3;
}
if (n % 2 == 0 || n % 3 == 0) {
return false;
}
for (long a = 5; a < Math.sqrt(n); a += 6) {
if (n % a == 0 || n % (a + 2) == 0) {
return false;
}
}
return true;
}
public static List<Long> primeFactors(long n) {
if (isPrime(n)) {
return List.of(n);
}
ArrayList<Long> list = new ArrayList<>();
for (long a = 2; a < n / 2; a++) {
if (n % a == 0) {
list.addAll(primeFactors(a));
list.addAll(primeFactors(n / a));
break;
}
}
return list;
}
}
package com.sinistercode;
import java.util.List;
public class Main {
public static void main(String[] args) {
final long startTime = System.currentTimeMillis();
final List<Long> result = Primes.primeFactors(74805770726454941L);
final long elapsedTime = System.currentTimeMillis() - startTime;
System.out.println(" Time: " + elapsedTime + "ms");
System.out.println("Result: " + result.toString());
}
}
After compiling the Java program, you can run it like this:
java -classpath sinistercode/primes/primes.java/out/production/primes com.sinistercode.Main
Time: 1276ms
Result: [108413167, 690006323]
After running that command a number of times on my computer, I found that the averate value for Time was always a little over 1200 (milliseconds).
The Common Lisp code is given in a single file. It contains a single optimization, which consists of explicitly marking two or three of the variables as fixnums. Other optimizations, such as speed, safety, and debugging optimizations are not enabled.
(defparameter *n* 74805770726454941)
(defun is-prime (n)
(declare (fixnum n))
(cond ((< n 4) (or (= n 2) (= n 3)))
((or (zerop (mod n 2)) (zerop (mod n 3))) nil)
(t (loop for a of-type fixnum from 5 to (floor (sqrt n)) by 6
never (or (zerop (mod n a)) (zerop (mod n (+ a 2))))))))
(defun prime-factors (n)
(declare (fixnum n))
(if (or (is-prime n) (= n 1))
(list n)
(loop for a from 2 to (floor n 2)
when (zerop (mod n a)) do
(return (append (prime-factors a) (prime-factors (/ n a)))))))
You can load this code into your Lisp system with something like
(load "primes.lisp")
Or, you can simple paste the code into your REPL.
Then, you can run the code like this:
(prime-factors *n*)
Which causes the REPL to output this:
(108413167 690006323)
To get a sense for how long the function takes to run, you can use the Common Lisp time macro, like this:
(time (prime-factors *n*))
The REPL will reply with something like this:
Evaluation took:
1.022 seconds of real time
1.021410 seconds of total run time (1.021410 user, 0.000000 system)
99.90% CPU
2,647,528,084 processor cycles
0 bytes consed
(108413167 690006323)
In a large number of trials, at different times, with different computer loads, the average length of time was always very slightly over 1000 milliseconds.
I'll leave the comparison of the aesthetics of the different programming languages up to the reader, but I think it's safe to say that for this particular problem, using a minimum of type hints, the Common Lisp program runs about 20% faster than the Java program. Even though Java is slower in this particular case, Java is a generally a high-performance language and there are lots of cases where a Java program might be faster than the equivalent Lisp program.
Common Lisp allows you to interact with the code that you're writing (and even the the code that you're running, while it's running) in much the same way that you interact with an SQL database. There's a back-and-forth that occurs when you're programming in Lisp, like a query-response system, where a query can involve, for example, making a change to a function or calling a function. For example, after you type the following code:
(defun is-prime (n)
(cond ((< n 4) (or (= n 2) (= n 3)))
((or (zerop (mod n 2)) (zerop (mod n 3))) nil)
(t (loop for a from 5 to (sqrt n) by 6
never (or (zerop (mod n a))
(zerop (mod n (+ a 2))))))))
You can immediately call the is-prime function by typing this:
(is-prime 101)
or even this
(loop for a from 1 to 100 when (is-prime a) collect a)
which would give you a list of all the prime numbers between 1 and 100 (inclusive).
When compiling code that you wrote in an editor, you're compiling at the granularity of function definitions, not files. Therefore, if you go back and make a change to a function, you normally compile just that function that you changed, and not the file in which that function resides.
This interactivity makes it easy to quickly become confident that the function you've written is going to work as you expect. You're never tempted to continue to write all the other necessary functions before you start testing. The same is true for smaller pieces of code inside the function.
In Java, on the other hand, most programmers fall into an iterative approach where they compile the program, run it, stop it, edit it, recompile it again, and so on. The environment is not quite as good about allowing you to interact with the code. There's always a temptation to write as much code as possible in each iteration, and to focus on testing/debugging once a lot of the code is written.
I never recommend Common Lisp to anyone and it probably isn't a good solution for large corporations, especially given that the language itself is programmable (as opposed to Java, which sees changes only from release to release, where those changes are made by the official Java Language designers). I can just imagine the mess that some programmers could make given the power to be language designers. When you program in Lisp, you have that power. When you program in Java, you don't.
Nevertheless, when I tinker with Neural Network ideas or when I want to explore a solution to a complex problem, I always rely on Common Lisp, even if the solution is ultimately delivered in Java or Python or some other mainstream language. In that exploratory phase, I can shave weeks off a project by using Common Lisp to have a conversation with my computing environment.