1const std = @import("../std.zig");
2const math = std.math;
3const testing = std.testing;
4const assert = std.debug.assert;
5const Log2Int = math.Log2Int;
6
7/// Returns the logarithm of `x` for the provided `base`, rounding down to the nearest integer.
8/// Asserts that `base > 1` and `x > 0`.
9pub fn log_int(comptime T: type, base: T, x: T) Log2Int(T) {
10 const valid = switch (@typeInfo(T)) {
11 .comptime_int => true,
12 .int => |IntType| IntType.signedness == .unsigned,
13 else => false,
14 };
15 if (!valid) @compileError("log_int requires an unsigned integer, found " ++ @typeName(T));
16
17 assert(base > 1 and x > 0);
18 if (base == 2) return math.log2_int(T, x);
19
20 // Let's denote by [y] the integer part of y.
21
22 // Throughout the iteration the following invariant is preserved:
23 // power = base ^ exponent
24
25 // Safety and termination.
26 //
27 // We never overflow inside the loop because when we enter the loop we have
28 // power <= [maxInt(T) / base]
29 // therefore
30 // power * base <= maxInt(T)
31 // is a valid multiplication for type `T` and
32 // exponent + 1 <= log(base, maxInt(T)) <= log2(maxInt(T)) <= maxInt(Log2Int(T))
33 // is a valid addition for type `Log2Int(T)`.
34 //
35 // This implies also termination because power is strictly increasing,
36 // hence it must eventually surpass [x / base] < maxInt(T) and we then exit the loop.
37
38 var exponent: Log2Int(T) = 0;
39 var power: T = 1;
40 while (power <= x / base) {
41 power *= base;
42 exponent += 1;
43 }
44
45 // If we never entered the loop we must have
46 // [x / base] < 1
47 // hence
48 // x <= [x / base] * base < base
49 // thus the result is 0. We can then return exponent, which is still 0.
50 //
51 // Otherwise, if we entered the loop at least once,
52 // when we exit the loop we have that power is exactly divisible by base and
53 // power / base <= [x / base] < power
54 // hence
55 // power <= [x / base] * base <= x < power * base
56 // This means that
57 // base^exponent <= x < base^(exponent+1)
58 // hence the result is exponent.
59
60 return exponent;
61}
62
63test "log_int" {
64 @setEvalBranchQuota(2000);
65 // Test all unsigned integers with 2, 3, ..., 64 bits.
66 // We cannot test 0 or 1 bits since base must be > 1.
67 inline for (2..64 + 1) |bits| {
68 const T = @Int(.unsigned, @intCast(bits));
69
70 // for base = 2, 3, ..., min(maxInt(T),1024)
71 var base: T = 1;
72 while (base < math.maxInt(T) and base <= 1024) {
73 base += 1;
74
75 // test that `log_int(T, base, 1) == 0`
76 try testing.expectEqual(@as(Log2Int(T), 0), log_int(T, base, 1));
77
78 // For powers `pow = base^exp > 1` that fit inside T,
79 // test that `log_int` correctly detects the jump in the logarithm
80 // from `log(pow-1) == exp-1` to `log(pow) == exp`.
81 var exp: Log2Int(T) = 0;
82 var pow: T = 1;
83 while (pow <= math.maxInt(T) / base) {
84 exp += 1;
85 pow *= base;
86
87 try testing.expectEqual(exp - 1, log_int(T, base, pow - 1));
88 try testing.expectEqual(exp, log_int(T, base, pow));
89 }
90 }
91 }
92}
93
94test "log_int vs math.log2" {
95 const types = [_]type{ u2, u3, u4, u8, u16 };
96 inline for (types) |T| {
97 var n: T = 0;
98 while (n < math.maxInt(T)) {
99 n += 1;
100 const special = math.log2_int(T, n);
101 const general = log_int(T, 2, n);
102 try testing.expectEqual(special, general);
103 }
104 }
105}
106
107test "log_int vs math.log10" {
108 const types = [_]type{ u4, u5, u6, u8, u16 };
109 inline for (types) |T| {
110 var n: T = 0;
111 while (n < math.maxInt(T)) {
112 n += 1;
113 const special = math.log10_int(n);
114 const general = log_int(T, 10, n);
115 try testing.expectEqual(special, general);
116 }
117 }
118}
119
120test "log_int at comptime" {
121 const x = 59049; // 9 ** 5;
122 comptime {
123 if (math.log_int(comptime_int, 9, x) != 5) {
124 @compileError("log(9, 59049) should be 5");
125 }
126 }
127}