Karatsuba 알고리즘 v.s. "*" 운영자?

Question

오늘, 나는 Karatsuba 알고리즘, 빠른 곱셈 알고리즘에 대해 들어 봤다. 나는이 의미가 "빠름"을 의미하는 것이 궁금하다.

일반적으로 우리는 코드 조각의 시간 복잡도를 계산할 때 * 연산자를 사용하는 곱셈 연산을 고려합니다. 그리고 항상 참이면 점근 표기법과 관련하여 더 빠른 알고리즘은 어떻게 생깁니 까? 또는 Karatsuba 알고리즘이 유용 할 수있는 매우 큰 수로 수행 될 때 O (1)로 간주되어서는 안됩니까?

컴퓨터 수준에서 컴파일러는 항상 *에 대한 최적화를 수행합니다. 예를 들어, 비트 단위 연산을 사용하여 숫자에 2^n을 곱합니다. Karatsuba 알고리즘이 실제 실행 시간에서 * 걸릴까요?

Answer 1

고전 승산은 O (N 2^{) N가 승산되는 수의 자릿수이다. 일반 컴퓨터 코드를 측정 할 때 즉 O (1) (크기가 변경되지 않기 때문에)}

가되도록

, 당신은, 고정 크기 (일반적으로 32 비트 또는 64 비트) 숫자를 다루고있어 BigInteger를 다루기 시작하면 이것이 매우 중요합니다.

Answer 2

이 알고리즘은 긴 숫자에 속합니다. CPU의 레지스터 크기가 길어집니다. 이것은 위키 피 디아에서 온 것입니다 :

Karatsuba 알고리즘은 빠른 곱셈 알고리즘입니다. 1960 년에 Anatolii Alexeevitch Karatsuba에 의해 발명되었고 1962 년에 발표 된 것은 이었습니다. 두 개의 n 자리 숫자를 곱하여 최대 3 n^(log_2 3) = 3 n^1.585의 한자리 곱셈을 일반 적으로 줄일 수 있습니다. n이 2의 거듭 제곱 일 때 정확하게 n^(log_2 3).

Answer 3

이 질문의 문제점은 * 호출자는 알고리즘이 아니라는 것입니다. 그것은 컴파 일러 (또는 인터프리터)와 CPU의 조합을 통해 어떻게 답을 얻었는지를 결정했습니다.

내장 된 곱셈을 사용하는 것이 O (1)라고 주장하지만 입력에 제한이없는 한 사실 일 수는 없습니다 (N은 충분히 작아야합니다. CPU 레지스터에 맞춰 짐) 또는 룩업 테이블이 사용됩니다.

SLak는 CPU에서 (대부분의 CPU의 경우) 곱셈이 발생할 때 언급하므로 숫자는 항상 32 또는 64 비트의 동일한 크기입니다. 숫자 1은 하나의 비트로 표현 될 수 있지만, 여전히 32 비트의 공간을 차지합니다 (대부분의 구현에서)

Big-O 표기법은 입력의 크기가 더 작다는 것을 알려주며 효율적인 알고리즘 (Big-O 용어로)은 덜 효율적인 알고리즘보다 빠릅니다.

비트 시프트는 모든 임의의 곱셈에 적용될 수 없으므로 실제로 유용하지만 알고리즘 적으로는 2의 제곱에 곱하는 것에 만 적용되는 다른 방법과 비교할 수 있습니다.

대부분의 언어는 32 비트보다 큰 숫자를 처리하기위한 특수 유형이 있으며 *을 사용하여 곱하면 Karatsuba 알고리즘이 사용되고있을 수도 있습니다.