`std.math.log` computes integer logarithm incorrectly (by using floating point math)

[FedericoStra]

Zig Version

0.12.0-dev.185+49075d205

Steps to Reproduce and Observed Behavior

The current implementation of std.math.log

zig/lib/std/math/log.zig

Lines 30 to 34 in 4d29b39

	// TODO implement integer log without using float math
	.Int => |IntType| switch (IntType.signedness) {
	.signed => @compileError("log not implemented for signed integers"),
	.unsigned => return @as(T, @intFromFloat(@floor(@log(@as(f64, @floatFromInt(x))) / @log(float_base)))),
	},

uses floating point math and as a consequence computes several integer logarithm incorrectly.

Here is a program producing a list of incorrect values:

const std = @import("std");
const math = std.math;
const assert = std.debug.assert;
const Log2Int = math.Log2Int;

/// Returns the logarithm of `x` for the provided `base`, rounding down to the nearest integer.
/// Asserts that `base > 1` and `x != 0`.
pub fn log_int(comptime T: type, base: T, x: T) Log2Int(T) {
    if (@typeInfo(T) != .Int or @typeInfo(T).Int.signedness != .unsigned)
        @compileError("log_int requires an unsigned integer, found " ++ @typeName(T));

    assert(base > 1 and x != 0);

    var exponent: Log2Int(T) = 0;
    var power: T = 1;
    while (power <= x / base) {
        power *= base;
        exponent += 1;
    }

    return exponent;
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    const T = u64;

    // for base = 2, 3, ..., maxInt(T)
    var base: T = 1;
    while (base < math.maxInt(T)) {
        base += 1;

        // for every exponent `exp` such that `base^exp` fits inside `T`
        const max_exp: T = log_int(T, base, math.maxInt(T));
        var exp: T = 0;
        while (exp <= max_exp) : (exp += 1) {
            const n = math.pow(T, base, exp);
            const std_log = math.log(T, base, n); // standard library implementation
            const correct = log_int(T, base, n); // correct result
            if (std_log != correct) {
                try stdout.print("math.log({}, {}, {}) = {}\n", .{ T, base, n, std_log });
                try stdout.print(" log_int({}, {}, {}) = {}\n", .{ T, base, n, correct });
            }
        }
    }
}

and its truncated output:

❯ zig run src/log_int_bug.zig |& head -n 50
math.log(u64, 9, 59049) = 4
 log_int(u64, 9, 59049) = 5
math.log(u64, 9, 3486784401) = 9
 log_int(u64, 9, 3486784401) = 10
math.log(u64, 9, 2541865828329) = 12
 log_int(u64, 9, 2541865828329) = 13
math.log(u64, 9, 205891132094649) = 14
 log_int(u64, 9, 205891132094649) = 15
math.log(u64, 9, 16677181699666569) = 16
 log_int(u64, 9, 16677181699666569) = 17
math.log(u64, 9, 12157665459056928801) = 19
 log_int(u64, 9, 12157665459056928801) = 20
math.log(u64, 11, 19487171) = 6
 log_int(u64, 11, 19487171) = 7
math.log(u64, 11, 379749833583241) = 13
 log_int(u64, 11, 379749833583241) = 14
math.log(u64, 11, 505447028499293771) = 16
 log_int(u64, 11, 505447028499293771) = 17
math.log(u64, 12, 35831808) = 6
 log_int(u64, 12, 35831808) = 7
math.log(u64, 12, 106993205379072) = 12
 log_int(u64, 12, 106993205379072) = 13
math.log(u64, 12, 1283918464548864) = 13
 log_int(u64, 12, 1283918464548864) = 14
math.log(u64, 14, 2744) = 2
 log_int(u64, 14, 2744) = 3
math.log(u64, 14, 38416) = 3
 log_int(u64, 14, 38416) = 4
math.log(u64, 14, 537824) = 4
 log_int(u64, 14, 537824) = 5
math.log(u64, 14, 7529536) = 5
 log_int(u64, 14, 7529536) = 6
math.log(u64, 14, 1475789056) = 7
 log_int(u64, 14, 1475789056) = 8
math.log(u64, 14, 20661046784) = 8
 log_int(u64, 14, 20661046784) = 9
math.log(u64, 14, 289254654976) = 9
 log_int(u64, 14, 289254654976) = 10
math.log(u64, 14, 4049565169664) = 10
 log_int(u64, 14, 4049565169664) = 11
math.log(u64, 14, 56693912375296) = 11
 log_int(u64, 14, 56693912375296) = 12
math.log(u64, 14, 793714773254144) = 12
 log_int(u64, 14, 793714773254144) = 13
math.log(u64, 14, 155568095557812224) = 14
 log_int(u64, 14, 155568095557812224) = 15
math.log(u64, 14, 2177953337809371136) = 15
 log_int(u64, 14, 2177953337809371136) = 16
math.log(u64, 17, 4913) = 2
 log_int(u64, 17, 4913) = 3

As can be easily checked, the value computed by log_int is correct, whereas the one computed by math.log isn't.

Expected Behavior

We expect math functions to compute the correct value.

[FedericoStra]

I've submitted the previous log_int function for addition to the standard library, see #17143.

[FedericoStra]

• fix regular integers: std.math.log_int: implement integer logarithm without using float math #17143
• fix comptime_int: this is still open:

  This patch leaves the comptime_int as is, i.e. broken. I haven't had the time to figure out where should I put the implementation for that. Given that the code for log_int is extremely simple, it should be straightforward for someone with knowledge of the compiler to port the implementation to cover that case too.