0

I am using the below code to get the number of divisors for the given number as per this answer https://stackoverflow.com/a/110365/2610955. I calculate the number of times a prime factor is repeated and then increment each of them and make a product out of them. But the algorithm seems too slow. Is there a way to optimise the program. I tried with type hints but they don't have any use. Is there something wrong with the algorithm or am I missing any optimisation here?

(defn prime-factors
  [^Integer n]
  (loop [num n
         divisors {}
         limit (-> n Math/sqrt Math/ceil Math/round inc)
         init 2]
    (cond
      (or (>= init limit) (zero? num)) divisors
      (zero? (rem num init)) (recur (quot num init) (update divisors init  #(if (nil? %) 1 (inc %))) limit init)
      :else (recur num divisors limit (inc init)))))

(prime-factors 6)

(set! *unchecked-math* true)

(dotimes [_ 10] (->> (reduce *' (range 30 40))
                     prime-factors
                     vals
                     (map inc)
                     (reduce *' 1)
                     time))

Edit : Removed rem as its not needed in the final output

Community
  • 1
  • 1
xtreak
  • 1,376
  • 18
  • 42
  • 1
    I don't understand Clojure (or your algorithm), but what you seem to be trying to do is factorise an integer. This is considered a hard problem, and no algorithm that is polynomial in the number of digits is known for it (though it's not known to be NP-hard). Anyway, I think the fastest easy thing to do is just to generate a list of primes (e.g. with the Sieve of Eratosthenes) up to sqrt(input_number), and then do `x = input_number; i = 0; while (x > 1 && i < nPrimes) { if (x % primes[i] == 0) { x = x / primes[i]; is_a_factor(primes[i]); } else { i = i + 1; } } if (x > 1) { is_a_factor(x); }`. – j_random_hacker Jun 15 '16 at 13:16
  • @j_random_hacker I am not trying to generate all the divisors. I am trying to get the number of divisors which I hope is not np complete. I am using the algorithm in the linked answer. Calculating how many times a prime number is repeated as a factor. Keep dividing by 2 if fails then with 3 until number drops to zero. Keep a count of it and use it to calculate the number of divisors – xtreak Jun 15 '16 at 14:43
  • I've just looked at that linked question and found that the algorithm it descibes is wrong -- see my comment there for a counterexample. – j_random_hacker Jun 15 '16 at 15:00
  • I don't know if counting the number of divisors is solvable in time less than actually finding them, but the algorithm in the linked question (and my algorithm) do both. – j_random_hacker Jun 15 '16 at 15:02
  • @j_random_hacker Thanks. There is an implementation by ntalbs that uses sieve of primes for the divisors. I will take a look. – xtreak Jun 15 '16 at 19:27
  • 1
    One other little "trick", you can replace `#(if (nil? %) 1 (inc %))` with [fnil](https://clojuredocs.org/clojure.core/fnil) `(fnil inc 0)` which is shorter and, in my opinion, clearer. – Garrett Rowe Jun 15 '16 at 20:16

2 Answers2

2

Minor thing: use int or long instead of Integer as @leetwinski mentioned.

Major reason: It seems that you loop from 2 to sqrt(n), which will loop over unnecessary numbers.

Take a look at the code below: (This is just a dirty patch)

(defn prime-factors
  [n]
  (loop [num n
         divisors {}
         limit (-> n Math/sqrt int)
         init 2]
    (cond
      (or (>= init limit) (zero? num)) divisors
      (zero? (rem num init)) (recur (quot num init) (update divisors init  #(if (nil? %) 1 (inc %))) limit init)
      :else (recur num divisors limit (if (= 2 init ) (inc init) (+ 2 init))))))

I just replace (inc init) with (if (= 2 init ) (inc init) (+ 2 init)). This will loop over 2 and odd numbers. If you run it, you will notice that the execution time reduced almost half of the original version. Because it skip the even numbers (except 2).

If you loop over only prime numbers, it will be much faster than this. You can get the sequence of primes from clojure.contrib.lazy-seqs/primes. Though this contrib namespace has deprecated, you can still use it.

This is my approach:

(ns util
  (:require [clojure.contrib.lazy-seqs :refer (primes)]))

(defn factorize
  "Returns a sequence of pairs of prime factor and its exponent."
  [n]
  (loop [n n, ps primes, acc []]
    (let [p (first ps)]
      (if (<= p n)
        (if (= 0 (mod n p))
          (recur (quot n p) ps (conj acc p))
          (recur n (rest ps) acc))
        (->> (group-by identity acc)
             (map (fn [[k v]] [k (count v)])))))))

Then you can use this function like this:

(dotimes [_ 10] (->> (reduce *' (range 30 40))
                     factorize
                     (map second)
                     (map inc)
                     (reduce *' 1)
                     time))
ntalbs
  • 28,700
  • 8
  • 66
  • 83
  • Prime numbers are of the form 6k+1 or 6k-1. That will also reduce a lot of count. For 1000 numbers there are 500 odd numbers and 332 numbers of 6k+1 or 6k-1 form. Thanks for the insight – xtreak Jun 15 '16 at 19:25
1

you can increase the performance by using primitive int in loop. Just replace (loop [num n... with (loop [num (int n)...

for me it works 4 to 5 times faster

another variant (which is in fact the same) is to change the type hint in the function signature to ^long.

The problem is that the ^Integer type hint doesn't affect the performance in your case (as far as i know). This kind of hint just helps to avoid reflection overhead when you call some methods of the object (which you don't), and primitive type hint (only ^long and ^double are accepted) actually converts value to the primitive type.

leetwinski
  • 17,408
  • 2
  • 18
  • 42
  • Thanks. I might have numbers bigger than int so I have used BigInt. Does adding in BigInt give some speed? The number might have 20 digits – xtreak Jun 15 '16 at 08:31
  • Bigint probably would make it slower, for it doesn't have any primitive counterpart. – leetwinski Jun 15 '16 at 11:33