2017-09-20 15 views
2

비트 시프트, 더하기 및 빼기 만 사용하여 로그 시간 복잡도로 정수 나누기를 구현하도록 요청 받았습니다.비트 시프트 더하기 및 빼기를 사용한 로그 시간 정수 나누기

저는 2의 제수 인 제수수를 어떻게 처리 할 수 ​​있는지 알 수 있습니다. 그러나 시간이 대수적 인 채로 남는 이상한 약수를 어떻게 처리 할 수 ​​있습니까?

심지어 가능합니까?

EDIT : 로그보다 작지만 선형보다 나은 시간 복잡성을 수행하는 방법도 환영합니다.

감사

+0

일반 경우 불가능합니다. 가장 잘 압니다. 나눗셈은 기껏해야 곱셈만큼 효율적일 수 있는데, 즉 O (M (n))의 시간 복잡도이고, Schönhage-Strassen에 기초한 곱셈은 복잡도 O (nlognloglogn)를 갖는다. 상수는 크기 때문에이 방법은 일반적으로 수천 비트의 피연산자에 대해서만 의미가 있습니다. 귀하의 질문은 이론적 인 질문입니까? 그렇다면 [Computer Science Stackexchange] (https://cs.stackexchange.com/)에 대한 질문을하는 것이 좋습니다. 실용적인 응용 프로그램 (유스 케이스)이 있다면 피연산자의 크기는 얼마입니까? – njuffa

+0

안녕하세요, 그 어셈블리에서 운동. 아래에 제안 된 방법은 로그 시간이 있다고 생각합니다. –

+0

아래의 해답에 설명 된 접근법에는 O (n)의 시간 복잡도가 있습니다. – njuffa

답변

1

그냥 종이에 있지만, 이진 나눗셈을하는 것과 같습니다. 분할 된 비트를 누산기로 옮겨서 적어도 제수와 같을 때까지 누산기에서 제수를 빼고 모든 비트를 모두 처리 할 때까지 계속 진행하면서 모든 shift w/oa 뺄셈에 대해 0을 기록하고 빼기를 할 때마다 1.

15/5 (1111/101) 
dividend accumulator result 
1111  0000  0 - can't subtract, shift 
1110  0001  0 - can't subtract, shift 
1100  0011  0 - can't subtract, shift 
1000  0111  0 - can subtract, set 1 
1000  0010  1 - can't subtract, shift 
0000  0101  10 - can subtract, set 1 
0000  0000  11 - we're done since we shifted 4 times 

답은 3 (11)입니다.

배당의 최상단 비트가 누산기의 하단으로 이동합니다. 결과는 배당/누적 기가 시프트 될 때마다 이동됩니다.

이것은 피제수의 비트 수가 아니라 피제수의 값에 대해 시간 대수입니다.

+0

좋아요. 어셈블리에서 구현할 수 있었지만 제대로 작동하는 것 같습니다. 감사합니다. –