数论算法
1. x*y
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| /**
* x乘以y
* 限制：y >= 0
*
* 原理: | (x*(y>>1))<<1 y偶数
* x * y = | x + (x*(y>>1))<<1 y奇数
* | 0 y == 0
* @param x
* @param y
* @return
*/
private static int doMuliply(int x, int y) {
if (y == 0) return 0;
int z = doMuliply(x, y >> 1);
return NumberUtils.isEven(y) ? z << 1 : x + (z << 1);
}
|
2. x/y
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| /**
* x除以y
* 限制：x > 0 ，y > 0
*
* | ArithmeticException y == 0
* 原理 | (0, 0) x == 0
* x / y = | (q'<<1, r'<<1) 其中(q',r')=(x>>1)/y x偶数
* | (q'<<1, r'<<1 + 1) 其中(q',r')=(x>>1)/y x奇数
* @param x
* @param y
* @return : 商，余
*/
public static Pair<Integer, Integer> doDivide(int x, int y) {
if (y == 0) throw new ArithmeticException();
if (x == 0) return Pair.build(0, 0);
Pair<Integer, Integer> half = doDivide(x >> 1, y);
int left = half.getLeft() << 1;
int right = half.getRight() << 1;
if (NumberUtils.isOdd(x)) right += 1;
return (right < y) ? Pair.build(left, right) : Pair.build(left+1, right-y);
}
|
3. pow(x, y) % N
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| /**
* pow(x, y) % N
* 限制：x > 0, y > 0, N > 1
*
* 原理: | (pow(x, y>>1) << 1) % N y是偶数
* pow(x, y) % N =|
* | x * (pow(x, y>>1) << 1) % N y是奇数
* @param x
* @param y
* @param N
* @return
*/
public static int powerMod(int x, int y, int N){
if(y == 0) return 1;
int half = powerMod(x, y>>1, N);
return NumberUtils.isEven(y) ? (half * half) % N : (x *half * half) % N;
}
|
4. 欧几里德GCD算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| /**
* GCD(x, y)
* 限制：x > y > 0
*
* 原理：
* GCD(x, y) = GCD(y, x%y)
*
* @param x
* @param y
* @return
*/
public static int gcd(int x, int y){
if(y == 0) return x;
return gcd(y, x % y);
}
|
5. 素数测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /**
* 素数测试
* 限制：x > 0, K > 0
*
* 原理：
* 费马定理：如果p是素数，则对任意的 1 <= a < x,有 pow(a, x-1) = 1 (mod x)
* 这是素数的必要条件，但不是充分条件。
* 随机选k个a，分别用费马定理去测试。
*
* @param x
* @return
*/
public static boolean isPrime(int x, int K) {
for (int i = 0; i < K; i++) {
int a = (int)(Math.random() * x);
if(powerMod(a, x-1, x) != 1){
return false;
}
}
return true;
}
|
总结：
《Algorithm》这本书我的理解，关注更多的是工业级别（或者说实用级别）的算法，这一点和算法导论不同，算法导论可以说是学院派，这个是工程师派。
比如上面的素数测试，这本书利用多次费马定理，从而降低误判概率（理论上还是存在误判的情况），但是正像作者说的，很多伟大的算法，都是很大概率正确的算法（而不是完全正确）。