[Algorithm Week_1] 여러가지 곱셈 알고리즘

1. Long Multiplication Algorithm

- 우리가 일반적으로 행하는 곱셈 알고리즘

- 어릴때부터 배우던 방식 그대로 곱하면 된다

			9	1	4
X			3	1	4
------------------------------------------------------------------------------------------------------------------------------------
		3	7	3	6
		9	3	4
2	8	0	2
------------------------------------------------------------------------------------------------------------------------------------
2	9	3	2	7	6

 

 

 

2. Lattice Multiplication

- 곱하는 수의 자릿수만큼의 matrix를 만들어준다

 

Ex) 1536 X 314 : 3 X 4 matrix 생성

---

- 이제 여기서 대각선끼리 더한다

- carry가 발생하는 경우 왼쪽 대각선으로 넘겨준다

- 오른쪽 아래 → 왼쪽 위 순서대로 덧셈을 한다

---

 

3. Peasant Multiplication

- x를 계속 2로 나눈다 (x가 0보다 클 동안)

- y는 계속 2를 곱한다

- 여기서 x가 홀수일 경우, prod에 y를 더해준다

- 여기서 x가 짝수일 경우 걍 넘어간다

 

x	y	prod
1534	314	-
767	628	628
383	1256	1884
191	2512	4396
95	5024	9420
47	10048	19468
23	20096	39564
11	40192	79756
5	80384	160140
2	160768	-
1	321536	481676

static int calc(int x, int y){
    int result = 0;

    while(x > 0){
        if(x % 2 != 0){
            result += y;
        }
        x/=2;
        y*=2;
    }

    return result;
}