최신 과학 지식을 접하는
가장 똑똑한 방법!

[주말N수학] 큰 수 곱셈을 빠르게 하는 법

2019년 05월 11일 08:00

이미지 확대하기

 

12+23을 계산할 때는 2+3=5를 먼저 계산하고, 1+2=3을 구해 35라는 답을 찾습니다. 즉 한 자리 숫자 덧셈을 2번 합니다. 물론 12+29처럼 받아 올림이 있는 경우는 조금 더 계산합니다. n자리 숫자의 덧셈은 받아 올림을 빼고 생각하면 많아야 2n번 계산하면 됩니다. 받아 올림까지 고려해도 넉넉잡아 3n번이면 충분합니다. 


하지만 곱셉의 경우는 좀 다릅니다. 예를 들어 12×23은 2×3, 1×3, 2×2, 1×2 이렇게 4번을 곱해야 합니다. 그 후 36과 240을 더해서 구합니다. 이 방법대로라면 한 자릿수 곱셈을 4번 한 다음 덧셈을 해서 구할 수 있습니다. 만약  n자릿수 2개를 곱한다면 한 자릿수 곱셈을 n²번이나 하게 됩니다. 즉 이 방법으로 n자릿수 2개를 곱하는데 걸리는 시간은 n²에 비례해 늘어납니다.

 

자연수의 곱셈을 다항식 곱셈으로


곱셈을 더 빠르게 하는 방법도 있습니다. 러시아의 유명한 수학자 안드레이 콜모고로프는 1960년 러시아 모스크바국립대에서 열린 세미나에서 n²보다 빠른 곱셈 방법에 대해 질문했습니다. 


그런데 당시 학생이었던 아나톨리 알렉세예비치 카라추바가 단 1주일 만에 n²보다 빠른 방법을 찾았습니다. 콜모고로프는 너무 기뻐서 카라추바의 결과를 여러 곳에 알렸고, 1962년 저자를 카라추바로 한 논문을 직접 써서 러시아 과학한림원에서 만드는 학술지에 출판했습니다. 카라추바는 한림원에서 보내온 저자용 논문 인쇄본을 보고 나서야 자기 이름으로 논문이 나온 것을 알았다고 합니다. 우리가 흔히 쓰는 방법으로 곱셈을 계산하면 한 자리 숫자 곱셈을 4번 하게 되지만, 카라추바 방법을 쓰면 곱셈은 3번만 해도 됩니다.  

 

이미지 확대하기
자릿수가 큰 곱셈에서는 10진법 대신에 큰 수 m을 정한 뒤, 곱하는 두 수를 m진법 (am+b)와 (cm+d)로 나타냅니다. 그다음 A=bd, B=ac, C=(a+b)(c+d), D=C-B-A를 구하고, Bm²+Dm+A를 계산합니다. 그러면 정확하게 (am+b)(cm+d)를 전개한 값이 나옵니다. 컴퓨터에서는 보통 2진법으로 수를 저장하므로, m을 2의 거듭제곱 꼴로 잡으면 계산이 편합니다. 

 

그런데 A, B, C를 구할 때 곱셈을 또 써야 합니다. 만약 계산할 값이 크다면 다시 더 작은 m을 잡아서 m진법으로 만든 뒤 계산하면 됩니다. 이처럼 반복해서 계산하면 총 걸리는 시간은 n이미지 확대하기^{log_{2}3}, 대략 이미지 확대하기n^{1.585}에 비례하게 됩니다. 큰 n²에 대해 n²보다는 훨씬 계산 속도가 빠른 셈입니다. 

 

이 방법은 (ax+b)(cx+d)=(ac)x²+(ad+bc)x+bd라는 다항식의 곱셈으로도 이해할 수 있습니다. 2차 다항식은 세 값만 알면 모든 계수가 결정되기 때문에 일일이 곱셈하는 대신, 계산이 쉬운 몇몇 x값에 대해 다항식의 값을 구한 뒤 그 값을 이용해 구할 수 있습니다. 


예를 들어 x=0​일 때 구한 값이 A이고, x=1일 때 구한 값이 C입니다. 최고차항, 즉 x가 무한대로 갈 때 양변을 비교하는 것이 B​입니다. 이렇게 A, B, C를 알아낸 뒤 이 정보를 이용해 다항식 계수를 알아내는 겁니다. 카라추바의 방법 이후 나온 모든 곱셈법은 이처럼 자연수의 곱셈을 다항식의 곱셈으로 바꿔서 계산합니다.

이미지 확대하기

 

고속 푸리에 변환으로 계산하기


1968년 독일 수학자 아르놀트 쇤하게는 곱셈 계산에 고속 푸리에 변환(FFT)을 처음 도입합니다. FFT는 불연속적인 데이터로 이뤄진 함수를 다른 함수로 빠르게 변환하는 방법입니다. FFT를 쓰면 특수한 상황에서 다항식의 계산을 빠른 속도로 할 수 있고, 그 정보를 이용해 다른 상황에서도 빠르게 값을 구할 수 있습니다. 


3년 뒤 쇤하게는 독일 수학자 포커 슈트라센과 함께 FFT를 이용한 곱셈 알고리듬을 정확하게 설명해 냅니다. 이 알고리듬은 현재 쇤하게-슈트라센 알고리듬이라고도 부릅니다. 이 방법을 이용하면 곱셈하는 데 필요한 시간이 nlognloglogn에 비례합니다.  


n값이 작으면 이 알고리듬은 기존 알고리듬보다는 느립니다. 비례상수 값이 워낙 크기 때문입니다. 이 알고리듬은 널리 사용되는 수학 계산 프로그램(GMP 라이브러리)에 쓰이는데, 곱하는 수의 자릿수가 1만~4만 자리는 돼야 카라추바의 방법이나 그 변형보다 계산이 빠릅니다. 이 때문에 그 정도로 큰 수를 곱할 때나 사용됩니다.


loglogn 부분을 없애고 더 빠른 속도로 계산하는 방법도 있습니다. 쇤하게와 슈트라센은 1971년 쓴 논문에서 추측을 제기합니다. 쇤하게-슈트라센 추측이란 '곱셈하는 데 필요한 시간이 nlogn에 비례하는 알고리듬을 만들 수 있다는 것'입니다.

 

이 추측은 1971년부터 30여 년이 지난 최근까지도 미해결이었습니다. 하지만 2007년 스위스 수학자 마틴 퓨러는 어떤 적당한 상수 K>0에 대해  n(logn)(Klog*n)에 비례하는 알고리듬을 만들었습니다. 여기서 log*n은 log를 몇 번이나 취해야 1보다 작아지는지 그 횟수를 묻는 함수로 매우 느리게 증가합니다. 


2016년 데이비드 하비, 요리시 판데르후번, 그레고이르 르세프는 퓨러의 알고리듬을 변형하고 여러 아이디어를 결합해 곱셈에 걸리는 시간이 n(logn)(8log*n)에 비례하는 알고리듬을 고안했습니다. 하지만 이 알고리듬이 쓰는 시간은 쇤하게와 슈트라센이 추측한 값인 nlogn보다는 조금 더 느리게 속도가 증가했습니다. 


큰 수는 nlogn에 비례하는 시간에 곱한다! 


그런데 올해 3월 18일 인터넷을 떠들썩하게 하는 논문이 공개됐습니다. 프랑스에서 운영하는 논문 공개 사이트에 하비와 판데르후번이 nlogn에 비례하는 시간에 두 n자릿수를 곱할 수 있는 알고리듬을 공개한 것입니다. 

 

이 42쪽짜리 논문은 아직 정식 검증을 거치거나 학술지에 출판된 것은 아닙니다. 앞으로 검증을 거쳐봐야 알겠지만, 이 논문의 저자는 2016년에도 결과를 낸 이 분야 전문가들이라 맞을 확률이 상당히 높아 보입니다. 이 논문 역시 FFT를 쓰고 쇤하게와 슈트라센의 아이디어를 사용하며 동시에 중국인의 나머지 정리 등 정수론의 여러 기술을 활용합니다.


물론 이 알고리듬은 매우 이론적입니다. 현재 증명은 이미지 확대하기2^{2^{4096}}보다는 훨씬 큰 수를 곱할 때 이 방법이 빠르다고 합니다. 이 정도 수라면 우주의 모든 입자의 수보다 훨씬 더 많을 겁니다. 


이런 빠른 곱셈 방법은 원주율의 자릿수를 매우 많이 구하거나, 아주 큰 메르센 소수(2n-1꼴의 소수)를 찾는 등에 사용됩니다. 새로운 알고리듬 덕분에 이런 계산들이 빨라진다는 뜻입니다. 예를 들어 e의 x승이나 원주율 π를 n자리까지 정확하게 구하는 데 걸리는 시간을 이제는 nlog²n에 비례하게 알고리듬을 짤 수 있습니다.


아직도 풀리지 않은 미해결 문제를 하나 소개합니다. ‘nlogn보다 더 빠른 알고리듬이 있을까요, 없을까요?’ 어떤 잘 알려진 추측이 옳다면 nlogn보다 더 빠른 알고리듬은 없을 거라고 합니다. 언젠가는 이런 문제도 해결되길 기대합니다. 

 

참고자료

데이비드 하비, 요리시 판데르후번 ‘Integer multiplication in time O(nlogn)’, 데이비드 하비, 요리시 판데르후번, 그레고이르 르세프 ‘Even faster integer multiplication’, 아나톨리 알렉세예비치 카라추바, 유리 페트로비치 오프만 ‘Multiplication of many-digital numbers by automatic computers’

 

관련기사 

수학동아 5월호, [엄상일의 따끈따끈한 수학] 큰 수의 곱셈을 더 빠르게 쇤하게-슈트라센 추측

 

※필진소개

엄상일 교수.  KAIST 수학과를 졸업하고, 미국 프린스턴대에서 박사 학위를 받았다. 현재 기초과학연구원과 KAIST에서 연구와 강의를 하고 있다. 그래프이론과 이산수학, 조합적 최적화가 주요 연구 분야다. 2012년 젊은과학자상(대통령상)을 받았고, 2017년 한국차세대과학기술한림원 회원으로 선정됐다.


엄상일 기초과학연구원 이산수학그룹 CI & KAIST 수리과학과 교수

 

메일로 더 많은 기사를 받아보세요!

관련기사

인기기사

댓글

댓글쓰기

관련 태그 뉴스

동아사이언스 SNS로
최신 소식을 받아 보세요!

  • 과학동아
    과학동아페이스북 과학동아카카오스토리 과학동아트위터
  • 과학동아천문대
    과학동아천문대페이스북
  • 어과동TV
    어과동TV페이스북
관련 태그 뉴스

동아사이언스 SNS로
최신 소식을 받아 보세요!

  • 과학동아
    과학동아페이스북 과학동아카카오스토리 과학동아트위터
  • 과학동아천문대
    과학동아천문대페이스북
  • 어과동TV
    어과동TV페이스북