안녕 게이들아?
지난번의 카라추바 곱셈법에 이어서 이번에는 톰-쿡 알고리즘을 알아보려고해.
카라추바 곱셈법의 확장이 톰-쿡 알고리즘이라고 할 수도 있고,
톰-쿡 알고리즘의 특정한 케이스가 카라추바 곱셈법이라고도 할 수 있어.
뭐 같은 말이긴 하지만 말이야
0. 소개
톰-쿡 알고리즘은 Andrei Toom와 Stephen Cook이 만든 알고리즘이야.
근데 왜 이름이 Toom이노; 톰-쿡이든 툼-쿡이든 그냥 톰-쿡 알고리즘 합시다!
1963년에 톰이 처음 만들어냈고, 1966년에 쿡이 이를 업그레이드 시켰다고 한다.
카라추바가 1960년에 만들고 1962년에 논문냈는데 이랑 거의 비슷하노..
이 알고리즘은 큰 수를 여러 조각으로 쪼개서 곱셈을 하는 방법이다.
k개의 조각으로 나눈다고 하고, 이를 톰-k라고 부른다.
저번에 쓴 카라추바 곱셈법은 톰-2와 같다.
일반적으로 톰-k에서 k가 클수록 곱셈을 하는 데 소비하는 시간은 줄어들게 된다.
반면, 덧셈이나 행렬계산 등 기타 잡 연산들을 하는 데 소비하는 시간이 훨씬 많이 들기 때문에 오히려 전체 연산 시간은 늘어나게 된다.
그래서 k를 무작정 키운다고 좋은 건 아니고, 톰-3 정도가 적절하다.
a와 b를 곱할 때, a는 3조각으로 나누고, b는 2조각으로 나눌 수 있는데, 이 때는 톰-2.5 라고 한다. (평균낸다.)
전체적인 개념을 설명해주면, 한 수를 3조각으로 분해하는데, 이 3조각이 각각 방정식의 계수라고 생각하는거야.
그러면 2차 방정식이 두개 나오겠지? 곱하는 수가 2개니까.
그리고 이 2차 방정식을 두개 곱하면 4차 방정식이 나올거야.
여기의 계수는 총 5개가 필요하지.
그리고 이 5개를 적당히 위치 해서 다 더 해주면 된다. (아래서 자세히 서술)
그래서 결과적으로 9개의 곱셈이 필요한 것을 5개로 줄일 수 있다. 이기야!
톰-쿡 알고리즘은 크게 5단계로 이루어진다.
1. 분할 Splitting
2. 평가 Evaluation
3. 점별 곱셈 Pointwise multiplication
4. 보간 Interpolation
5. 재구성 Recomposition
1~5번은 알고리즘으로 순서대로 서술하겠다.
*참고사항 : 예시로 드는 수는 충분히 크지 않아서 톰-쿡 알고리즘이 비효율적일 수 있다.
1. 분할
a = 1234567891
b = 582736475
각각 10,9자리이다.
이 숫자를 어떻게 쪼개면 잘 쪼겠다고 소문이 나겠노?
먼저 a와 b를 로그 취한 것의 정수부분만 구한다.
오오미.. 슨상님 곱셈하는데 로그가 왠 말이노 ㅠㅠ
하지말고 그냥 쉽게 말하면 각 자리수에서 1씩 빼주면 된다.
즉, [loga] = 9, [logb]=8 이다.
여기서 k로 나눠준다. 우린 3조각으로 나눌꺼니까, 각각 9/3=3, 8/3=2.6이 된다.
이 둘을 버림한다. 3과 2가 나온다.
이 중에 큰 값을 고른다. (3)
그리고 1을 더해준다.
그래서 최종적으로 나온 결과는 4이다.
우리는 4자리씩 쪼개면 된다.
a = 12 3456 7891
b = 5 8273 6475
p(x)는 x진수로 된 수라고도 볼 수 있다.
x=1000=10^4을 대입해주면
p(x)=a, q(x)=b가 나올 것이다.
아하! 불알 탁!
그럼 p(x)q(x)에 x=10^4을 넣으면 a*b가 나오겠다는 것을 알 수 있겠지?
즉, 우리가 앞으로 궁금해야할 것은 4차함수인 p(x)q(x)의 계수들이다.
그런데 일반적으로 이걸 구하려면 계수가 3개씩 있으니 총 9번의 최대 4자리 끼리의 곱셈이 필요하다.
하지만 다른 좋은 방법이 있다.
그것은 바로 방정식 위의 점을 이용하는 것이다.
2. 평가
평가는 뭐냐하면 p(x), q(x)의 특정 x에서의 값들을 구하는 과정이다.
이걸 왜 구하냐면, 특정한 점 t에서 p(t)q(t)를 곱한 것은, r(x)=p(x)q(x)라고 할 때 r(t)의 값과 같기 때문이다.
이를 이용하면 r(x)의 계수들ㅇㄹ 구할 수 있다.
4차 방정식에는 계수가 5개 있으니까 5개의 계수를 결정하기 위해서는 5개의 점을 대입해보면 된다.
일반적으로 그 점들은 작은 정수들이 들어간다.
-2, -1, 0, 1, 2 같은 애들..
그런데 0,1,-1,-2만 이용하고 5번째 점은 그냥 최고차항의 계수를 쓰겠다. (표시는 무한대 기호로 표시한다)
수식 입력이 귀찮아서 그냥 위키피디아에서 수식 이미지 가져왔다.
p(∞)라고 표현된 것이 바로 최고차항의 계수이다.
위의 식들은 행렬로 표현하면 아주 편하게 계산할 수 있다.
이 때 편의를 위해 0의 0승을 그냥 1로 정의했다.
이 과정을 이용하면 x=0,1,-1,-2,∞일 때 p(x)와 q(x)의 값들을 구할 수 있다.
이 과정을 쉽게하려면 다음과 같이 하면 된다.
임시로 t라는 수를 하나 잡는다.
위와 같이 계산하면 약간의 계산 이득을 볼 수 있다.
이제 실제로 값을 구해보자.
음수도 나올 수 있다.
3. 점별 곱셈
이제 x=0,1,-1,-2,∞일 때 r(x)값을 구해보도록 하자.
오오미 이게 뭐시당가..
4~5자리수 곱셈이랑께!
x=s일 때, r(s)=p(s)q(s)의 값을 구하는 작업이다.
음수가 나오는 건 정상이다. 안나올수도 있고
이 부분이 시간이 제일 많이 걸린다고 한다.
카라츄바 곱셈법으로 하면 적절할듯!
4. 보간
2번의 평가 과정에서 2차 함수의 행렬을 구했듯이 이번에는 r(x)의 행렬을 구할 수 있다.
이의 역행렬을 취하면 보간행렬을 구할 수 있다.
보면 분수가 있어서 좀 더러워보이는데
생각해보면 처음에 두 2차 함수 곱해서 만든 4차 함수는 계수들이 당연히 정수들 아니겠노?
어차피 약분 될 애들이니까 걱정해줄 필요 없다.
k값에 따라서 이를 효율적으로 구하는 순서는 달라질 수 있지만, k=3일 때는 다음과 같은 순서로 하면 좀 빠르게 구할 수 있다.
끝이라고 적히지 않은 값들은 임시적으로 저장해놓는 값이다.
드디어 r(x)의 모든 계수를 구했다 이기야!
5. 재구성
이제 다 됐다
여기에 처음에 쪼개준 단위인 1000을 대입해보자.
이 결과는 계산기로 계산한 결과와 100% 일치한다.
분석해보면 고전적인 방법으로는 10*9=90번의 곱셈이 필요하다.
하지만 톰-3을 이용하면 5번의 4*4 곱셈이 필요한데, 4*4 곱셈은 카라추바 곱셈법(톰-2)를 이용하면 9회만에 수행 가능하다.
따라서, 3단계 점별곱셈에서 45회의 1의 자리 곱셈이 수행된다.
또한 2단계에서 2배를 해주는 과정이 필요하므로 2*5=10회 정도의 곱셈을 수행한다.
보간 과정에서 3회의 8자리 나눗셈이 필요하고, 1회의 2자리 곱셈을 수행했다.
이 외에 많은 덧셈과 뺄셈을 수행했다.
심심한 게이들은 저 수를 90회 곱해서 직접 더해보는 것과 톰-3을 이용해서 구해보는 두가지 과정을 해보면 재미있을 것 같다.
6. 물을 것 같은 질문
Q. 보니까 전혀 간단해보이지 않는다. 이게 어떻게 된 일이노?
A. 두 숫자가 충분히 크지 않다. 숫자가 존나 크다면 존나 편리함을 알 수 있을 것이다.
그리고 무엇보다 이것은 컴퓨터를 위한 알고리즘이지 사람이 쓰라고 있는 알고리즘이 아니다.
Q. 사람이 쓰지도 못할 거 왜 올리노?
A. 원리를 알아간다는 것은 행복한 일이다.
Q. 톰-3 이 외의 경우에는 어떻게 계산하나? (-2,-1,0,1,∞ 이 외의 값을 넣은 경우에는?)
A. 해당 값을 넣었을 때 나오는 관계식들을 행렬로 만들어 준 다음에 적당히 하면 역행렬을 만들 수 있다.
이건 k값이 같을 경우에는 항상 일정한 행렬이 나오니까 그냥 미리 만들어 놓은거 쓰자이기!
Q. 곱하는 두 수의 크기가 차이날 경우 어떻게 하나?
A. 만약 한 숫자는 100자리고 한 숫자는 30자리다. 이럴 경우에, 100자리짜리는 3조각으로 나누고 30자리짜리는 그냥 1조각으로 하면 된다. 이 때 톰-2의 방법으로 풀면 된다. 그런데 사실 한쪽이 1조각일 경우에는 고전적인 곱셈방법과 전혀 차이가 없으니 사용하지 않아도 된다.
Q. 4자리 수를 주어진 수에 따라 구했더니 한 조각이 2자리 수로 나오는데, 이러면 3조각이 아니라 2조각 밖에 안 생긴다 ㅠㅠ
A. 톰-쿡 알고리즘을쓰기에는 노무 작은 수다.
행렬 수식 출처 ; 위키피디아
나머지 수식은 Hanword로 직접 노가다해가면서 쳤다 ㅠㅠ
