41 lines
1.5 KiB
Clojure
41 lines
1.5 KiB
Clojure
(ns test-p.core
|
|
(:require [clojure.math.numeric-tower :as math]))
|
|
|
|
(defn extended-gcd
|
|
"The extended Euclidean algorithm
|
|
Returns a list containing the GCD and the Bézout coefficients
|
|
corresponding to the inputs. "
|
|
[a b]
|
|
(cond (zero? a) [(math/abs b) 0 1]
|
|
(zero? b) [(math/abs a) 1 0]
|
|
:else (loop [s 0
|
|
s0 1
|
|
t 1
|
|
t0 0
|
|
r (math/abs b)
|
|
r0 (math/abs a)]
|
|
(if (zero? r)
|
|
[r0 s0 t0]
|
|
(let [q (quot r0 r)]
|
|
(recur (- s0 (* q s)) s
|
|
(- t0 (* q t)) t
|
|
(- r0 (* q r)) r))))))
|
|
|
|
(defn chinese_remainder
|
|
" Main routine to return the chinese remainder "
|
|
[n a]
|
|
(let [prod (apply * n)
|
|
reducer (fn [sum [n_i a_i]]
|
|
(let [p (quot prod n_i) ; p = prod / n_i
|
|
egcd (extended-gcd p n_i) ; Extended gcd
|
|
inv_p (second egcd)] ; Second item is the inverse
|
|
(+ sum (* a_i inv_p p))))
|
|
sum-prod (reduce reducer 0 (map vector n a))] ; Replaces the Python for loop to sum
|
|
; (map vector n a) is same as
|
|
; ; Python's version Zip (n, a)
|
|
(mod sum-prod prod))) ; Result line
|
|
|
|
(def n [3 5 7])
|
|
(def a [2 3 2])
|
|
|
|
(println (chinese_remainder n a))
|