gerritjvv · August 22, 2022 23:06 · gerritjvv · Aug 22, 2022
diff --git a/lcm.clj b/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]))


  )
	(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]))


	)
No results found