August 27, 2010
The solution is easily computed by the Chinese remainder theorem, which states that given a set of positive, pairwise coprime moduli mi, 1 < i < r with product p = m1 · … · mr and corresponding residues ai mod mi, then the r relations n ≡ ai mod mi have a unique solution computed as the sum over r of ai · vi · pi modulo p, where pi = p / mi and the vi are the inverses vi · pi ≡ 1 (mod mi).
Here is our version of the calculation:
(define (chinese-remainder as ms)
(let ((p (apply * ms)))
(define (f a m)
(let* ((v (/ p m)) (b (inverse v m)))
(* a b v)))
(modulo (apply + (map f as ms)) p)))
The Chinese general had a thousand troups:
> (chinese-remainder '(10 4 2) '(11 12 13))
In testing this program, there were some calculations that failed with a divide-by-zero error. The problem arose in a modular inverse function that was stolen from a leading textbook. The book clearly states that the modulus need not be prime, as indeed it will not be in some uses of the Chinese remainder theorem, but in fact that is incorrect, and in that version of the modular inverse function the modulus must indeed by prime. The textbook authors were aware of the error, and noted the error in the errata on their website. Unfortunately, that algorithm was used in several exercises on Programming Praxis, including all recent uses of the
prime? function, all of which will have to be modified to use the correct modular inverse function. This is, of course, a strong reminder that borrowing code or algorithms, even from a trusted source, makes the code or algorithm your own, and you, not the original author, bear responsibility for any errors that appear.
Pages: 1 2