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.

99 Clojure Problems – 36: Determine the Prime Factors of a Given Positive Integer (2)

Construct a list containing the prime factors and their multiplicity. Alternately, use a map for the result.

Example

(deftest p36-prime-factors-multiplicity
  (is (= {3 2, 5 1, 7 1} (prime-factors-multiplicity 315) )))

Solution

If you have been following this series this problem might sound familiar. In fact it is just a slight variation on the combination of Problem 35 (prime factors) and Problem 10 (run-length encoding). I followed Phil Gold in using a map as the output format to make the problem a bit more interesting.

While you could reimplement the solution from scratch, I think it is good practice to reuse existing code. In this case all we have to do is call prime-factors on the input, run-length encode, reverse the individual pairs of primes and their multiplicity as required by the problem description. Turning it into a map is then just a matter of flattening the result and applying the assoc function to an empty map and our intermediate result. Try it yourself before you look at the code.

Read more about this series.