#4-3-2 The Art of Computer Programming - 준수치적 알고리즘

이번 절은 나머지식 산술에 대한 내용이다.

 

공약수가 없는 여러 개의 수(소수 집합)들을 두고 직접 수를 다루지 않고 소수로 나눈 수들을 다루는 방법이다.

처음에 공약수가 없는 수라고 해서 뭔가 했음..

 

이렇게 표현하면 방법의 단점은

두 수를 비교했을 때, 어떤 수가 더 큰지 알 수가 없다. 이미 모듈러 연산을 했기 때문.

그리고 연산의 결과로 위 넘침이 발생한 지의 여부도 알기가 힘들다.

 

여러 연산들을 동시에 수행할 수 있는(병렬 연산이 가능한) 컴퓨터의 경우 덧셈, 뺄셈에서 나머지식 연산이 크게 유리하다.

서로 다른 법들에 대한 연산들을 모두 동시에 수행할 수 있기 때문이다.

 

중국인의 나머지 정리에 대해 소개한다. 내가 아는 손자병법의 손자인지는 모르겠지만.. 여하튼 손자라는 사람의 손자 산경에서 언급했던 내용이라고 한다.

 

특정 조건(계산의 상당 부분에 큰 정수들의 정확한 곱셈이 관여하고 덧셈과 뺄셈들도 나타나는, 그러나 나누기나 수 비교 또는 중간 결과가 범위 밖으로 '넘치는지'의 판정은 별로 필요하지 않은 부류의 응용들)에서 나머지 산술 방법을 이용하는 게 큰 이득이 될 수 있다는 게 이 절의 핵심 내용이다.