KARATSUBA

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

const int MAX_NUMBER_SIZE = 1024;

vector<int> karatsuba(vector<int> &a, vector<int> &b);
void exponential(vector<int> &a, int k);
void addTo(vector<int> &a, vector<int> &b);
void subFrom(vector<int> &a, vector<int> &b);
vector<int> multiply(const vector<int> &a, const vector<int> &b);
void normalize(vector<int> &c);
int getLength(char *arr);

int main()
{
	int caseNum = 0;
	char firstInput[MAX_NUMBER_SIZE], secondInput[MAX_NUMBER_SIZE];
	vector<int> first, second;

	cin >> caseNum;
	cin.ignore();

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		cin.getline(firstInput, MAX_NUMBER_SIZE);
		cin.getline(secondInput, MAX_NUMBER_SIZE);

		for (int i = getLength(firstInput) - 1; i >= 0; i--)
		{
			first.push_back(firstInput[i] - '0');
		}
		for (int i = getLength(secondInput) - 1; i >= 0; i--)
		{
			second.push_back(secondInput[i] - '0');
		}

		auto result = karatsuba(first, second);

		for (int i = result.size() - 1; i >= 0; i--)
		{
			cout << result[i];
		}
		cout << endl;
	}
}

vector<int> karatsuba(vector<int> &a, vector<int> &b)
{
	int half = a.size() / 2;

	if (a.size() <= 50) return multiply(a, b);

	vector<int> a0(a.begin(), a.begin() + half);
	vector<int> a1(a.begin() + half, a.end());
	vector<int> b0(b.begin(), b.begin() + half);
	vector<int> b1(b.begin() + half, b.end());

	vector<int> z0 = karatsuba(a0, b0);
	vector<int> z1 = karatsuba(a1, b1);
	addTo(a0, a1);
	addTo(b0, b1);
	vector<int> z2 = karatsuba(a0, b0);
	subFrom(z2, z0);
	subFrom(z2, z1);

	exponential(z1, half + half);
	exponential(z2, half);
	addTo(z1, z2);
	addTo(z1, z0);

	normalize(z1);
	return z1;
}

void exponential(vector<int> &a, int k)
{
	for (int i = 0; i < k; i++)
		a.insert(a.begin(), 0);
}

void addTo(vector<int> &a, vector<int> &b)
{
	int i;
	for (i = 0; i < a.size(); i++)
	{
		if (i < b.size()) a[i] += b[i];
	}

	while (i < b.size())
	{
		a.push_back(b[i]);
		i++;
	}
}

void subFrom(vector<int> &a, vector<int> &b)
{
	int i = 0;
	for (i = 0; i < a.size(); i++)
	{
		if (i < b.size()) a[i] -= b[i];
	}

	while (i < b.size())
	{
		a.push_back(-b[i]);
		i++;
	}
}



vector<int> multiply(const vector<int> &a, const vector<int> &b)
{
	vector<int> c(a.size() + b.size() + 1);
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < b.size(); j++)
		{
			c[i + j] += a[i] * b[j];
		}
	}

	normalize(c);
	
	return c;
}

void normalize(vector<int> &c)
{
	c.push_back(0);

	for (int i = 0; i < c.size() - 1; i++)
	{
		if (c[i] < 0)
		{
			int borrow = (abs(c[i]) + 9) / 10;
			c[i + 1] -= borrow;
			c[i] += borrow * 10;
		}
		else
		{
			c[i + 1] += c[i] / 10;
			c[i] %= 10;
		}
	}
	while (c.size() > 1 && c.back() == 0) c.pop_back();
}

int getLength(char *arr)
{
	int cnt = 0;
	while (arr[cnt] != NULL)
	{
		cnt++;
	}
	return cnt;
}

Karatsuba 곱셈 성능 비교

Karatsuba 알고리즘과 O(n^2) 알고리즘의 비교표

n	Karatsuba 알고리즘	O(n^2) 알고리즘
1000	371 ms	712 ms
10,000	16,306 ms	72,724 ms
100,000	487,913 ms	7,382,174 ms

개발 하면서 든 생각

책에 보면 b0, b1 을 선언할 때 b.begin() + min<int>(b.size(), half) 를 사용하는 데 왜 굳이 이렇게 사용하는지 이유를 모르겠다..

어차피 a 랑 b 랑 같은 길이의 정수이면 똑같이 절반씩 나누어질텐데 싶어서 그냥 half 로 두고 코딩을 하였다. 즉,

b0(b.begin(), b.begin() + min<int>(b.size(), half); 대신에 b0(b.begin(), b.begin() + half); 로 작성하였다. 일단 길이가 똑같은 두 정수 몇 개를 input 값으로 넣어보았는데 잘 작동한다. 혹시 누군가가 min() 을 사용해야 하는 이유를 알려주면 참 좋겠다 크윽..

UPDATED (20181214)

min() 함수를 써야 하는 건 input 정수의 길이가 2의 제곱수가 아닐 경우가 있기 때문이다. 2의 제곱수가 아닐 경우 반으로 나눠질 때 한쪽보다 다른 한 쪽의 길이가 더 작아질 수 있다. 그래서 half 대신 min<int>(b.size(), half) 를 쓰나보다.

UPDATED (20181215)

그런데 다시 생각해보니 2의 제곱수가 아니어도 절반씩 나누어지는 건 똑같고, 만일 n 이 홀수라면 an = n/2 + 1, bn = n/2 개로 나누어 질 것이다. 그럼 an, bn 을 가지고 다시 karatsuba()를 수행하면 an 의 half 가 bn 보다 커질리가 없을텐데 라는 생각이 든다. 그리고 n <= 50 이면 karatsuba() 대신 multiply() 를 사용하니까 사실상 an - bn = 1 정도의 차이는 무시해도 되지 않을까..

KaratsubaInput.txt

KaratsubaOutput.txt