러시아 농부 곱셈법

러시아 농부 곱셈법

A * B 연산이 있을 때

A는 계속 2배로 하고
B는 계속 1/2배로 해서

B가 1이 될때 까지 반복한 결과가
곱셈의 답이 된다는 알고리즘이다.

설명

---

B가 짝수일 때
$A_B = (A_2) * (B/2)$

B가 홀수일 때
$A_B = (A_2) * (B/2) + A$

여기서 나누기 연산은 나머지를 버리는 연산이고, 부족한 A만큼을 채워준다고 생각하면 쉬울 것이다.

따라서 B가 홀수일 때는 A만큼을 더해준다.

증명

---

A*B 연산을 러시아 농부 곱셈법을 이용해서 한다고 하자.

러시아 농부 곱셈법 함수를(Russian Farmer)

RF(A,B)라고 하자.

1. 초기값 증명

1. B가 1일 때
   B가 1이 될 때 까지 반복하는 것이므로 바로 종료
2. 따라서 $RF(A,B)$는 A가 답이 된다.
3. B가 2일 때
   B가 1이 될 때 까지 반복하는 것이므로따라서 $RF(A,B)$는 2A가 답이 된다.
4. $RF(A,B) = (A_2)(B/2) = (A_2)(1) = 2A$

2. B가 k일 때 성립한다고 가정

$RF(A,k) = A*k$ 라고 가정하자

1. k가 짝수일 때
   $RF(2_A,\lfloor \frac{k}{2} \rfloor) = A_k$
2. k가 홀수일 때
   $RF(2_A,\lfloor \frac{k}{2} \rfloor) + A = A_k$

3. B가 2*k일때 증명

$$
\begin{aligned}
RF(A/2, 2_k) &= RF(A, \frac{2_k}{2})
\
&= RF(A, k)
\
&= A*B
\end{aligned}
$$

k+1이 아니고 2*k 일때 증명해서 참이 왜 나오는가?

k 가정에서 임의의 A, k에서 전부 성립한다고 가정을 했다.
홀수 짝수에서 경우의 수가 나뉘는건 나뉨수는 k밖에 존재하지 않는다.

따라서

짝수 홀수로 나뉘는 k를 봤을 때,
각각 다음과 같이 나온다고 가정 했으므로,
$RF(2_A,\lfloor \frac{k}{2} \rfloor) = A_k$

$RF(2_A,\lfloor \frac{k}{2} \rfloor) + A = A_k$

그 이전 단계에서 k일때로 갈 수 있는지 증명하면 된다.
임의의 수(k)에서 성립한다고 했을 때 2k에서 성립함을 증명하면
모든 수(k)에서 성립한다는 것과 같으므로

A가 A/2이고 B가 k*2일 때를 증명해서 참임을 증명하면 된다.

예시

---