[toc]
0x1::math64
use 0x1::error;
use 0x1::fixed_point32;常数
AI注：不能对值0取以2为底的对数。
const EINVALID_ARG_FLOOR_LOG2: u64 = 1;函数
max
返回两个数中较大的一个。
public fun max(a: u64, b: u64): u64实现
public fun max(a: u64, b: u64): u64 {
if (a >= b) a else b
}min
返回两个数中较小的一个。
public fun min(a: u64, b: u64): u64实现
public fun min(a: u64, b: u64): u64 {
if (a < b) a else b
}average
返回两个数的平均值。
public fun average(a: u64, b: u64): u64实现
public fun average(a: u64, b: u64): u64 {
if (a < b) {
a + (b - a) / 2
} else {
b + (a - b) / 2
}
}gcd
通过欧几里得算法返回a和b的最大公约数。
public fun gcd(a: u64, b: u64): u64实现
public inline fun gcd(a: u64, b: u64): u64 {
let (large, small) = if (a > b) (a, b) else (b, a);
while (small != 0) {
let tmp = small;
small = large % small;
large = tmp;
};
large
}mul_div
通过u128计算a * b / c以防止中间溢出。
public fun mul_div(a: u64, b: u64, c: u64): u64实现
public inline fun mul_div(a: u64, b: u64, c: u64): u64 {
assert!(c != 0, std::error::invalid_argument(4));
(((a as u128) * (b as u128) / (c as u128)) as u64)
}clamp
将x限制在区间[lower, upper]内。
public fun clamp(x: u64, lower: u64, upper: u64): u64实现
public fun clamp(x: u64, lower: u64, upper: u64): u64 {
min(upper, max(lower, x))
}pow
返回n的e次幂。
public fun pow(n: u64, e: u64): u64实现
public fun pow(n: u64, e: u64): u64 {
if (e == 0) {
1
} else {
let p = 1;
while (e > 1) {
if (e % 2 == 1) {
p = p * n;
};
e = e / 2;
n = n * n;
};
p * n
}
}floor_log2
返回x的以2为底的对数的向下取整值。
public fun floor_log2(x: u64): u8实现
public fun floor_log2(x: u64): u8 {
let res = 0;
assert!(x != 0, std::error::invalid_argument(EINVALID_ARG_FLOOR_LOG2));
let n = 32;
while (n > 0) {
if (x >= (1 << n)) {
x = x >> n;
res = res + n;
};
n = n >> 1;
};
res
}log2
计算以2为底的对数。
public fun log2(x: u64): fixed_point32::FixedPoint32实现
public fun log2(x: u64): FixedPoint32 {
let integer_part = floor_log2(x);
// 将x规范化到[1, 2)区间内，以进行定点32位计算。
let y = (if (x >= 1 << 32) {
x >> (integer_part - 32)
} else {
x << (32 - integer_part)
} as u128);
let frac = 0;
let delta = 1 << 31;
while (delta != 0) {
// log x = 1/2 log x^2
// x在[1, 2)区间内
y = (y * y) >> 32;
// 现在x在[1, 4)区间内
// 如果x在[2, 4)区间内，那么log x = 1 + log (x / 2)
if (y >= (2 << 32)) { frac = frac + delta; y = y >> 1; };
delta = delta >> 1;
};
fixed_point32::create_from_raw_value (((integer_part as u64) << 32) + frac)
}sqrt
返回x的平方根，精确到floor(sqrt(x))。
public fun sqrt(x: u64): u64实现
public fun sqrt(x: u64): u64 {
if (x == 0) return 0;
let res = 1 << ((floor_log2(x) + 1) >> 1);
// 使用标准牛顿-拉弗森迭代法改进初始近似值。
// 误差项演进为delta_i+1 = delta_i^2 / 2（二次收敛）。
// 经过4次迭代后，delta小于2^-32，因此低于阈值。
res = (res + x / res) >> 1;
res = (res + x / res) >> 1;
res = (res + x / res) >> 1;
res = (res + x / res) >> 1;
min(res, x / res)
}ceil_div
返回x除以y后向上取整的结果。
public fun ceil_div(x: u64, y: u64): u64实现
public inline fun ceil_div(x: u64, y: u64): u64 {
// ceil_div(x, y) = floor((x + y - 1) / y) = floor((x - 1) / y) + 1
// (x + y - 1) 可能会导致错误溢出，因此我们使用后一种版本
if (x == 0) {
assert!(y != 0, std::error::invalid_argument(4));
0
}
else (x - 1) / y + 1
}规格说明
max
public fun max(a: u64, b: u64): u64如果false，则中止。
确保如果a >= b，则结果为a；如果a < b，则结果为b。
min
public fun min(a: u64, b: u64): u64如果false，则中止。
确保如果a < b，则结果为a；如果a >= b，则结果为b。
average
public fun average(a: u64, b: u64): u64特性 opaque；如果false，则中止。
确保结果为(a + b) / 2。
clamp
public fun clamp(x: u64, lower: u64, upper: u64): u64需要(lower <= upper)；如果false，则中止。
确保如果(lower <= x && x <= upper)，则结果为x；如果x < lower，则结果为lower；如果upper < x，则结果为upper。
pow
public fun pow(n: u64, e: u64): u64特性 opaque；如果[abstract] spec_pow(n, e) > MAX_U64，则中止。
确保[abstract] result == spec_pow(n, e)。
floor_log2
public fun floor_log2(x: u64): u8特性 opaque；如果[abstract] x == 0，则中止。
确保[abstract] spec_pow(2, result) <= x；确保[abstract] x < spec_pow(2, result+1)。
sqrt
public fun sqrt(x: u64): u64特性 opaque；如果[abstract] false，则中止。
确保如果x > 0，则result * result <= x；确保如果x > 0，则x < (result+1) * (result+1)。
spec_pow
fun spec_pow(n: u64, e: u64): u64 {
if (e == 0) {
1
}
else {
n * spec_pow(n, e-1)
}
}