정수의 곱셈을 빨리하기 위한 방법 중의 하나로 기수법으로 표현된 정수를 여러 조각으로 분할하여 덧셈이나 뺄셈 회수는 몇회 증가하는 대신, 곱셈 횟수를 몇회 감소하는 방법입니다. 곱셈이 덧셈이나 뺄셈 보다는 시간이 많이 걸린다는 전제 하에 카라츄바 곱셈(Karatsuba multiplication)을 적용하면 시간복잡도 O(N**2) 의 계산 과정을 을 약 시간복잡도 O(N*&1.5)의 계산 과정으로 줄일 수 있습니다. (여기서 N은 기수법으로 표현된 정수의 분할 개수입니다.) 예를 들어 두 자리 십진법 수 23과 45의 곱셈 23*45을 생각해 봅니다. (이 경우 N = 2 입니다.) 2 3 x ) 4 5 ----------- 1 5 1 0 1 2 8 ----------- 1 0 3 5 위의 곱셈표에서 ..