모듈로 알고리즘 생성

Question

좋아이 내가 내 머리를 wracking 봤는데 숙제 질문에 대한

입력에이 n 비트 길이와 b < 경우 B, A를의 정수 알고리즘을 표시하는을 계산 모드 B는 O (N^2)에

나는 다음과 같은 알고리즘 왔어요 내가 바른 길에있어 경우에 궁금 :

modulus(a,b) 
c = a-b; 
modulus (c,b) 
result c; 

것은이 올바른 것입니까? 아니면 너무 직관적으로하고 있습니까? 어떤 팁?

의사 코드로 알고리즘을 작성하려고했습니다. 그렇습니다. modulus 구현에 대해 묻습니다.

Answer 1

mod b를 계산하려면 결과가 b보다 작을 때까지 a에서 b의 배수를 빼야합니다. 간단하게하기 위해 a> = 0, b> 0이라고 가정하겠습니다.하지만 mod-a, b = mod (a, -b) = -mod (a, b) 서명 한 사례.

mod을 구현하는 가장 순진 (하지만 비효율적 인) 방법은 이것이다 :

def mod(a, b): 
    while a >= b: 
     a -= b 
    return a 

a가 b보다 훨씬 큰 경우이 끔찍한입니다. 복잡도는 최악의 경우 O (2^n) 인 O (a/b)입니다. 여기서 n은 비트 수입니다. 대신, 우리는 b의 큰 배수를 뺄 수 있습니다. 우리는 이것을 비트 이동으로 할 수 있습니다.

def mod(a, b): 
    bs = b 
    while bs <= a: 
     bs <<= 1 
    while bs > b: 
     bs >>= 1 
     if a >= bs: a -= bs 
    return a 

이 코드에서, 우리는 변수 b에서 b가 a보다 커질 때까지 왼쪽으로 계속 이동합니다. 한 번에 한 걸음 씩, 우리는 그것을 b로 되돌려 놓고, 가능한 경우 a에서 값을 뺍니다. 이것은 본질적으로 바이너리로 긴 나누기 구현입니다.

시간 복잡도는 다음과 같습니다. 왼쪽 시프트는 O (n)입니다 (여기서 n은 비트 수입니다. 임의의 큰 숫자를 처리한다고 가정). 비교 및 ​​뺄셈입니다. 따라서이 구현에서 두 루프 모두 while이 필요에 따라 O (n^2)가됩니다.