大数相乘以及快速幂

发表于 | 分类于

宏观上，我们认为数的相乘为constant time，即O(1). 然而，如果考虑到数的位数，那么乘法操作就变得复杂起来。
如果两个长度为N的数相乘，小学所讲的乘法运算复杂度为O(n^2) –> 对每一位都要进行相乘运算。
另一个方法是karatsuba。

如图所示，基础思想为divide and conquer。
以下为c++代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int get_length(long num) {
	int length = 0;
	while (num > 0) {
		num /= 10;
		length++;
	}
	return length;
}
long long karatsuba(long x, long y) {
	// x = a * 10^(length/2) + b
	// y = c * 10^(length/2) + d
	// x * y = ac * 10^length + bd + ((a + c)*(b + d) - ac - bd)*10^(length/2)
	
	if (x < 10 && y < 10) return x * y;
	
	// calculate a b c d
	int length = max(get_length(x), get_length(y));
	int t = pow(10, length / 2);

	long long a = x / t;
	long long b = x - a * t;
	long long c = y / t;
	long long d = y - c * t;

	// z1 = ac, z2 = bd, z3 = (a+c)*(b+d) - z1 - z2
	long long z1 = karatsuba(a, c);
	long long z2 = karatsuba(b, d);
	long long z3 = karatsuba((a + b), (c + d)) - z1 - z2;

	return z1 * t*t + z2 + z3 * t;
}

在写代码的时候，发现使用long并不会扩张int的取值范围。于是去百度，发现，long的位数由编译器来确定，c语言只规定long位数不低于int。
而我使用的VC，把long定义为4字节，同int一样。

快速幂：
求幂的时候，我们也可以用divide and conquer来缩短运算。如果把相乘看为O(1)，求N次幂显然需要O(N)次运算。
然而，我们可以让底数增大，这样相乘的次数就会减少。例如$2^4 = 2^2 * 2^2$.
于是，运算可以简化为O(logN)
以下是相应代码。

1
2
3
4
5
6
7
8
9
10
double Power(double base, int exponent) {
    int exp = abs(exponent);
    double res = 1.0;
    while (exp) {
        if (exp & 1) res *= base;
        base *= base;
        exp >>= 1;
    }
    return exponent < 0? 1/res:res;
}