곱셈 알고리즘은 두 숫자를 곱하는 데 사용되는 다양한 방법과 관련된 수학적 개념이다. 세로 곱셈, 격자 곱셈, 주산 곱셈, 쿼터 제곱 곱셈과 같은 다양한 알고리즘이 존재하며, 각 알고리즘은 다른 계산 방식을 사용한다. 고속 곱셈 알고리즘은 계산 복잡성을 줄이기 위해 개발되었으며, 카라추바 알고리즘, Toom-Cook 곱셈, 쇤하게-슈트라센 알고리즘 등이 있다. 복소수 곱셈과 다항식 곱셈도 곱셈 알고리즘의 범주에 속하며, 이들의 계산 복잡도에 대한 연구가 진행되고 있다.
더 읽어볼만한 페이지
컴퓨터 산술 알고리즘 - 컴퓨터 프로그래밍의 예술 도널드 커누스가 집필한 컴퓨터 과학 분야의 대표 저서인 컴퓨터 프로그래밍의 예술은 자료 구조, 알고리즘, 준수치적 알고리즘, 정렬 및 검색, 조합론적 알고리즘 등 프로그래밍 핵심 주제를 깊이 있게 다루고 문제 해결 능력 향상에 기여하며, MIX/MMIX 어셈블리 언어 분석을 통해 튜링상 수상 및 "세기의 과학을 형성한 100여 권의 책"으로 선정되는 등 높은 평가를 받았다.
컴퓨터 산술 알고리즘 - 카라추바 알고리즘 카라추바 알고리즘은 1960년 아나톨리 카라추바가 개발한 곱셈 알고리즘으로, 분할 정복 방식을 사용하여 두 n자리 숫자의 곱셈 시간 복잡도를 O(n²)에서 O(n1.585)로 개선한다.
곱셈 - 구구단 구구단은 곱셈을 간편하게 계산하도록 곱셈 결과를 표로 정리한 것이며, 1단부터 9단까지 외우는 곱셈 구구가 일반적이고, 덧셈, 뺄셈, 나눗셈 구구 등 다양한 형태가 존재하며, 수학적 개념 이해의 기초가 되고 실생활에도 응용된다.
곱셈 - 네이피어의 뼈 네이피어의 뼈는 존 네이피어가 1617년에 발명한 계산 도구로, 곱셈을 덧셈으로 변환하여 계산을 간편하게 하고 나눗셈과 제곱근 계산에도 활용되며, 계산 기반과 막대 세트로 구성되어 막대에 표시된 숫자를 이용하여 복잡한 곱셈을 단순화한다.
곱셈 알고리즘
2. 세로 곱셈 (필산 곱셈)
기수법을 사용하는 곱셈 방식에서, 세로 곱셈은 학교에서 가르치는 일반적인 방법이다. 세로 곱셈은 초등학교 곱셈 또는 표준 알고리즘이라고도 불린다. 이 방법은 피승수에 승수의 각 자릿수를 곱하고, 그 결과들을 자릿수에 맞춰 쓴 후 모두 더하는 방식으로 이루어진다. 이 곱셈법은 구구단 암기가 필수적이다.[1]
세로 곱셈은 10진법에서 큰 수를 손으로 곱할 때 유용하다. 종이에 계산할 때는 모든 곱셈 결과를 적고 더하지만, 주판을 사용하면 각 결과가 나올 때마다 바로 합산한다.[1]
아래 의사 코드는 곱셈 과정을 설명한다. 결과 합계를 유지하기 위해 한 행만 사용하며, '+=' 연산자는 기존 값에 더하여 저장하는 연산자이다.
```pascal
multiply(a[1..p], b[1..q], base) // 피연산자는 색인 1에서 가장 오른쪽에 있는 숫자를 포함합니다.
product = [1..p+q] // 결과에 대한 공간 할당
for b_i = 1 to q // b의 모든 숫자에 대해
carry = 0
for a_i = 1 to p // a의 모든 숫자에 대해
product[a_i + b_i - 1] += carry + a[a_i] * b[b_i]
carry = product[a_i + b_i - 1] / base
product[a_i + b_i - 1] = product[a_i + b_i - 1] mod base
product[b_i + p] = carry // 마지막 숫자는 최종 자리올림에서 가져옵니다.
return product
2. 1. 세로 곱셈의 원리
기수법을 사용하면, 숫자를 곱하는 자연스러운 방법이 학교에서 '''세로 곱셈'''으로 가르쳐지는데, 때로는 '''초등학교 곱셈''' 또는 '''표준 알고리즘'''이라고도 불린다. 피승수에 승수의 각 자릿수를 곱한 다음, 적절하게 시프트된 모든 결과를 더한다. 이 방법은 한 자릿수에 대한 구구단 암기를 필요로 한다.
이것은 10진법에서 손으로 더 큰 숫자를 곱하는 일반적인 알고리즘이다. 종이에 세로 곱셈을 하는 사람은 모든 곱셈 결과를 적어놓고 그것들을 더할 것이다. 반면 주판 사용자는 각 곱셈 결과가 계산되는 즉시 합산할 것이다.
다음은 23,958,233 (피승수)과 5,830 (승수)을 곱하여 139,676,498,390을 얻는 예시이다.
23958233
× 5830
———————————————
00000000 ( = 23,958,233 × 0)
71874699 ( = 23,958,233 × 30)
191665864 ( = 23,958,233 × 800)
+ 119791165 ( = 23,958,233 × 5,000)
———————————————
139676498390 ( = 139,676,498,390)
2. 2. 세로 곱셈의 다른 표기법 (독일 등)
독일 등 일부 국가에서는 곱셈을 위와 유사하게 묘사하지만, 원래 곱을 가로로 유지하고 곱하는 수의 첫 번째 숫자부터 곱셈을 시작한다.[1]
23958233 · 5830
———————————————
119791165
191665864
71874699
00000000
———————————————
139676498390
3. 격자 곱셈법
격자 곱셈법은 필산 곱셈 외에 손으로 곱셈을 할 때 사용하는 방법이다. 컴퓨터나 구구단을 사용할 수 없을 때 격자 곱셈법을 쓰면 유용하다.
3. 1. 격자 곱셈법의 원리
격자 곱셈법(또는 상자 방법)은 초등학교에서 학생들에게 여러 자리 곱셈을 가르치기 위해 사용하는 방법 중 하나이다. 1990년대 후반부터 잉글랜드와 웨일스의 국가 초등학교 수학 커리큘럼의 표준 부분이 되었다.[3]
이 방법은 곱하는 두 수를 백의 자리, 십의 자리, 일의 자리 등으로 나누어 ("분할") 계산한다. 각 부분의 곱은 간단한 곱셈으로 계산하고, 마지막에 이 곱셈 결과들을 모두 더하여 최종 답을 구한다.
예를 들어 34 × 13을 계산할 때 다음과 같은 격자를 사용할 수 있다.
×
30
4
10
300
40
3
90
12
위 표를 통해 300 + 40 + 90 + 12 = 442와 같이 덧셈을 하여 442라는 답을 얻는다. 이 덧셈은 한 번에 계산할 수도 있고, (300 + 40) + (90 + 12) = 340 + 102 = 442와 같이 행별로 더하여 계산할 수도 있다.
이 계산 방식은 명시적인 격자 배열이 아니더라도 부분 곱 알고리즘으로도 알려져 있다. 이 방법의 핵심은 간단한 곱셈들을 각각 따로 계산하고, 모든 덧셈은 마지막 단계에서 한꺼번에 처리하는 것이다.
격자 곱셈법은 원칙적으로 어떤 크기의 수를 곱할 때도 사용할 수 있지만, 곱하는 수의 자릿수가 많아질수록 계산해야 할 부분 곱의 개수가 많아져 복잡해진다. 그럼에도 불구하고 여러 자리 곱셈의 개념을 쉽게 이해할 수 있도록 돕는 유용한 방법이다. 또한, 대부분의 곱셈 계산을 계산기나 스프레드시트로 하는 현대에는 일부 학생들에게 실제로 필요한 유일한 곱셈 알고리즘이 될 수도 있다.
3. 2. 격자 곱셈법의 활용 (영국 등)
격자 곱셈법(또는 상자 방법)은 1990년대 후반부터 잉글랜드와 웨일스의 국가 초등학교 수학 커리큘럼의 표준 부분이 되었다.[3] 학생들에게 여러 자리 곱셈을 가르치기 위한 입문 방법으로 활용되고 있다.
이 방법은 두 인수를 백의 자리, 십의 자리, 일의 자리 부분으로 나누어 ("분할") 곱하고, 부분 곱을 계산한 다음, 이 값들을 모두 더하여 최종 답을 얻는 방식이다.
예를 들어 34 × 13의 계산은 다음과 같이 격자를 사용하여 계산할 수 있다.
×
30
4
10
300
40
3
90
12
위 표를 통해 442라는 값을 구할 수 있는데, 단일 합계(오른쪽 참조) 또는 행별 합계 (300 + 40) + (90 + 12) = 340 + 102 = 442로 계산할 수 있다.
이 계산 방식은 부분 곱 알고리즘으로도 알려져 있다. 핵심은 간단한 곱셈을 별도로 계산하고 모든 덧셈을 마지막 단계에 남겨두는 것이다.
격자 방법은 원칙적으로 모든 크기의 인수에 적용할 수 있지만, 자릿수가 증가함에 따라 부분 곱의 수가 번거로워진다. 그럼에도 불구하고 여러 자리 곱셈의 개념을 이해하는데 유용하며, 계산기나 스프레드시트를 주로 사용하는 시대에 일부 학생들에게는 유일하게 필요한 곱셈 알고리즘일 수 있다.
4. 격자 곱셈 (체 곱셈)
1 /|4 /|2 /|4 /|1 /|1 /|1 /|
/ | / | / | / | / | / | / | 5
2 /|7 /|4 /|6 /|1 /|2 /|2 /|
/ | / | / | / | / | / | / | 8
0 /|2 /|1 /|2 /|0 /|0 /|0 /|
/ | / | / | / | / | / | / | 3
0 /|0 /|0 /|0 /|0 /|0 /|0 /|
/ | / | / | / | / | / | / | 0
|
|
4. 1. 격자 곱셈의 역사
격자 곱셈은 1202년 피보나치의 산반서를 통해 유럽에 소개되었다. 피보나치는 이 연산을 정신적인 것으로 묘사하며, 중간 계산을 수행하기 위해 오른손과 왼손을 사용했다. 마트라크치 나수흐는 16세기에 저술한 책 '움데트-울 히사브'에서 이 방법의 6가지 변형을 제시했다. 이 방법은 오스만 제국의 엔데룬 학교에서 널리 사용되었다.[4] 네이피어의 뼈대(네이피어의 막대) 역시 이 방법을 사용했으며, 네이피어가 사망한 해인 1617년에 출판되었다.
5. 주산 곱셈 (러시아 농부 곱셈)
주산 곱셈은 곱셈 구구단을 모르는 사람들도 사용할 수 있는 간단한 곱셈 방법이다. 곱하는 수 중 하나를 반복해서 반으로 나누고(나머지는 버림), 다른 하나는 반복해서 두 배로 늘리는 방식으로 작동한다. 고대 이집트에서 사용된 방법이다.[6]
5. 1. 주산 곱셈의 원리
주산 곱셈은 곱셈 구구단을 외우지 못한 농부들이 주로 사용했기 때문에 붙여진 이름이다.[5] 이 알고리즘은 고대 이집트에서도 사용되었다.[6] 이 방법은 빨리 배울 수 있고, 외울 필요가 없으며, 종이와 연필이 없을 때 포커 칩과 같은 도구를 사용해 계산할 수 있다는 장점이 있다. 하지만 세로 곱셈보다 단계가 많아 큰 숫자를 다루기는 어렵다.
주산 곱셈은 곱하는 수를 반복해서 반으로 나누고(나머지는 버림), 그 옆에는 곱해지는 수를 반복해서 두 배로 늘려 적는 방식으로 진행된다. 첫 번째 열의 마지막 숫자가 짝수인 행을 지우고, 두 번째 열에 남은 숫자들을 더하면 곱셈의 결과를 얻을 수 있다.
5. 2. 주산 곱셈의 장단점
주산 곱셈은 곱셈 구구단을 외울 필요 없이 곱셈을 할 수 있는 방법으로, 농부들이 주로 사용했기 때문에 '농부 곱셈법'이라고도 불린다.[5] 이 알고리즘은 고대 이집트에서도 사용되었다.[6]
주산 곱셈의 장점은 다음과 같다.
배우기 쉽다.
암기가 필요 없다.
포커 칩과 같은 도구를 사용하여 계산할 수 있다.
하지만 주산 곱셈은 큰 숫자를 곱할 때 단계가 많아져서 복잡하고 어려울 수 있다는 단점이 있다.
6. 쿼터 제곱 곱셈
쿼터 제곱 곱셈은 두 수의 곱셈을 제곱, 덧셈, 뺄셈, 나눗셈 연산으로 변환하여 계산하는 방법이다. 이 방법의 핵심은 다음 공식과 같이 두 수의 합과 차를 이용하여 곱셈 결과를 얻는다는 것이다.
:
이 방식은 바빌로니아 수학에서 기원했다고 알려져 있으며,[7][8] 19세기에는 곱셈 계산을 돕기 위해 쿼터 제곱표가 출판되기도 했다. 1817년 앙투안 부아쟁(Antoine Voisin)은 1부터 1000까지의 숫자에 대한 쿼터 제곱표를 출판했고, 이후 사무엘 론디(Samuel Laundy, 1856년, 1~100000 범위[9])와 요제프 블라터(Joseph Blater, 1888년, 1~200000 범위[10])가 더 큰 범위의 표를 출판했다.
또한, 쿼터 제곱 곱셈은 아날로그 컴퓨터에서 두 아날로그 신호의 곱을 계산하거나, MOS 테크놀로지 6502와 같이 하드웨어 곱셈기가 없는 8비트 시스템에서 곱셈을 수행하는 데 유용하게 사용되었다.[11][12] 1980년 에버렛 L. 존슨(Everett L. Johnson)은 디지털 데이터 승수에 쿼터 제곱 방법을 사용할 것을 제안했다.
6. 1. 쿼터 제곱 곱셈의 공식
Quarter square multiplication영어의 공식은 다음과 같다.
:
이 공식은 곱셈을 더 쉽게 할 수 있도록 돕는다.[7][8]
와 가 정수인 경우, 가 성립한다. 왜냐하면 와 는 둘 다 짝수이거나 둘 다 홀수이기 때문이다. 이는 다음을 의미한다.
:
즉, 제곱을 4로 나눈 정수 부분만 계산하면 된다.
다음은 0부터 18까지의 숫자에 대한 쿼터 제곱을 보여주는 표이며, 나머지는 버린다. 이를 통해 까지의 숫자 곱셈이 가능하다.
n
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
⌊n2/4⌋
0
0
1
2
4
6
9
12
16
20
25
30
36
42
49
56
64
72
81
예를 들어 9와 3을 곱하려면, 두 수의 합(12)과 차(6)를 위 표에서 찾는다. 각각 36과 9를 얻을 수 있으며, 이 둘의 차이는 27이다. 27은 9와 3의 곱이다.
6. 2. 쿼터 제곱 곱셈의 활용
쿼터 제곱 곱셈은 다음 공식을 이용한다.
:
이 공식을 사용하면 두 수의 곱셈을 제곱, 덧셈, 뺄셈, 나눗셈으로 변환할 수 있다. x와 y가 모두 정수이면 (x+y)와 (x-y)는 항상 짝수이거나 홀수이므로, 4로 나눈 몫은 정수 부분만 취하여 계산할 수 있다.
이 방법은 아날로그 컴퓨터에서 두 입력 전압의 곱을 계산하는 데 사용되었다. 연산 증폭기를 사용하여 두 입력 전압의 합과 차를 구하고, 구간별 선형 회로를 사용하여 각 값을 제곱한다. 그 후, 두 제곱 값의 차이를 구하고 1/4을 곱하여 최종 결과를 얻는다.[11]
또한, 쿼터 제곱 곱셈은 하드웨어 승수를 지원하지 않는 8비트 시스템, 예를 들어 MOS 테크놀로지 6502에서 곱셈을 구현하는 데 활용되었다.[12] 8비트 정수의 경우, 0부터 510까지의 모든 합에 대한 쿼터 제곱 값을 저장하는 표(총 511개 항목, 각 항목은 16비트)를 이용하여 곱셈을 빠르게 계산할 수 있다.
다음은 0부터 18까지의 숫자에 대한 쿼터 제곱 표이다. (나머지는 버림)
n
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
⌊n²/4⌋
0
0
1
2
4
6
9
12
16
20
25
30
36
42
49
56
64
72
81
예를 들어, 9와 3을 곱하려면, 표에서 9+3=12와 9-3=6에 해당하는 값인 36과 9를 찾는다. 이 둘의 차이인 27이 9와 3의 곱이다.
7. 고속 곱셈 알고리즘
이론 전산학 분야에서는 두 개의 비트 정수를 곱하는 데 필요한 연산 횟수를 연구한다. 이를 곱셈의 계산 복잡도라고 한다. 손으로 하는 일반적인 알고리즘은 점근적 복잡도가 이지만, 1960년에 아나톨리 카라추바가 카라추바 알고리즘을 통해 더 나은 복잡도가 가능하다는 것을 발견했다.
현재 계산 복잡도가 가장 좋은 알고리즘은 2019년 데이비드 하비와 요리스 반 데르 후벤이 발표한 알고리즘으로, 쇤하게-슈트라센 알고리즘에서 도입된 수론적 변환 전략을 사용하여 연산만으로 정수를 곱한다.[13] 이것이 가능한 최상의 알고리즘으로 추정되지만, 의 하한은 알려져 있지 않다.
7. 1. 카라추바 알고리즘
카라추바 알고리즘은 두 수를 곱하는 효율적인 방법 중 하나로, 큰 수를 다룰 때 특히 유용하다. 이 알고리즘은 큰 곱셈 문제를 더 작은 곱셈 문제들로 나누어 해결하는 분할 정복 알고리즘 방식을 사용한다.
어떤 기수 에서 자리 문자열로 표현된 두 수 와 를 생각해보자. 보다 작은 임의의 양의 정수 에 대해, 와 를 다음과 같이 나타낼 수 있다.
여기서 와 는 보다 작은 수이다. 이 두 수를 곱하면 다음과 같은 결과를 얻는다.
여기서,
이다. 이 식은 네 번의 곱셈을 필요로 하지만, 카라추바는 을 다음과 같이 세 번의 곱셈만으로 계산할 수 있음을 발견했다.
이 방법을 사용하면 큰 곱셈 문제를 더 작은 문제들로 나누고, 각 작은 문제들을 해결한 후, 그 결과들을 조합하여 원래 문제의 답을 얻을 수 있다.
하지만 재귀를 사용할 때 발생하는 추가적인 계산(오버헤드) 때문에, 작은 수(이 작은 경우)에 대해서는 카라추바 알고리즘이 일반적인 곱셈 방법보다 느릴 수 있다. 따라서 실제 구현에서는 작은 수에 대해서는 일반적인 곱셈 방법을 사용하고, 큰 수에 대해서만 카라추바 알고리즘을 적용하는 경우가 많다.
7. 1. 1. 카라추바 알고리즘의 역사
카라추바 알고리즘은 O(''n''log23) ≈ O(''n''1.585) 분할 정복 알고리즘으로, 재귀를 사용하여 하위 계산을 병합한다. 이 공식은 찰스 배비지에게 알려져 있었다.[14] 카라추바는 ''xy''를 몇 번의 추가적인 덧셈을 통해 단 세 번의 곱셈으로 계산할 수 있다는 것을 발견했다. 카라추바 알고리즘은 필산 곱셈보다 점근적으로 더 빠른 최초의 곱셈 알고리즘으로 알려져 있으며,[15] 따라서 빠른 곱셈 이론의 시작점으로 볼 수 있다.
7. 2. Toom-Cook 곱셈
툼-쿡(Toom-Cook) 곱셈은 곱할 각 숫자를 여러 부분으로 나누어 계산하는 방식이다. 툼-쿡 곱셈은 카라추바 방법의 일반화된 형태 중 하나이다. 3방향 툼-쿡은 크기 ''3N''의 곱셈을 크기 ''N'' 곱셈 5번으로 수행할 수 있다. 이는 연산을 9/5배 가속화하는 반면, 카라추바 방법은 4/3배 가속화한다.[1]
더 많은 부분을 사용할수록 재귀 곱셈에 소요되는 시간을 줄일 수 있지만, 덧셈 및 자릿수 관리의 오버헤드도 증가한다.[1] 이러한 이유로 푸리에 변환 방법은 일반적으로 수천 자릿수의 숫자에 대해 더 빠르며, 훨씬 더 큰 숫자에 대해서는 점근적으로 더 빠르다.[1]
7. 3. 쇤하게-슈트라센 알고리즘
쇤하게-슈트라센 알고리즘은 1971년 쇤하게와 슈트라센이 개발한 곱셈 알고리즘이다. 이 알고리즘은 고속 푸리에 변환(FFT)을 사용하여 두 수의 곱셈을 빠르게 수행한다.[16]
350px
밑수 B의 모든 숫자는 다항식으로 표현할 수 있다.
:
두 숫자의 곱셈은 두 다항식의 곱으로 볼 수 있으며, 이는 컨볼루션 연산을 통해 계산할 수 있다. FFT를 이용하면 컨볼루션 문제를 곱셈 문제로 변환할 수 있다.
이 알고리즘은 분할 정복 전략을 사용하며, 시간 복잡도는 O(''n'' log(''n'') log(log(''n'')))이다.[16]
7. 3. 1. 쇤하게-슈트라센 알고리즘 이후의 발전
2007년, 스위스 수학자 마틴 퓌러는 복소수 위에서 푸리에 변환을 사용하여 ''n'' log(''n'') 2Θ(log*(''n''))의 점근적 복잡도를 갖는 정수 곱셈 알고리즘을 개선했다.[17] 여기서 log*는 반복 로그를 나타낸다. 2008년에는 아닌디야 데, 찬단 사하, 피유시 쿠루르 및 람프라사드 삽타리시가 모듈러 산술을 사용한 유사한 알고리즘을 제시하여 동일한 실행 시간을 달성했다.[18] 이들은 23''k'' + 1보다 훨씬 작은 ''N''을 찾아 ''Z''/''NZ''가 (2''m'')번째 단위 근을 갖도록 함으로써 계산 속도를 높이고 시간 복잡도를 줄였다. 그러나 이 알고리즘들은 매우 큰 입력에 대해서만 쇤하게-슈트라센 알고리즘보다 빠르다.
2014년, 하비, 요리스 판 데르 호벤과 레세르프[19]는 의 실행 시간을 달성하는 새로운 알고리즘을 제시했다. 또한 을 달성하지만 유효성은 메르센 소수의 분포에 대한 표준 추측에 의존하는 알고리즘의 변형도 제안했다. 2016년, 코바노프와 톰은 페르마 소수의 일반화를 기반으로 한 정수 곱셈 알고리즘을 제안하여 추측적으로 의 복잡도 경계를 달성했다.[20] 이는 2015년 하비, 판 데르 호벤 및 레세르프의 조건부 결과와 일치하지만 다른 알고리즘을 사용하며 다른 추측에 의존한다. 2018년, 하비와 판 데르 호벤은 민코프스키 정리에 의해 보장되는 짧은 격자 벡터의 존재를 기반으로 한 접근 방식을 사용하여 의 무조건적인 복잡도 경계를 증명했다.[21]
2019년 3월, 데이비드 하비와 요리스 판 데르 호벤은 곱셈 알고리즘을 발견했다고 발표했다.[22] 이 알고리즘은 2021년 ''수학 연보''에 게재되었다.[23] 쇤하게와 슈트라센은 ''n'' log(''n'')이 "가장 좋은 결과"라고 예측했기 때문에, 하비는 다음과 같이 말했다: "...우리의 연구는 이 문제의 종착역이 될 것으로 예상되지만, 이를 엄밀하게 증명하는 방법은 아직 모릅니다."[24]
8. 복소수 곱셈
복소수 곱셈은 일반적으로 네 번의 곱셈과 두 번의 덧셈을 포함한다.
:
다음과 같이 나타낼 수도 있다.
×
a
bi
c
ac
bci
di
adi
-bd
1963년 피터 웅가르(Peter Ungar)는 카라추바 알고리즘과 기본적으로 동일한 계산을 사용하여 곱셈 횟수를 세 번으로 줄일 수 있음을 보였다.[27] (''a'' + ''bi'') · (''c'' + ''di'')는 다음과 같이 계산할 수 있다.
:''k''1 = ''c'' · (''a'' + ''b'')
:''k''2 = ''a'' · (''d'' − ''c'')
:''k''3 = ''b'' · (''c'' + ''d'')
:실수부 = ''k''1 − ''k''3
:허수부 = ''k''1 + ''k''2
이 알고리즘은 네 번이 아닌 세 번의 곱셈과 두 번 대신 다섯 번의 덧셈 또는 뺄셈을 사용한다. 손으로 계산하는 경우처럼 곱셈이 덧셈이나 뺄셈보다 더 많은 비용이 들면 속도 이점이 있다. 그러나 최신 컴퓨터에서는 곱셈과 덧셈에 거의 같은 시간이 걸릴 수 있으므로, 속도 이점이 없을 수도 있다. 부동 소수점을 사용할 때 정밀도가 다소 손실될 수 있다는 단점도 있다.
고속 푸리에 변환(FFT) (또는 모든 선형 변환)에서 복소수 곱셈은 상수 계수 ''c'' + ''di'' (FFT에서 트위들 팩터라고 함)에 의해 이루어진다. 이 경우 두 번의 덧셈(''d''−''c''와 ''c''+''d'')을 미리 계산할 수 있다. 따라서 세 번의 곱셈과 세 번의 덧셈만 필요하다.[28] 그러나 이러한 방식으로 곱셈을 덧셈으로 바꾸는 것은 최신 부동 소수점 장치에서는 더 이상 유용하지 않을 수 있다.[29]
9. 다항식 곱셈
다항식 곱셈은 위에 제시된 곱셈 알고리즘들을 사용하여 계산할 수 있다. 크로네커 치환 기법을 사용하면 다항식 곱셈 문제를 단일 이진 곱셈으로 변환할 수도 있다.[30]
세로 곱셈 방법은 대수 공식을 곱하는 데에도 일반화할 수 있다. 다음은 14ac - 3ab + 2 곱하기 ac - ab + 1의 예시이다.
14ac -3ab 2
ac -ab 1
————————————————————
14a2c2 -3a2bc 2ac
14a2bc 3 a2b2 -2ab
14ac -3ab 2
———————————————————————————————————————
14a2c2 -17a2bc 16ac 3a2b2 -5ab +2[31]
열 기반 곱셈의 또 다른 예로, 23 롱톤(t), 12 센트너(cwt) 및 2 쿼터(qtr)를 47로 곱하는 경우를 생각할 수 있다. 이 예시에서는 에버듀포아 단위를 사용하며, 1 t = 20 cwt, 1 cwt = 4 qtr이다. 계산 과정은 다음과 같다.
t cwt qtr
23 12 2
47 x
————————————————
141 94 94
940 470
29 23
————————————————
1110 587 94
————————————————
1110 7 2
답: 1110 톤 7 cwt 2 qtr
먼저 쿼터(qtr)를 47로 곱하면 94가 된다. 다음으로 센트너(cwt) 12에 47을 곱하면 (2 + 10)*47 = 94 + 470 이다. 마찬가지로 23에 47을 곱하면 141 + 940이 된다. 쿼터 열을 합산하면 94인데, 이는 23 cwt와 2 qtr이므로, 2를 답에 적고 23을 다음 열 왼쪽에 적는다. cwt 열의 세 항목을 더하면 587이 되고, 이는 29 t 7 cwt이므로 7을 답에 적고 29를 왼쪽 열에 적는다. 마지막으로 톤 열을 합산하면 1110이 되고, 조정할 사항이 없으므로 결과를 그대로 적는다.
이와 같은 방법과 레이아웃은 모든 전통적인 측정 단위와 이전 영국의 파운드 스털링(£sd) 시스템과 같은 비십진 통화에도 적용할 수 있다.
10. 곱셈 알고리즘의 계산 복잡도
이론 전산학 분야에서는 두 개의 n비트 정수를 곱하는 데 필요한 비트 연산 횟수를 연구한다. 이를 곱셈의 계산 복잡도라고 한다. 손으로 하는 일반적인 알고리즘은 점근적 복잡도가 이지만, 1960년에 아나톨리 카라추바는 더 나은 복잡도를 가지는 카라추바 알고리즘을 발견했다.
현재 가장 빠른 알고리즘은 2019년 데이비드 하비와 요리스 반 데르 후벤이 발표한 알고리즘으로, 쇤하게-슈트라센 알고리즘의 수론적 변환 전략을 사용하여 연산만으로 정수를 곱한다.[13] 현재 의 하한은 알려져 있지 않기 때문에, 이 알고리즘이 가장 효율적인 알고리즘으로 추정된다.
10. 1. 곱셈의 하한
두 개의 ''n''비트 숫자를 단일 프로세서에서 곱하는 데는 자명한 하한 Ω(''n'')이 있다. 이와 일치하는 알고리즘(즉, 튜링 기계와 같은 기존 기계에서)이나 더 엄밀한 하한은 알려져 있지 않다. 곱셈은 어떤 소수 ''p''에 대해서도 AC0[''p''] 외부에 있다. 즉, AND, OR, NOT 및 MOD''p'' 게이트를 사용하여 곱을 계산할 수 있는 일련의 상수 깊이, 다항식(또는 심지어 서브 지수) 크기 회로가 없다. 이는 MOD''q''를 곱셈으로의 상수 깊이 감소로부터 따른다.[25] 곱셈에 대한 하한은 일부 클래스의 분기 프로그램에 대해서도 알려져 있다.[26]
참조
[1]
웹사이트
Multiplication
http://www.mathemati[...]
2022-03-15
[2]
논문
A Fortran Multiple-Precision Arithmetic Package.
1978-03
[3]
뉴스
Back to school for parents
http://news.bbc.co.u[...]
BBC News
2000-02-13
[4]
논문
The Ottoman Palace School Enderun and the Man with Multiple Talents, Matrakçı Nasuh
https://koreascience[...]
2010
[5]
웹사이트
Peasant Multiplication
https://www.cut-the-[...]
2017-11-04
[6]
서적
The Penguin Dictionary of Curious and Interesting Numbers
Penguin Books
[7]
간행물
Quarter Tables Revisited: Earlier Tables, Division of Labor in Table Construction, and Later Implementations in Analog Computers
http://escholarship.[...] [8]
서적
Mathematics in Ancient Iraq: A Social History
Princeton University Press
[9]
간행물
Reviews
https://books.google[...] [10]
간행물
Multiplying with quarter squares
[11]
간행물
A Digital Quarter Square Multiplier
IEEE Computer Society
1980-03
[12]
논문
Fastest 6502 Multiplication Yet
http://www.txbobsc.c[...]
1986-03
[13]
논문
Integer multiplication in time
https://hal.archives[...] [14]
문서
Chapter VIII – Of the Analytical Engine, Larger Numbers Treated
https://archive.org/[...]
Charles Babbage
1864
[15]
문서
The Art of Computer Programming
D. Knuth
1998
[16]
논문
Schnelle Multiplikation großer Zahlen
https://link.springe[...]
1971
[17]
서적
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA
null
2007
[18]
서적
Proceedings of the 40th annual ACM Symposium on Theory of Computing (STOC)
null
2008
[19]
논문
Even faster integer multiplication
[20]
논문
Fast Integer Multiplication Using Generalized Fermat Primes
[21]
논문
Faster integer multiplication using short lattice vectors
[22]
간행물
Mathematicians Discover the Perfect Way to Multiply
https://www.quantama[...]
2019-04-11
[23]
논문
Integer multiplication in time
https://hal.archives[...] [24]
뉴스
Maths whiz solves 48-year-old multiplication problem
https://newsroom.uns[...]
UNSW
2019-04-04
[25]
서적
Computational Complexity: A Modern Approach
null
Cambridge University Press
2009
[26]
논문
A lower bound for integer multiplication on randomized ordered read-once branching programs
https://core.ac.uk/d[...]
2003
[27]
간행물
The Art of Computer Programming volume 2: Seminumerical algorithms
Addison-Wesley
[28]
논문
Fast Fourier transforms: A tutorial review and a state of the art
https://core.ac.uk/d[...]
1990
[29]
논문
A modified split-radix FFT with fewer arithmetic operations
https://www.fftw.org[...]
2007
[30]
간행물
Modern Computer Algebra
https://books.google[...]
Cambridge University Press
[31]
서적
Workshop Mathematics
https://archive.org/[...]
MacMillan and Co
1900
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
