카라츠바 곱셈 계산기
두 수를 반으로 쪼개 네 번이 아니라 세 번의 곱셈으로 처리하는 과정을 재귀 단계별로 보입니다. 자릿수 곱셈 횟수를 초등학교 방식(n²)과 견주고, 임계 자릿수를 바꿔 가며 작은 수에서는 왜 오히려 손해인지 확인할 수 있습니다.
0 이상의 정수, 24자리까지
0 이상의 정수, 24자리까지
이 자릿수 이하로 내려가면 재귀를 멈추고 초등학교 방식으로 곱합니다. 실제 구현이 하는 일과 같습니다.
곱
1082152022374638
자릿수 곱셈을 53번 했습니다. 초등학교 방식이라면 64번(8자리 × 8자리)이므로 83% 수준입니다.
임계 자릿수를 바꾸면
| 임계 | 자릿수 곱셈 | 재귀 호출 |
|---|---|---|
| 1자리 | 53번 | 79번 |
| 2자리 | 46번 | 25번 |
| 3자리 | 44번 | 13번 |
| 4자리 | 48번 | 7번 |
| 5자리 | 52번 | 4번 |
| 6자리 | 52번 | 4번 |
| 7자리 | 52번 | 4번 |
| 8자리 | 64번 | 1번 |
임계를 올릴수록 재귀 호출이 줄고 자릿수 곱셈은 늡니다. 실제 구현(GMP, 파이썬의 큰 정수)이 일정 자릿수 아래에서 초등학교 방식으로 되돌아가는 것은, 여기서 세지 않는 덧셈·뺄셈과 자리 옮기기가 재귀 한 층마다 붙어 작은 수에서는 곱셈 하나 아낀 이득보다 커지기 때문입니다.
쪼개는 과정
x·y = ac·B² + ((a+b)(c+d) − ac − bd)·B + bd
ac, bd는 어차피 필요하니 (a+b)(c+d) 한 번만 더 곱하면 가운데 항 ad+bc가 뺄셈으로 나옵니다. 곱셈이 네 번에서 세 번으로 줄고, 자릿수 n짜리 곱이 n/2짜리 곱 세 개가 되므로 T(n) = 3·T(n/2) + O(n)에서 Θ(n^log₂3) = Θ(n^1.585)이 나옵니다.
위에서 3층까지
12345678 × 87654321 = 1082152022374638
a=1234 b=5678 · c=8765 d=4321 · B=104
ac = 10816010
bd = 24534638
(a+b)(c+d) = 90450432
ad+bc = 90450432 − 10816010 − 24534638 = 55099784
1234 × 8765 = 10816010
a=12 b=34 · c=87 d=65 · B=102
ac = 1044
bd = 2210
(a+b)(c+d) = 6992
ad+bc = 6992 − 1044 − 2210 = 3738
12 × 87 = 1044
a=1 b=2 · c=8 d=7 · B=101
ac = 8
bd = 14
(a+b)(c+d) = 45
ad+bc = 45 − 8 − 14 = 23
34 × 65 = 2210
a=3 b=4 · c=6 d=5 · B=101
ac = 18
bd = 20
(a+b)(c+d) = 77
ad+bc = 77 − 18 − 20 = 39
46 × 152 = 6992
a=4 b=6 · c=15 d=2 · B=101
ac = 60
bd = 12
(a+b)(c+d) = 170
ad+bc = 170 − 60 − 12 = 98
5678 × 4321 = 24534638
a=56 b=78 · c=43 d=21 · B=102
ac = 2408
bd = 1638
(a+b)(c+d) = 8576
ad+bc = 8576 − 2408 − 1638 = 4530
56 × 43 = 2408
a=5 b=6 · c=4 d=3 · B=101
ac = 20
bd = 18
(a+b)(c+d) = 77
ad+bc = 77 − 20 − 18 = 39
78 × 21 = 1638
a=7 b=8 · c=2 d=1 · B=101
ac = 14
bd = 8
(a+b)(c+d) = 45
ad+bc = 45 − 14 − 8 = 23
134 × 64 = 8576
a=13 b=4 · c=6 d=4 · B=101
ac = 78
bd = 16
(a+b)(c+d) = 170
ad+bc = 170 − 78 − 16 = 76
6912 × 13086 = 90450432
a=69 b=12 · c=130 d=86 · B=102
ac = 8970
bd = 1032
(a+b)(c+d) = 17496
ad+bc = 17496 − 8970 − 1032 = 7494
69 × 130 = 8970
a=6 b=9 · c=13 d=0 · B=101
ac = 78
bd = 0
(a+b)(c+d) = 195
ad+bc = 195 − 78 − 0 = 117
12 × 86 = 1032
a=1 b=2 · c=8 d=6 · B=101
ac = 8
bd = 12
(a+b)(c+d) = 42
ad+bc = 42 − 8 − 12 = 22
81 × 216 = 17496
a=8 b=1 · c=21 d=6 · B=101
ac = 168
bd = 6
(a+b)(c+d) = 243
ad+bc = 243 − 168 − 6 = 69
재귀는 4층까지, 모두 79번 내려갑니다. 화면에는 3층까지만 보입니다.
계산 방법
- 1곱할 두 정수를 넣습니다. 24자리까지 다룹니다.
- 2임계 자릿수를 정합니다. 그 아래로 내려가면 재귀를 멈추고 초등학교 방식으로 곱합니다.
- 3자릿수 곱셈 횟수를 초등학교 방식과 견줍니다.
- 4「쪼개는 과정」에서 ac, bd, (a+b)(c+d)가 어떻게 가운데 항이 되는지 따라갑니다.
- 5임계 자릿수를 1부터 올려 가며 자릿수 곱셈과 재귀 호출이 어떻게 맞바뀌는지 봅니다.
자주 묻는 질문
가운데 항을 곱하지 않고 빼서 얻습니다. x = a·B + b, y = c·B + d로 쪼개면 x·y = ac·B² + (ad + bc)·B + bd인데, (a+b)(c+d) = ac + ad + bc + bd이므로 ad + bc = (a+b)(c+d) − ac − bd입니다. ac와 bd는 어차피 필요하니 (a+b)(c+d) 한 번만 더 곱하면 가운데 항이 뺄셈으로 나옵니다.
log₂3 = 1.585입니다. 자릿수 n짜리 곱 하나를 자릿수 n/2짜리 곱 세 개로 바꾸므로 T(n) = 3·T(n/2) + O(n)이 되고, 마스터 정리로 Θ(n^log₂3)이 됩니다. 초등학교 방식은 자릿수 곱셈이 정확히 n²번이니 n이 커질수록 격차가 벌어집니다.
아닙니다. 두세 자리에서는 오히려 초등학교 방식이 더 빠릅니다. 재귀를 한 번 내려갈 때마다 덧셈·뺄셈과 자리 옮기기가 붙는데, 자릿수가 몇 개 안 되면 이 부대비용이 곱셈 하나 아낀 이득보다 크기 때문입니다. 이 계산기에서 자릿수 곱셈만 세어도 두 자리끼리는 카라츠바가 다섯 번, 초등학교 방식이 네 번으로 카라츠바가 집니다.
아닙니다. GMP나 파이썬의 큰 정수 연산은 일정 자릿수 아래에서 초등학교 방식으로 되돌아가고, 아주 큰 수에서는 툼-쿡이나 FFT 기반 방식으로 다시 갈아탑니다. 카라츠바는 그 사이 구간을 맡습니다. 이 계산기의 「임계 자릿수」가 바로 그 되돌아가는 지점입니다.
넘칠 수 있습니다. 999 + 999 = 1998처럼 올림이 나면 자릿수가 하나 늘어납니다. 고정 크기 배열로 짜면 여기서 값이 잘리는 것이 이 알고리즘 구현의 1순위 사고입니다. 그 탓에 재귀 깊이도 딱 log₂n에서 멈추지 않아, 8자리끼리 곱하면 3층이 아니라 4층까지 내려갑니다.
한 자리 × 한 자리를 1회로 셉니다. 초등학교 방식으로 p자리와 q자리를 곱하면 정확히 p·q회이고, 카라츠바는 재귀의 잎에서 초등학교 방식을 쓰므로 잎마다 그만큼을 더합니다. 덧셈·뺄셈은 세지 않아 카라츠바에 유리한 셈법인데, 그런데도 작은 수에서는 카라츠바가 집니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 계산은 BigInt로 합니다. 검증은 무작위 수 2,000쌍을 임계 자릿수 1·2·4로 각각 돌려 그냥 곱한 값과 모두 일치하는지 대조해 했습니다.
- 재귀 트리의 모든 노드에서 그 노드의 곱이 두 피연산자의 곱과 같은지, 가운데 항이 (a+b)(c+d) − ac − bd로 나오는지도 확인했습니다.
- 7자리부터는 어떤 무작위 입력에서도 카라츠바의 자릿수 곱셈이 초등학교 방식을 넘지 않는 것을, 2~6자리에서는 넘는 입력이 있는 것을 테스트로 고정해 두었습니다. 두 자리끼리는 늘 5회 대 4회로 카라츠바가 집니다.
- 올림 때문에 (a+b)(c+d) 쪽 재귀가 한 층 더 내려갑니다. 8자리끼리 곱하면 자릿수 곱셈 53회·재귀 호출 79회·깊이 4로, 3⁴ = 81을 그대로 기대하면 어긋납니다. 증가율이 Θ(n^1.585)인 것은 그대로입니다.
- 자릿수 곱셈만 세고 덧셈·뺄셈·자리 옮기기는 세지 않습니다. 세지 않은 그 비용이 작은 수에서 카라츠바를 지게 만드는 원인입니다.
- 24자리까지, 재귀 트리는 3층까지 보입니다. 음수는 다루지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.