Karatsuba Multiplication 편집하기

'''Karatsuba Multiplication''' is a divide-and-conquer algorithm used for fast multiplication of large numbers. It reduces the number of necessary multiplications compared to traditional long multiplication, making it more efficient for large inputs.
==Algorithm Overview==
Karatsuba multiplication breaks two n-digit numbers into smaller parts and recursively computes their product using fewer multiplications.

== History ==
Karatsuba multiplication was discovered by the Russian mathematician '''Anatolii Alexeevitch Karatsuba''' in 1960. The algorithm was first presented at a seminar by Andrey Kolmogorov, who initially believed that the standard multiplication method of O(n²) was the best possible. However, Karatsuba demonstrated a faster method, reducing the number of multiplications required. This discovery laid the foundation for modern fast multiplication algorithms.

== Steps ==
#'''Divide:''' Split two n-digit numbers into two halves.
#*Let X and Y be two numbers of length n.
#*Represent them as:
#**X = 10^m * A + B
#**Y = 10^m * C + D
#*where A, B, C, and D are approximately n/2-digit numbers.
#'''Recursive Multiplication:'''
#*Compute three products instead of four:
#**AC = A × C
#**BD = B × D
#**AD + BC = (A + B) × (C + D) - AC - BD
#'''Combine:'''
#*Result = AC × 10^(2m) + (AD + BC) × 10^m + BD
==Example==
Consider multiplying 1234 × 5678 using Karatsuba’s method:
#'''Divide:'''
#*X = 1234 → A = 12, B = 34
#*Y = 5678 → C = 56, D = 78
#'''Recursive Multiplication:'''
#*AC = 12 × 56 = 672
#*BD = 34 × 78 = 2652
#*(A + B) × (C + D) - AC - BD = (12+34) × (56+78) - 672 - 2652
#*= 46 × 134 - 672 - 2652 = 6164 - 672 - 2652 = 2840
#'''Combine:'''
#*Result = 672 × 10^4 + 2840 × 10^2 + 2652 = 7006652
==Time Complexity==
*'''Traditional multiplication:''' O(n²)
*'''Karatsuba multiplication:''' O(n^(log₂3)) ≈ O(n^1.585)
==Advantages==
*More efficient than traditional multiplication for large numbers.
*Reduces the number of recursive multiplications from 4 to 3.
==Limitations==
*Overhead for small numbers due to recursion.
*Memory usage increases as recursion depth grows.
==Applications==
*'''Cryptography:''' Used for large integer multiplication in encryption algorithms.
*'''Big Number Arithmetic:''' Essential in high-precision computations.
*'''Polynomial Multiplication:''' Applied in symbolic computation and computer algebra.
*'''Fast Fourier Transform (FFT)-based Computations:''' Used in efficient multiplication techniques.
==See Also==
*[[Divide-and-Conquer Algorithm]]
*[[Fast Multiplication]]
*[[Strassen Algorithm]]
*[[FFT Multiplication]]
*[[Computational Complexity]]
[[Category:Algorithm]]