티스토리 뷰
지난 번 고대 이집트 곱셈법에 이어 이번에는 최초로 그냥 곱셈 계산보다 빠른 알고리즘인 카라추바 알고리즘에 대해 알아볼거야.
여기서는 "1자리 곱셈 수"가 줄어드는 것에 초점을 맞출거야.
고대 이집트 곱셈법에서도 구구단은 필요 없게 되었지만 2배 연산이 늘어나고 덧셈을 많이 해주어야 하는 단점이 있었지?
이처럼 카라추바 알고리즘도 1자리 곱셈수는 줄지만 덧셈과 뺄셈의 연산 수는 늘어날 수 있다는 점은 짚고 들어가자.
1. 서론
카라추바 알고리즘은 1960년에 발견되어서 1962년에 논문으로 나온 알고리즘이야.
카라추바라는 사람이 어떤 사람이 곱셈과 관련된 복잡도(연산이 반복되는 정도) 관련 세미나를 들으러 갔는데
세미나를 듣던 중에 부랄을 탁! 치면서 이 알고리즘을 생각해냈다고 해.
고전적인 곱셈법과 비교했을 때 계산이 얼마나 빠른 지 대충 설명해주면
약 1000자리 숫자를 연산하는데 고전적인 방법은 1000의 제곱, 1,000,000의 회의 1자리 곱셈이 필요하지만
카라추바 알고리즘을 이용하면 3^10=59,000번의 1자리 곱셈만 해주면 된다고 해.
고전곱셈법의 5.9% 밖에 안 씀 ㅍㅌㅊ?
2. 본론
먼저 두 숫자를 다음과 같이 쪼개.
아따 이 흉물스러운 것은 뭐시당가.. 슨상님 계실 적에는 이런 일이 없었는디..
B는 뭐고 m은 또 뭔지 갑자기 복잡해 보이지?
B는 진수의 밑이고 m은 적당한 수야. 일반적으로 n자리면 n/2를 m으로 잡는 게 가장 효율이 좋다고 한다.
그래도 복잡해보이는 느낌이 들지?
아주 쉽게 설명하면
1234라는 숫자가 있으면 그냥 x1=12, x0=34로 나누라는 이야기야
숫자를 반토막 내라 이기야!
그리고 다음을 구한다.
위는 이 식이 유도되는 과정도 같이 적은 것이다.
우리가 궁금한 것은 L,M,N이다.
그런데.. 저기서 필요한 곱셈은 총 4번으로 보인다.
L과 N을 구할 때 각각 1번, M을 구할 때 2번..
그렇다. 이렇게 계산을 하면 고전적인 방법과 전혀 다를 바가 없다.
그래서 다음과 같이 M을 구한다.
이제 M을 구할 때 곱셈은 한 번만 하면 된다.
우리는 이제 L,M,N만 구해주면 된다.
3. 예시
이제 실제 예를 통해서 더욱 자세히 이해해보자.
48과 53을 곱해보자.
먼저 2000과 400을 더해주고, 거기에 24를 더해준 다음에, 마지막으로 120을 더하면 2544가 나오게 된다.
이 때 필요한 1자리 곱셈은 총 4번, n의자리덧셈 3번.
이것을 카라추바 곱셈법으로 풀어보자.
L = 4*5=20
N = 8*3=24
M = 20+24-(4-8)(5-3)=20+24-(-8)=44+8=52
2024+520=2544
저 위의 짤은 카라추바 곱셈법을 더욱 쉽게 만들어 놓은 버전으로, 해석하면 다음과 같다.
1. 4*5를 앞에, 8*3을 뒤에 두면 2024가 나온다.
2. 2024의 뒤의 3자리를 더한다. 6
3. 2024의 앞의 3자리를 더한다. 4
4. 4-8=-4와 5-3=2를 곱한다. -8
5. 46에서 -8을 뺀다. (46에서 8을 더한다). 54
6. 천의 자리와 일의 자리는 2,4가 그대로 내려오고 중간 백, 십의 자리는 5에서 구한 54
처음에 2,3번 순서를 보고 이게 무슨 슨상 두부외상하는 소린가 했는데
위에서 정의한 M을 잘 생각해보면,
20과 24를 더해야한다.
이 때 십의 자리만 보면 2+2이고, 일의 자리만 보면 0+4이다.
그런데 이 때 십의 자리는 전체 곱셈 결과에서는 10의 자리에 해당한다. (M에는 B^m=10을 곱해줘야하니까)
따라서 2024의 백의 자리인 0을 M의 10의 자리에 더해주고
2024의 십의 자리인 2를 M의 1의 자리에 더해주는 것이다.
따라서 결론적으로는 앞의 세개를 더하고 뒤에 세개를 더하는 꼴이 되는 것이다.
그래서 1,2,3의 과정을 거치면 2464가 된다. 여기에 중간에 8(80)을 더해주면 최종값인 2544가 된다.
여기서는 계산을 각각 몇번씩 했는 지 세어보자.
1의 자리 곱셈 3번
1의 자리 덧셈 2+2+2(뺄셈)번
10의자리와 1의자리 덧셈 1번
1의 곱셈 3번, 덧셈 7번이 소요되었다. (만약 1~6의 단계를 거치지 않는다면 곱셈3번, 덧셈4번(뺄셈1번포함)이 될 것이다.)
앞의 고전적 곱셈방식은 1의 곱셈 4번, 덧셈 3번이 소요되었다.
두 자리 수에서는 별로 차이가 없어보인다.
만약에 자리수가 좀 늘어나면 어떻게 될까?
1234와 4321을 곱하는 것을 보도록 하자.
고전적인 방법으로 저 곱셈을 수행하려면 4*4=16번의 1자리수곱셈과 15번의 덧셈이 필요하다.
그러나, 카라추바 곱셈법을 이용하면
1. 12*43, 34*21 (각각 4번씩 - 곱셈 8번; 카라추바 사용시 곱셈 6번)
2. 16+7+14 (덧셈 2번)
3. 5+16+7 (덧셈 2번)
4. (12-34)(43-21)=-22*22 (뺄셈 2번, 1자리수곱셈 4번; 카라추바 사용시 곱셈 3번)
두자리수 곱셈을 고전적인 방법으로 한다면 1자리수 곱셈이 총 9번, 덧셈(뺄셈포함)은 18번 사용되었다.
기존의 곱셈16번, 덧셈15번 vs 곱셈9번, 덧셈18번
ㄷㅎ 아닌가?
4. 효율성
지금 작은 수를 해서 별로 효율적으로 느껴지지 않을 수 있다.
그러나 위 그래프를 보면, 9자리만 되어도 카라추바는 복잡도가 약 15정도인데 고전적인 방법은 약 80의 복잡도를 가져 카라추바가 20%정도의 복잡도를 가짐을 알 수 있다.
또한 자리수가 늘어날수록 그 격차는 기하급수적으로 늘어난다.
5. 결론
두자리수(ab*cd) 끼리 곱할 때
1. 십의자리 끼리 곱해서 백의 자리로 (L*100)
2. 일의자리 끼리 곱해서 일의 자리로 (N)
3. L+M-(a-b)(c-d) 해서 십의자리로 (M*10)
이러면 (L*100+N)+M*10 이 답이 된다.