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}