lcm.clj

(ns lcm.core)
;; Finding the least common multiplier for a list of numbers
;; Reference material
;; https://en.wikipedia.org/wiki/Least_common_multiple
;; https://en.wikipedia.org/wiki/Euclidean_algorithm
;; https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/
;; https://octave.sourceforge.io/octave/function/lcm.html

(defn bigint-gcd ^long [^long a ^long b]
      (.longValue (.gcd (BigInteger/valueOf a) (BigInteger/valueOf b))))

(defn euclid-gcd [^long a ^long b]
      "Simple eclidean gcd https://en.wikipedia.org/wiki/Euclidean_algorithm"
      (loop [a' (long (max a b)) b' (long (min a b))]
            (if (zero? b')
              a'
              (recur b' (mod a' b')))))

(def ^:dynamic *gcd* euclid-gcd)

(defn lcm
      ([])
      ([^long a ^long b]
       (* a (/ b (*gcd* a b))))
      ([ls]
       (reduce lcm ls)))


(comment
  ;; Incomplete Proof of LCM applies to a list
  ;; if  P = lcm(a, b)
  ;; then if we factorise a into a_1 * a_2 = a
  ;;      a_1 and a_2 are both multiples of a and therefore a multiple of P [basic number theory]
  ;;      The same can be said for b
  ;;      If P is the LCM for a and b, then it is also the LCM for [a_1, a_2, a, b]
  ;;      If a new list is made [a_1, a_2, a, b, c] then P may not be the LCM for this list
  ;;      if a new LCM is calculated P2 then [a_1, a_2, a, b, c] are by definition a multiple of P2.
  ;;

  (lcm [])                                                  ;=> nil
  (lcm [10])                                                ;=> 10
  (lcm [2 4])                                               ;=> 4
  (lcm [3 7])                                               ;=> 21
  (lcm [2 4 10])                                            ;=> 20
  (lcm [15 2 4])                                            ;=> 60

  (binding [*gcd* bigint-gcd]
           (lcm [10 11 3 4 5]))


  )

note that performance can be improved by

• instead of using reduce use a loop recur on primitives
• adding type annotations
• using a faster implementation on gcd, either the binary implementation with shifts or something already implemented in fortran or c, https://docs.octave.org/doxygen/4.2/d3/d77/gcd_8cc_source.html.