곱셈 연산 시간의 비교

Question

a, b를 n 자리의 두 정수로합시다. a의 사각형의 계산 시간이 a * b보다 짧다는 것이 궁금합니다.

도움 주셔서 감사합니다.

Answer 1

x86에서 IMUL을 사용하지 않고 A를 정사각형으로 표시하는 방법이 없다고 생각합니다. 내가 틀렸을 수도있다.

걸리는 시간을 확인하려면 마이크로 벤치 마크하세요!

편집 : 오, 잠깐! b는 2 개의 메모리 읽기를 취하고 a는 1을 취합니다! 따라서 a *는 더 빠릅니다 :-).

진실한 대답 : 물건에 영향을 미치는 외부 요인이 없으면 a * b가 느려질 이유가 없습니다.

Answer 2

the benchmarks in Bentley's "Programming Pearls"을 살펴보면 측정 할 수있는 부분을 해킹 할 수 있습니다.

Answer 3

나는 당신의 질문은 가정

는 *하는하자 B는 n 개의 숫자와 두 개의 정수합니다. 나는 a의 제곱을 계산하는 계산 시간이 a * b를 계산하는 계산 시간보다 짧 으면 궁금합니다. *

n이 큽니다. 하나의 곱하기 명령어 만 사용할 수 없을 정도로 커지면, know는 두 요소가 동일하다는 사실을 이용할 수 있습니다. 학교에서 배운 알고리즘에 대해서는 사실입니다. 숫자 쌍의 곱의 거의 절반이 곱해질 필요가 없기 때문입니다. 매우 큰 n의 극단에서 FFT와의 컨볼 루션을 사용하면 두 요소에 대한 FFT는 제곱에 대해 동일하며 한 번만 계산해야합니다.