Repository navigation
Expand file tree
/
Copy pathmath.cairo
More file actions
83 lines (78 loc) · 1.76 KB
/
Copy pathmath.cairo
File metadata and controls
83 lines (78 loc) · 1.76 KB
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
use math::Oneable;
// @notice Computes `base ^ exp`
// @param base The base of the exponentiation
// @param exp The exponent of the exponentiation
// @return The exponentiation result
fn pow<
T,
impl TZeroable: Zeroable<T>,
impl TOneable: Oneable<T>,
impl TCopy: Copy<T>,
impl TDrop: Drop<T>,
impl TAdd: Add<T>,
impl TSub: Sub<T>,
impl TMul: Mul<T>,
impl TDiv: Div<T>,
impl TRem: Rem<T>,
impl TPartialEq: PartialEq<T>,
impl TPartialOrd: PartialOrd<T>
>(
mut base: T, mut exp: T
) -> T {
let two = TOneable::one() + TOneable::one();
let four = two + two;
let sixteen = four * four;
if exp < sixteen {
slow_pow(base, exp)
} else {
fast_pow(base, exp)
}
}
fn slow_pow<
T,
impl TZeroable: Zeroable<T>,
impl TSub: Sub<T>,
impl TMul: Mul<T>,
impl TOneable: Oneable<T>,
impl TCopy: Copy<T>,
impl TDrop: Drop<T>
>(
base: T, mut exp: T
) -> T {
if exp.is_zero() {
TOneable::one()
} else {
base * slow_pow(base, exp - TOneable::one())
}
}
fn fast_pow<
T,
impl TZeroable: Zeroable<T>,
impl TOneable: Oneable<T>,
impl TCopy: Copy<T>,
impl TDrop: Drop<T>,
impl TAdd: Add<T>,
impl TSub: Sub<T>,
impl TMul: Mul<T>,
impl TDiv: Div<T>,
impl TRem: Rem<T>,
impl TPartialEq: PartialEq<T>
>(
mut base: T, mut exp: T
) -> T {
let mut ans = TOneable::one();
loop {
if exp.is_zero() {
break ans;
}
let two = TOneable::one() + TOneable::one();
let mm = exp % two;
if mm == TOneable::one() {
ans = ans * base;
exp = exp - TOneable::one();
} else {
base = base * base;
exp = exp / two;
};
}
}