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

## No comments:

Post a Comment