비트 시프트, 더하기 및 빼기 만 사용하여 로그 시간 복잡도로 정수 나누기를 구현하도록 요청 받았습니다.비트 시프트 더하기 및 빼기를 사용한 로그 시간 정수 나누기
저는 2의 제수 인 제수수를 어떻게 처리 할 수 있는지 알 수 있습니다. 그러나 시간이 대수적 인 채로 남는 이상한 약수를 어떻게 처리 할 수 있습니까?
심지어 가능합니까?
EDIT : 로그보다 작지만 선형보다 나은 시간 복잡성을 수행하는 방법도 환영합니다.
감사
그냥 종이에 있지만, 이진 나눗셈을하는 것과 같습니다. 분할 된 비트를 누산기로 옮겨서 적어도 제수와 같을 때까지 누산기에서 제수를 빼고 모든 비트를 모두 처리 할 때까지 계속 진행하면서 모든 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)입니다.
배당의 최상단 비트가 누산기의 하단으로 이동합니다. 결과는 배당/누적 기가 시프트 될 때마다 이동됩니다.
이것은 피제수의 비트 수가 아니라 피제수의 값에 대해 시간 대수입니다.
좋아요. 어셈블리에서 구현할 수 있었지만 제대로 작동하는 것 같습니다. 감사합니다. –
일반 경우 불가능합니다. 가장 잘 압니다. 나눗셈은 기껏해야 곱셈만큼 효율적일 수 있는데, 즉 O (M (n))의 시간 복잡도이고, Schönhage-Strassen에 기초한 곱셈은 복잡도 O (nlognloglogn)를 갖는다. 상수는 크기 때문에이 방법은 일반적으로 수천 비트의 피연산자에 대해서만 의미가 있습니다. 귀하의 질문은 이론적 인 질문입니까? 그렇다면 [Computer Science Stackexchange] (https://cs.stackexchange.com/)에 대한 질문을하는 것이 좋습니다. 실용적인 응용 프로그램 (유스 케이스)이 있다면 피연산자의 크기는 얼마입니까? – njuffa
안녕하세요, 그 어셈블리에서 운동. 아래에 제안 된 방법은 로그 시간이 있다고 생각합니다. –
아래의 해답에 설명 된 접근법에는 O (n)의 시간 복잡도가 있습니다. – njuffa