魔法师の高塔

Rust学习 2

快速幂算法是计算幂的常用分治算法。从共性上讲,快速斐波那契数列计算也归到此类中。

Demo

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
trait Semigroup{
fn append(&self,x: &Self) -> Self;
}
impl Semigroup for i64 {
fn append(&self, x: &i64) -> i64{
self * x
}
}
#[derive(Debug,Copy,Clone)]
struct Matrix2X2{
a11: i64,
a12: i64,
a21: i64,
a22: i64,
}
impl Matrix2X2 {
fn new(a11: i64,a12: i64,a21: i64,a22: i64) -> Matrix2X2{
Matrix2X2{a11:a11,a12:a12,a21:a21,a22:a22}
}
}
impl Semigroup for Matrix2X2 {
fn append(&self,x: &Matrix2X2) -> Matrix2X2{
Matrix2X2::new(self.a11*x.a11+self.a12*x.a21,
self.a11*x.a12+self.a12*x.a22,
self.a21*x.a11+self.a22*x.a21,
self.a21*x.a12+self.a22*x.a22)
}
}
fn even(x: i64) -> bool{
match x {
_ if x%2==0 => true,
_ => false
}
}
fn quick_pow<T: Semigroup + Copy>(x: &T, n: i64) -> T{
match n {
1 => *x,
_ if even(n) => {
let a = quick_pow(x, n/2);
a.append(&a)
},
_ => {
let a = quick_pow(x, n-1);
x.append(&a)
}
}
}
fn main(){
let a: i64 = 2;
let aa = quick_pow(&a, 30);
println!("{:?}", aa);
let b = Matrix2X2::new(1, 1, 1, 0);
let bb = quick_pow(&b, 20);
println!("{:?}", bb);
}

从类型i64Matrix2X2而言,他们的共性在于这两个类型中的元素都能构成半群,所以抽象出Semigroup这个特质,可以看到i64的乘法与Matrix2X2的乘法在半群定义下的描述,我们也可以针对这两种类型的加法做半群定义。自然,Rust已经为我们准备好了两个Trait,std::ops::Addstd::ops::Mul,基础类型已经实现了这两个特质,我们可以对Matrix2X2实现,然后就能以*+来代替append
在代码中,Matrix2X2自动获得了DebugCopyClone特质,Debug是用来描述类型,CopyClone用来实现深复制,即先拷贝内容到新内存区域,然后将新内存区域和这个标识符绑定,而原资源的所有权不发生转移。