A pure functional Primality Test in Scala

A good algorithm to determine if a number is prime is one that tests only a subset of all numbers to enhance its performance. On the contrary, a non-optimized algorithm performs the test on each number, like the Sieve of Eratosthenes.

One particular optimization descends from the fact that all primes greater than 3 are of the form 6k ± 1, where k is any integer greater than 0. There is a famous Python algorithm that implements this optimization.

def is_prime(n: int) -> bool:
    """ Primality test using 6k+-1 optimization. """
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i ** 2 <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

In this post, I would like to translate this algorithm using a pure functional approach in Scala language.

Using Functional Programming we achieve some notable results:

• No side effects - if the code compiles, then it works
• Thread-safe and concurrency-safe
• Easier to reason about, because the function is algebraic
• Results can be combined - using pipelines

... and many others. (See this post if you want to learn more)

The algorithm above is not functional because the function is_prime is not pure. The reason is that it uses a variable (i) in a while loop.

To express the same algorithm as a pure function we need to eliminate all variables and use just constants. To do that, we use recursion.

This way, instead of storing the loop index (i) into the function, we pass it as a parameter to the function itself.

This is a first attempt.

def isPrime(n: Int, i: Int = 5): Boolean = {
    if (n <= 3)
        return n > 1
    if (n % 2 == 0 || n % 3 == 0)
        return false
    while (i * i <= n) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false
        return isPrime(n, i + 6)
    }
    true
}

As you can see, (i) is now an optional parameter of the function, and inside the while loop, the value of (i) is updated at every call.

To underline that (i) is an internal parameter and that the user should never supply it, we could use the implicit parameter group feature of Scala. In this way, we isolate the (i) parameter and make it clear that it is a parameter used only for recursion.

def isPrime(n: Int)(implicit i: Int = 5): Boolean = {
    if (n <= 3)
        return n > 1
    if (n % 2 == 0 || n % 3 == 0)
        return false
    while (i * i <= n) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false
        return isPrime(n)(i + 6)
    }
    true
}

This algorithm performs quite well, especially in multithreaded contexts.

The function above can be easily called like this:

println("Is 7669 prime? " + isPrime(7669))

You may find full source code in my GIT repo https://github.com/guildenstern70/PurePrimality

Comments

[Mark Lewis]

I would suggest that you not use math.pow to square things. Just do i*i instead of math.pow(i, 2). I expect that you will find it is much faster to run in addition to being shorter to type. As a general rule, using math.pow is inefficient for any small integer power. In this case, it is particularly bad because i is an integer and math.pow is working with doubles and the conversion from Int to Double also has a cost.

[Alessio Saltarin]

Done, thank you!

[Roberto Leibman]

I think a better practice would be to have an inner function (traditionally called loop), that way your caller doesn't need to know the dirty details of you using recursion. Also.... you probably want to add @tailrec, to make sure your function can be optimized by the compiler.

[Roberto Leibman]

Plus an implicit int is a really bad idea!

[Alessio Saltarin]

I am not sure the function is tail recursive...

[TH Lim]

The function is pure if it,

1. always return the same value for the same input
2. always accepts values and returns values
3. only uses the values from its parameters i.e. the function not use values or variables outside of the function. So, if the mutation happens inside the function and the variable localized within the function, the function is considered pure.