std.math.log_int.assert
别名
别名目标 std.debug.assert
std.math.log_int.log_int
函数
返回以给定 base 为底的 x 的对数,向下舍入到最接近的整数。
断言 base > 1 且 x > 0。
pub fn log_int(comptime T: type, base: T, x: T) Log2Int(T)
参数
T: type
base: T
x: T
std.math.log_int.Log2Int
别名
别名目标 std.math.Log2Int
std.math.log_int.math
别名
别名目标 std.math
std.math.log_int.std
别名
别名目标 std
std.math.log_int.testing
别名
别名目标 std.testing
源码
std/math/log_int.zig
const std = @import("../std.zig");
const math = std.math;
const testing = std.testing;
const assert = std.debug.assert;
const Log2Int = math.Log2Int;
/// 返回以给定 `base` 为底的 `x` 的对数,向下舍入到最接近的整数。
/// 断言 `base > 1` 且 `x > 0`。
pub fn log_int(comptime T: type, base: T, x: T) Log2Int(T) {
const valid = switch (@typeInfo(T)) {
.comptime_int => true,
.int => |IntType| IntType.signedness == .unsigned,
else => false,
};
if (!valid) @compileError("log_int requires an unsigned integer, found " ++ @typeName(T));
assert(base > 1 and x > 0);
if (base == 2) return math.log2_int(T, x);
// 用 [y] 表示 y 的整数部分。
// 整个迭代过程保持以下不变量:
// power = base ^ exponent
// 安全性与终止性。
//
// 循环内部不会溢出,因为进入循环时有:
// power <= [maxInt(T) / base]
// 因此:
// power * base <= maxInt(T)
// 是类型 `T` 的合法乘法,而
// exponent + 1 <= log(base, maxInt(T)) <= log2(maxInt(T)) <= maxInt(Log2Int(T))
// 是类型 `Log2Int(T)` 的合法加法。
//
// 这也保证了终止性,因为 power 严格递增,
// 最终必定超过 [x / base] < maxInt(T),从而退出循环。
var exponent: Log2Int(T) = 0;
var power: T = 1;
while (power <= x / base) {
power *= base;
exponent += 1;
}
// 若从未进入循环,必有:
// [x / base] < 1
// 因此:
// x <= [x / base] * base < base
// 所以结果为 0,可直接返回仍为 0 的 exponent。
//
// 否则,若至少进入循环一次,
// 退出循环时,power 可被 base 整除,且有:
// power / base <= [x / base] < power
// 因此:
// power <= [x / base] * base <= x < power * base
// 这意味着:
// base^exponent <= x < base^(exponent+1)
// 因此结果为 exponent。
return exponent;
}
test "log_int" {
@setEvalBranchQuota(2000);
// 测试所有位宽为 2、3、……、64 的无符号整数类型。
// 无法测试 0 位或 1 位,因为底数必须大于 1。
inline for (2..64 + 1) |bits| {
const T = @Int(.unsigned, @intCast(bits));
// 对于 base = 2, 3, ..., min(maxInt(T),1024)
var base: T = 1;
while (base < math.maxInt(T) and base <= 1024) {
base += 1;
// 测试 `log_int(T, base, 1) == 0`
try testing.expectEqual(@as(Log2Int(T), 0), log_int(T, base, 1));
// 对于适合 T 的幂 `pow = base^exp > 1`,
// 测试 `log_int` 是否正确检测到对数
// 从 `log(pow-1) == exp-1` 到 `log(pow) == exp` 的跃迁。
var exp: Log2Int(T) = 0;
var pow: T = 1;
while (pow <= math.maxInt(T) / base) {
exp += 1;
pow *= base;
try testing.expectEqual(exp - 1, log_int(T, base, pow - 1));
try testing.expectEqual(exp, log_int(T, base, pow));
}
}
}
}
test "log_int vs math.log2" {
const types = [_]type{ u2, u3, u4, u8, u16 };
inline for (types) |T| {
var n: T = 0;
while (n < math.maxInt(T)) {
n += 1;
const special = math.log2_int(T, n);
const general = log_int(T, 2, n);
try testing.expectEqual(special, general);
}
}
}
test "log_int vs math.log10" {
const types = [_]type{ u4, u5, u6, u8, u16 };
inline for (types) |T| {
var n: T = 0;
while (n < math.maxInt(T)) {
n += 1;
const special = math.log10_int(n);
const general = log_int(T, 10, n);
try testing.expectEqual(special, general);
}
}
}
test "log_int at comptime" {
const x = 59049; // 9 ** 5;
comptime {
if (math.log_int(comptime_int, 9, x) != 5) {
@compileError("log(9, 59049) should be 5");
}
}
}