#4-3-3 The Art of Computer Programming - 준수치적 알고리즘

이번 절은 '곱셈을 어느 정도까지 빠르게 할 수 있을까?'에 대한 내용이다.

 

m자릿수에 n자릿수를 곱하는 데에는 약 cmn회의 연산이 필요하다(c는 상수)

m을 n이라 가정했을 때는 n제곱에 따른 알고리즘 수행 시간이 필요하다.

 

1. 계수적 방법들 : 최상위 절반, 최하위 절반을 활용하여 연산

2. 나머지식 방법 : 나머지식 산술을 이용해서 큰 수를 빠르게 곱함

3. 이산 푸리에 변환 :  합성곱을 구할 때 푸리에 변환을 사용

4. 나눗셈 : 나눗셈도 곱셈처럼 빠르게 수행할 수 있으며, '뉴턴 법'을 사용한다.

5. 실시간 곱셈 : n제곱의 규모에서 n번으로 수행 시간을 줄이는 방법.

 

여러 방법이 소개되는데.. 읽어보기에는 너무 어렵다 ㅠㅠ

수식 지옥이다. 으어어어

그래도 오늘 하고자 한 양만큼을 읽었으니 됐다! 한 번에 다 이해 못할 수도 있지 뭐~