두 정수를 곱하기위한 Karatsuba 알고리즘

곱셈을위한 분할 및 정복 접근법

Unsplash에 Antoine Dautry의 사진

우리 모두는 어렸을 때 두 숫자를 곱하는 방법을 배웠습니다. (😄)를 잊은 경우에는 두 숫자 19와 95를 곱하는 방법을 살펴 보겠습니다.

19와 95를 곱하려면 위에 표시된대로 4 (2²) 기본 연산이 필요합니다. 마찬가지로 123과 456을 곱하려면 9 (3²) 기본 연산이 필요합니다. 따라서 두 개의 n 자리 숫자가 주어지면 일반화하면이 전통적인 접근 방식에는 n² 기본 곱셈 연산이 필요합니다. 따라서이 순진한 접근 방식의 시간 복잡도는 O (n²)입니다.

이것이 두 숫자를 곱하는 유일한 방법입니까? 🤔

1960 년에 Anatoly Alexeyevich Karatsuba라는 러시아 수학자는 두 숫자를 곱하는 새로운 알고리즘을 발견했습니다. 이 알고리즘이 어떻게 작동하는지 살펴 보겠습니다.

Karatsuba 알고리즘

x = 1234 및 y = 5678 인 두 개의 4 자리 숫자 x와 y를 고려해 보겠습니다. 먼저 아래 그림과 같이 n 자리 숫자를 n / 2 자리 숫자로 나누어야합니다.

a와 c는 x와 y의 처음 n / 2 자리를 나타냅니다 . 마찬가지로 b와 d는 x와 y의 마지막 n / 2 자리를 나타냅니다.

Karatsuba 알고리즘은 4 가지 주요 단계로 구성됩니다.

마지막으로 1 단계의 출력에 10ⁿ, 4 단계의 출력에 10 ^ (n / 2)를 곱한 다음 2 단계의 출력에 둘 다 더합니다 (아래 그림 참조).

1234와 5678을 곱하면 7006652가됩니다.

그러나 이것은 어떻게 작동합니까? 🤔

이것을 분해합시다. 위에서 언급했듯이 x = 1234 및 y = 5678로 설정합니다. 또한 a = 12, b = 34, c = 56 및 d = 78을 정의했습니다.

a, b, c, d로 x와 y를 쓰면 :

이제 x와 y를 곱하면 :

1 단계에서 ac를 계산하고 2 단계에서 bd를 계산했습니다. 3 단계에서는 (a + b). (c + d) = ac + ad + bc + bd를 계산했습니다. (ad + bc)를 얻으려면 ac와 bd를 빼야합니다. 이것이 4 단계에서하는 일입니다. 요약하면

이제 이전에 수행 한 4 단계가 모두 의미가 있습니다.

Karatsuba 알고리즘의 Python 구현

 
 #acknowledgement: https://brilliant.org/wiki/karatsuba-algorithm/ 
 
 from math import ceil, floor
 
 #math.ceil(x) Return the ceiling of x as a float, the smallest integer value greater than or equal to x.
 
 #math.floor(x) Return the floor of x as a float, the largest integer value less than or equal to x.
 
 def karatsuba(x,y):
 
     #base case
 
     if x < 10 and y < 10: # in other words, if x and y are single digits
 
         return x*y
 
     n = max(len(str(x)), len(str(y)))
 
     m = ceil(n/2)   #Cast n into a float because n might lie outside the representable range of integers.
 
     x_H  = floor(x / 10**m)
 
     x_L = x % (10**m)
 
     y_H = floor(y / 10**m)
 
     y_L = y % (10**m)
 
     #recursive steps
 
     a = karatsuba(x_H,y_H)
 
     d = karatsuba(x_L,y_L)
 
     e = karatsuba(x_H + x_L, y_H + y_L) - a - d
 
     return int(a*(10**(m*2)) + e*(10**m) + d)

view raw karatsuba.py hosted with ❤ by GitHub

이 구현은 재귀를 사용합니다. 1, 2, 3 단계는 21, 22, 23 행에서 수행됩니다. 마지막으로 4 단계의 출력은 25 행에서 반환됩니다. 재귀 호출에는 종료 조건이 있어야합니다. 여기서 a, b, c, d의 값이 한 자리 (0–9)가되면 재귀가 종료됩니다 (8 행과 9 행).

이 시점에서 한 가지 흥미로운 질문은 다음과 같습니다.

ac, ad, bc, bd를 계산해야합니다. ac 및 bd는 1 단계와 2 단계에서 계산됩니다. 두 개의 추가 단계에서도 ad 및 bc를 계산할 수 있습니다. 그러나 대신 (a + b). (c + d)를 곱한 다음 ac와 bd를 뺍니다. 왜? 🤔

그 이유는 재귀 호출 수를 줄이기 위해서입니다. 현재 구현에는 3 개의 재귀 호출 만 필요합니다. ad와 bc를 따로 계산하면 재귀 수는 4가됩니다. 재귀 호출 수를 최소한으로 유지하면 더 나은 성능을 얻을 수 있습니다.

Karatsuba 알고리즘이 기존 방식보다 어떻게 더 나은가요?

앞서 전통적인 접근 방식이 O (n²) 의 복잡성을 가짐을 확인했습니다. 이제 Karatsuba 알고리즘의 시간 복잡도를 파악해 보겠습니다.

n 자리 숫자 2 개가 주어지면 알고리즘은 n / 2 자리 숫자에서 세 번 반복됩니다. 따라서 복잡성은 다음과 같이 표현할 수 있습니다.

이 문제를 해결하면 시간 복잡성은 다음과 같습니다.

log₂³는 대략 1.585 <2와 같습니다. 따라서 충분히 큰 n의 경우 Karatsuba 알고리즘은 기존의 순진한 접근 방식에 비해 더 나은 성능을 발휘합니다 (실행 시간이 짧음).

기사를 즐겼기를 바랍니다 !!!

참고: https://www.youtube.com/watch?v=JCbZayFr9RE

상호 운용성 데이터 -IoT : R에서 데이터를 송수신하고 Arduino를 제어하는 방법

R과 Arduino (데이터 및 IoT) 간의 데이터 흐름을 통해 상호 운용성을 설정하는 방법

R과 Arduino에 대해 이야기 할 때 둘 다 문자 R을 공유한다는 것 외에 다른 공통점에 대해 이야기 할 수 있습니까? 처음부터 시작하겠습니다. 익숙하지 않은 경우 Arduino는 사용하기 쉬운 하드웨어 (Arduino 보드)와 소프트웨어 (Arduino IDE)를 기반으로하는 오픈 소스 전자 플랫폼입니다. 올바른 유형의 데이터와 데이터를 처리하고 후속 작업을 수행하기위한 일련의 지침이있는 경우이 인기있는 카드에 수행 할 작업을 지정할 수 있습니다.

Interesting For You

9 Hollywood Divas Who Fell In Love With Women

수학 방정식 및 연산 시각화

수학 그래프를 사용하여 방정식의 본질을 포착하고 시각적으로 풀기

방정식의 본질에 대한 시각적 인 조사를 시작하기 전에 방정식은 관계이며 그 관계는 여러 가지 방법으로 기록 될 수 있음을 기억해야합니다. 이 기사 전체에서, 이것은 완전히 새로운 (적어도 나에게는) 사고 방식이기 때문에 오래 전에 배운 오래된 관습을 잊어 버리는 것이 중요합니다.