우선 가우스 정수는 아래와 같이 정의됩니다.
Definition. (Gaussian Integer) 두 정수 a, b에 대하여, 복소수 a + bi를 가우스 정수라고 한다. |
Definition. (Divisibility) 두 가우스 정수 z, w에 대하여, w가 0이 아니고 z/w가 가우스 정수이면 z는 w로 나누어 떨어진다고 한다. |
가우스 정수는 유클리드 정역입니다.
제가 하고 싶은 건 두 가우스 정수 z, w(!=0)을 입력받아 z가 w로 나누어 떨어지는지 확인하는 코드를 짜고 싶었습니다. 우선, 효율보다는 확실한 해답을 하나 찾아봤습니다. python으로 구현했는데 필요없는 부분은 생략하고 아이디어를 적자면 다음과 같습니다.
class GaussInt: def __init__(self, real, imag): self.real = real; self.imag = imag def real(self): return self.real def imag(self): return self.imag def __add__(self, r): return sum of self and r(int or GaussInt) def __mul__(self, r): return product of self and r(int or GaussInt) def __abs__(self): return Taxi norm of self i.e. abs(self.real()) + abs(self.imag()) def IsDivisibleBy(self, r): M = abs(self) for C s.t. abs(C) <= M: if self = C * r: return True return False |
다만 당연히 모든 경우의 수를 체크하고, 그 때마다 곱셈 계산하고 비교하고 하다보니 느립니다. 조금 더 효율을 높일 수 있는 방법이 있을까요?