왜 나누는 것보다 비용이 더 많이 드는가?

Question

저는 최근에 Vector 3 클래스를 작성했고, 친구에게 검토를 위해 normalize() 함수를 제출했습니다. 그는 그것이 좋다고 말했다. 그러나 CPU 시간에서 "곱하는 것이 나눈 것보다 쌉니다"때문에 가능한 한 상호성에 의해 곱해야합니다.

제 질문은 간단합니다. 이유가 무엇입니까?

Answer 1

하드웨어가 더 쉽게 구현할 수있는 기본 작업, 즉 더하기, 빼기, 이동, 비교 등을 생각해보십시오. 사소한 설정에서도 배수는 더 적은 기본 단계를 필요로합니다. 더하기, 더 빨라 진진 알고리즘을 제공합니다. 예를 들어 here을 참조하십시오. 그러나 하드웨어는 일반적으로 특수 하드웨어를 제외하고는이를 활용하지 않습니다. 예를 들어, 위키 피 디아 URL에 "Toom-Cook은 5 N 크기의 곱셈을위한 크기 N 승법 곱셈을 할 수 있습니다."- 매우 큰 수의 경우 꽤 빠릅니다 (Fürer의 알고리즘, 꽤 최근의 개발, 할 수있다 Θ(n ln(n) 2Θ(ln*(n))) - 다시, 위키 피 디아 페이지와 그곳에서 링크를 참조하십시오).

부서는 단지 더 천천히, 다시 - wikipedia; 최고의 알고리즘 (HW에 구현 된 알고리즘 중 일부는 곱셈을위한 최상의 알고리즘처럼 정교하고 복잡한 곳이 아니기 때문에) 곱셈에 대한 양초를 가질 수 없습니다.

엄청나게 큰 숫자의 문제를 정량화하기 위해 다음과 같은 결과가 gmpy이며 사용하기 쉬운 Python 래퍼 GMP을 사용합니다. 그리고 - 최고의 wheezes.

$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a*ib' 
1000000 loops, best of 3: 0.186 usec per loop 
$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a/b' 
1000000 loops, best of 3: 0.276 usec per loop 

보시다시피, 심지어는이 작은 크기 (숫자의 비트)의 수에, 정확히 같은 속도에 집착하는 사람들에 의해 최적화 된 라이브러리와 : 프로 느린 (첫번째 세대 ;-) 맥북에 역수에 의한 곱셈은 나누기에 소요되는 시간의 1/3을 절약 할 수 있습니다.

그것은이 몇 나노초는 생사의 문제가 있지만, 그들은 이을 때, 물론 당신이 반복적으로 동일한 값으로 나누어지는 경우 만 드문 경우에있을 수 있습니다합니다 (1.0/b를 멀리 법인에게 양도하는 작동!),이 지식은 생명을 구할 수 있습니다. 같은 맥락 훨씬

(-와 호너 scheme 다항식 계산을위한 광대 바람직 - x*x 종종 [파이썬 포트란처럼 ** "상향 전력"연산자가 언어] x**2가에 비해 시간을 절약 할 반복적 인 기상 레이더 작동! -).

Answer 2

(float) 나누기를위한 CPU 연산은 곱셈보다 훨씬 복잡합니다. CPU는 더 많은 일을해야합니다. 하드웨어에 대한 지식이 많지 않지만 일반적인 부서 구현에 대한 정보는 많이 있습니다 (예 : newton-raphson 알고리즘 기반).

또한 CPU 성능을 얻기 위해 항상 나눗셈 대신 역수를 곱하는 것에주의해야합니다. 정확히 동일한 결과를 제공하지 않을 수도 있습니다. 이는 귀하의 신청에 따라 중요 할 수도 있고 아닐 수도 있습니다.

Answer 3

초등학교로 돌아 가면 곱셈보다 곱셈이 어렵고 곱셈보다 더 어렵다는 것을 알 수 있습니다. CPU와 관련하여 상황이 다르지 않습니다.

역수계 계산에는 나눗셈이 포함되므로 역수를 한 번 계산하고 세 번 사용하지 않으면 속도가 올라가지 않습니다.