사칙연산을 빠르게 수행해보자

사칙연산은 모든 수학적 알고리즘의 기본이다.

그렇다면, 프로그래밍 언어들은 가장 빠른 알고리즘을 기본적으로 제공해줄까?

출처 - https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

위에서 보듯이 곱셈(Multiplication)과 나눗셈(Division)의 경우 다양한 알고리즘이 있다.

프로그램 언어들에서 제공해주는 +,-,*,/ 가 수행하는 알고리즘을 알아본 결과, JAVA와 C가 기본적으로 제공해주는 Multiplication 알고리즘은 O(n^2)인 Long multiplication을 사용하고 있다.

출처 - https://en.wikipedia.org/wiki/Multiplication_algorithm

일반적으로는 Long Multiplication 알고리즘을 사용했을 때, 다른 알고리즘들에 비해서 차이가 크진 않지만, 빅데이터와 같이 많은 곱셈이 필요할 때는 많은 차이를 보일 수 있다.

'구종만'씨 께서 지은 알고리즘 책에서는 50자리를 기준으로, 이보다 밑이면 Long Multiplication(기본제공)으로 하고, 이상이면 Karatsuba를 사용하기를 권장하고 있다.

출처 - 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 세트, 구종만