[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/5LUl9JTa    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Aug 24:
; chinese remainder theorem

(define (euclid x y)
  (let loop ((a 1) (b 0) (g x) (u 0) (v 1) (w y))
    (if (zero? w) (values a b g)
      (let ((q (quotient g w)))
        (loop u v w (- a (* q u)) (- b (* q v)) (- g (* q w)))))))

(define (inverse x m)
  (if (not (= (gcd x m) 1))
      (error 'inverse "divisor must be coprime to modulus")
      (call-with-values
        (lambda () (euclid x m))
        (lambda (a b g) (modulo a m)))))

(define (chinese-remainder as ms)
  (let ((p (apply * ms)))
    (define (f a m)
      (let* ((t (/ p m)) (b (inverse t m)))
        (* a b t)))
    (modulo (apply + (map f as ms)) p)))

(display (chinese-remainder '(10 4 12) '(11 12 13))) (newline)


Output:
1
1000


Create a new paste based on this one


Comments: