빠른 모듈로 연산

- 난이도: 다이아몬드 5
- 기본 문제: 17467

일반적인 CPU 구조에서 모듈로 연산을 처리하는 것은, 다른 연산들 (덧셈,뺄셈,곱셈,비트연산)에 비해서 매우 느리다. 그래서 모듈로 연산을 회피하는 것이 성능 향상에 중요하다.
간단하고도 널리 알려진 방법은 모듈러스가 2의 거듭제곱꼴일때, 모듈로 연산을 비트 연산으로 대체하는 방법이다.
그것보다는 좀더 복잡하지만, 일반적인 모듈러스 값에 대해서도 모듈로 연산을 다른 연산들로 대체하는 방법들이 있다.
모듈러스가 상수인 경우(컴파일 타임에 값을 알수 있는 경우) 에는 컴파일러가 알아서 나눗셈이나 모듈로연산을 최적화된 연산으로 대체해준다
- 참고: https://modoocode.com/313
하지만, 모듈러스 값이 런타임에 주어지는 경우에는 이렇게 컴파일러가 알아서 최적화시켜줄수는 없는데, 이때 컴파일러가 해야 할 작업을 우리가 직접 코드로 구현해줄 수 있다.
잘 활용하면 상당한 속도 향상을 얻을 수 있지만, 이것은 상수최적화에 가까운 영역이지 이론적인 시간복잡도가 향상이 되는 것이 아니라서, PS에서는 보통 잘 다뤄지는 내용은 아니다.
- 그래서 방법 자체는 그렇게 어렵지 않은 데에 비해서, PS에서는 잘 알려지지 않았었고, 그래서 기본 난이도가 실제 난이도 보다 높게 측정되어 있다
그리고, Python에서는 이러한 기법들이 실제 속도향상에 도움이 되지 않는다.
- Python에서는 애초에, 나머지 연산이 비트연산이나 덧셈 등과 비교해서 속도 차이가 크지 않다. 실제 연산에 걸리는 시간보다, 값을 참조해서 가져오고 하는 오버헤드가 훨씬 크기 때문에, 실제 연산의 시간 차이는 전체 시간에서 별로 비중이 크지 않다.
- 따라서, 연산 종류에 관계 없이 그냥 연산 횟수가 늘어나면 시간도 더 늘어난다고 생각하는 것이 편하다..
알려진 알고리즘은 Barret reduction과 Montgomery reduction이 있다.
공통적으로 모듈러스 값이 고정되어 있는 상황에서 반복적으로 모듈로 연산을 할때 효율적이다.
- Barret reduction은 그냥 x%n 을 구할때 쓴다
- Montgomery reduction은 (a*b)%n 을 구할때 쓴다.

Barret reduction

빠른 모듈로 연산
참고
- https://www.nayuki.io/page/barrett-reduction-algorithm
x % n 을 비트 쉬프트, 뺄셈, 곱셈만을 이용해서 계산해준다
모듈러스 n에 대해서 미리 전처리가 필요하다.
모듈러스 값이 고정된 상황에서, 반복적으로 모듈로 연산을 할 경우에 효율적이다.

로직을 파이썬으로 옮기면 이런식이다

def mod_func(mod):
    def mod_m(n):
        t = n - ((n * r) >> shift) * mod
        return t if t < mod else (t - mod)

    shift = mod.bit_length() * 2
    r = (1 << shift) // mod
    return mod_m

이 함수를 이용해서 n! % P 를 계산하는 예시는 다음과 같다

def factorial_mod_p(n, p):
  ret = 1
  mod_p = mod_func(P)
  for i in range(1, N + 1):
    ret = mod_p(ret * i)
  return answer

하지만 위에서 말했듯이, Python에서는 이 방식을 사용하면 더 느려진다.
- N<P≤10^8 에 대해서 N! % P를 구하는 17466 문제에 적용했을때, 그냥 % 연산자를 사용하는 나이브한 방식으로는 PyPy3 기준 1864ms에 통과했지만, Barret reduction 을 이용했을 때에는제한시간 3초를 초과해서 TLE가 되었다.

Montgomery reduction

빠른 모듈러 곱셈
참고
- Montgomery modular multiplication
- https://www.nayuki.io/page/montgomery-reduction-algorithm
ab % n 을 빠르게 계산해준다
(a,n)와 (b,n)을 몽고메리 폼으로 바꾸는 전처리가 필요하다. 결과도 몽고메리 폼으로 나오기 때문에, 다시 정수형으로 변환하는 후처리가 필요하다.
a, b값이 계속 바뀔 경우에는 매번 전처리를 해줘야 하므로 Barret reduction 보다 비효율적이다.
모듈러스 값이 고정되어있고, 몇몇개의 정해진 값만 연쇄적으로 곱하는 경우에 효율적으로 사용할수 있다. 대표적인 경우는 거듭제곱 연산이다.
Python에서는 Barret reduction과 같은 이유로 속도가 더 느려질 것이다. 그래서 구현도 해보지 않았다.

목차

빠른 모듈로 연산

Barret reduction

Montgomery reduction