두 숫자를 나눌 시간 복잡도는 무엇입니까?

Question

두 개의 숫자 a와 b (a> b)가 있다고 가정하고 a를 b로 나눈다면 (즉 a/b를 계산하십시오). 얼마나 시간을 드릴까요?

글쎄, 사람들은 아키텍처뿐만 아니라 명령어 세트에 대해서도 의견을 말하고 있습니다. 그래서 여기에 가정이 있습니다.

a와 b가 각각 두 비트의 정수이고 n 비트가 있고 표준 명령 세트가있는 표준 x86_64 시스템이 있다고 가정합니다.

Answer 1

그냥 링크가 아닌 대답을 제공하라는 요청이 있었으므로이 질문에 답변 할 것입니다. 위 ph에서 지적한 것처럼 https://en.wikipedia.org/wiki/Division_algorithm#Newton.E2.80.93Raphson_division에 좋은 링크가 있습니다.

나누기는 계산 복잡성 이론에 관한 한 곱셈보다 비용이 많이 들지 않는 여러 연산 중 하나입니다. 이것에 대한 이유 중 하나는 계산 복잡성 이론은 알고리즘의 비용이 커지면서 알고리즘의 비용이 어떻게 증가하는지에 대해서만 염려합니다.이 경우에는 다중 정밀도 분할을 의미합니다. 또 다른 하나는 펜 - 앤드 - 페이퍼 긴 분할보다 더 빠른 분할 알고리즘이 있다는 것입니다.이 알고리즘은 사실 컴퓨터 하드웨어의 설계에 영향을 줄만큼 훌륭합니다. 유명한 예가 Cray-1 역수 반복과 펜티엄 버그입니다.

나누기를 수행하는 가장 빠른 방법은 by로 나누는 대신 a에 1/b를 곱하여 문제를 상호 역수로 줄이는 것입니다. 1/b를 계산하려면 우선 2의 거듭 제곱으로 문제의 크기를 조정하여 [1, 2]의 범위에서 b를 얻고, 일반적으로 룩업 테이블에서 대답을 추측합니다. - Pentium 버그는 조회 테이블. 이제 많은 오류에 대한 답을 얻을 수 있습니다. 1/b + x가 있습니다. 여기서 x는 오류입니다.이 오류는 사용자에게 알려지지 않았지만 조회 테이블이 적당한 크기 인 경우 작습니다.

방정식을 풀기위한 Newton-Raphson 반복 이론은 c = 1/b + x가 1/b에 대한 추측이면 c (2-bc)가 더 나은 추측임을 알려줍니다. c = 1/b + x 인 경우, 일부 대수는 더 나은 추측이 1/b-bx^2로 작동한다는 것을 알려줍니다. 오류 x를 제곱하고, x가 작기 때문에 (처음에는 0.1이라고 가정) 올바른 비트 수를 대략 두 배로 늘 렸습니다.

이 작업을 수행 할 때마다 올바른 비트 수를 두 배로 늘리므로 충분한 답변을 얻는 데 많은 시간이 걸리지 않습니다. 어쨌든 각 반복은 근사치 일 뿐이므로 근사치가 제공하는 정확도로 계산하면됩니다. 원하는 정확도의 정확도는 아닙니다. 근본적인 작업의 대부분은 c (2-b)의 곱셈이며 작업하는 정확도 비트 수가 선형보다 빠르게 증가합니다. 당신이 앉아서 이것 모두의 비용을 계산할 때, 당신은 그것이 1 = 1/2 + 1/4 + 1/8 +와 같은 합계를 얻는 숫자의 수와 함께 충분히 빨리 성장한다는 것을 알게됩니다. - 용어가 많지만 처음부터 그리 멀지 않은 답변에 수렴 - 다중 정밀도 나누기의 비용은 다중 정밀도 곱셈의 비용보다 일정한 요소보다 크지 않습니다.