99 Clojure Problems – 37/38: Calculate Euler's Totient Function phi(m) (Improved)

See problem P34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem P36 then the function phi(m>) can be efficiently calculated as follows: Let [[p1, m1], [p2, m2], [p3, m3], ...] be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula: $$\varphi(m) = (p_1-1) p_1^{(m_1-1)} (p_2-1) p_2^{(m_2-1)} (p_3-1) p_3^{(m_3-1)} \ldots $$

I combined this with the next problem: P38 (*) Compare the two methods of calculating Euler's totient function. Use the solutions of problems P34 and P37 to compare the algorithms. Try to calculate phi(10090) as an example.

Example

(deftest p37-totient-improved
  (is (= 144 (fast-totient 315))))

The output of comparing the two functions using the criterium benchmarking library looks like this on my machine (running it in a REPL):

Benchmarking the original approach

Evaluation count : 13200 in 60 samples of 220 calls.
             Execution time mean : 4.661557 ms
    Execution time std-deviation : 111.338965 µs
   Execution time lower quantile : 4.577765 ms ( 2.5%)
   Execution time upper quantile : 4.905024 ms (97.5%)
                   Overhead used : 130.196103 ns

Found 5 outliers in 60 samples (8.3333 %)
 low-severe  2 (3.3333 %)
 low-mild  3 (5.0000 %)
 Variance from outliers : 11.0453 % Variance is moderately inflated by outliers

Benchmarking the product based algorithm

Evaluation count : 1510020 in 60 samples of 25167 calls.
             Execution time mean : 39.865790 µs
    Execution time std-deviation : 463.957713 ns
   Execution time lower quantile : 39.517915 µs ( 2.5%)
   Execution time upper quantile : 40.800218 µs (97.5%)
                   Overhead used : 130.196103 ns

Found 4 outliers in 60 samples (6.6667 %)
 low-severe  2 (3.3333 %)
 low-mild  2 (3.3333 %)
 Variance from outliers : 1.6389 % Variance is slightly inflated by outliers

Solution

The given formula follows from Euler's product formula. Translating the formula into Clojure is pretty straightforward. We can reuse the result from P36 and reduce the resulting map of prime numbers and their multiplicity by plugging in the product formula directly as the reducer function.

If you look at the code you will find that there is some additional "key/val-noise" due to the fact that we are getting a map back from the function calculating the multiplicities.

Running the benchmarks shows that this solution is about two orders of magnitude faster than the original solution based on the divisor sum and using Clojures ratio datatype.

There is a precondition though: The prime numbers have to be precalculated. If you have to calculate the prime numbers on the fly the product formula approach is only one order of magnitude faster:

Evaluation count : 259980 in 60 samples of 4333 calls.
             Execution time mean : 233.261376 µs
    Execution time std-deviation : 13.268456 µs
   Execution time lower quantile : 218.678716 µs ( 2.5%)
   Execution time upper quantile : 262.518850 µs (97.5%)
                   Overhead used : 131.115424 ns

Found 2 outliers in 60 samples (3.3333 %)
 low-severe  2 (3.3333 %)
 Variance from outliers : 41.8220 % Variance is moderately inflated by outliers

Read more about this series.