Multiplication of Large Integers (아주 큰 정수의 곱셈)

2.6 Arithmetic with Large Integer

---

2.6.2 Multiplication of Large Integers

굉장히 큰 정수의 곱셈은 어떻게 할까?

배열로 표현 한다.

n자리 정수의 곱 시간복잡도는? n자리 정수 2개 곱셈 = O(n^2)

---

그럼 Divide and conquer로 시간복잡도를 낮춰보자.

n자리 정수를 절반으로 나눠서 계산하자

m은 n자리 정수를 2로 나눈 값이다.

 

---

u와 v 는 n자리 정수이다. >>> integer 타입이 아니라 배열이다.

 

if ( u 나 v 가 0이면 ) : 곱이 0이니까 0이고

 

else if ( threshold보다 작다면 ) : u와 v를 그냥 곱한다.

 

else :

m은 n을 2로 나눈 값이고

divide는 나눈 몫을 나타낸다. 이때 divde는 배열을 나누는 것이다. 그냥 나누는것이 아닌 구현해야하는 function이다. 

rem은 나머지를 나타낸다. 

Divide (x, u, m)

 

시간 복잡도 -> master theorem 이용하기

 

naive랑 똑같이 나온다...

 

다른코드 써보자

---