반응형
큰수표현
-
알고리즘: 큰 수의 곱셈 알고리즘(feat. c++ pseudocode )알고리즘 2020. 9. 27. 19:11
빅데이터 시대에서는 엄청나게 큰 숫자를 다루는 일이 존재한다. 하지만 자료형들은 수를 담을 수 있는 한계가 존재하고 배열로 표현함으로써 더 큰 정수를 표현할 수 있다. 예를 들어, S[5]S[4]S[3]S[2]S[1] = 92420로 표현할 수 있다. 이런 방식으로 표현한다면 표현하지 못할 수는 없다. 하지만 큰 수만 표현할 수 있으면 뭐하냐 효율적으로 연산이 가능해야 한다. 큰 수의 덧셈뺄셈은 많은 시간복잡도를 잡아먹지는 않지만, 곱셈의 경우에는 단순한 방법으로 quadratic-time algorithm(두개의 반복문)을 이용하여 곱셈으로 자릿수를 표현하면 시간복잡도는 다음과 같다. 하지만 이보다 더 좋은 큰자리수 곱셈알고리즘이 존재한다. 분할정복으로 이 보다 더 좋은 차수의 큰 정수 곱셈을 만들어보..