1const std = @import("../std.zig");
2const testing = std.testing;
3
4/// Returns the base-10 logarithm of x.
5///
6/// Special Cases:
7/// - log10(+inf) = +inf
8/// - log10(0) = -inf
9/// - log10(x) = nan if x < 0
10/// - log10(nan) = nan
11pub fn log10(x: anytype) @TypeOf(x) {
12 const T = @TypeOf(x);
13 switch (@typeInfo(T)) {
14 .comptime_float => {
15 return @as(comptime_float, @log10(x));
16 },
17 .float => return @log10(x),
18 .comptime_int => {
19 const Int = @Int(
20 if (x < 0) .signed else .unsigned,
21 // We let log10_int check if x is 0, for a nicer error message.
22 @max(16, if (x == 0) 0 else 1 + std.math.log2(x)),
23 );
24 return @as(comptime_int, log10_int(@as(Int, x)));
25 },
26 .int => |IntType| switch (IntType.signedness) {
27 .signed => @compileError("log10 not implemented for signed integers"),
28 .unsigned => return log10_int(x),
29 },
30 else => @compileError("log10 not implemented for " ++ @typeName(T)),
31 }
32}
33
34// Based on Rust, which is licensed under the MIT license.
35// https://github.com/rust-lang/rust/blob/f63ccaf25f74151a5d8ce057904cd944074b01d2/LICENSE-MIT
36//
37// https://github.com/rust-lang/rust/blob/f63ccaf25f74151a5d8ce057904cd944074b01d2/library/core/src/num/int_log10.rs
38
39/// Return the log base 10 of integer value x, rounding down to the
40/// nearest integer.
41pub fn log10_int(x: anytype) std.math.Log2Int(@TypeOf(x)) {
42 const T = @TypeOf(x);
43 const OutT = std.math.Log2Int(T);
44 if (@typeInfo(T) != .int or @typeInfo(T).int.signedness != .unsigned)
45 @compileError("log10_int requires an unsigned integer, found " ++ @typeName(T));
46
47 std.debug.assert(x != 0);
48
49 const bit_size = @typeInfo(T).int.bits;
50
51 if (bit_size <= 8) {
52 return @as(OutT, @intCast(log10_int_u8(x)));
53 } else if (bit_size <= 16) {
54 return @as(OutT, @intCast(less_than_5(x)));
55 }
56
57 var val = x;
58 var log: u32 = 0;
59
60 inline for (0..11) |i| {
61 // Unnecessary branches should be removed by the compiler
62 if (bit_size > (1 << (11 - i)) * 5 * @log2(10.0) and val >= pow10((1 << (11 - i)) * 5)) {
63 const num_digits = (1 << (11 - i)) * 5;
64 val /= pow10(num_digits);
65 log += num_digits;
66 }
67 }
68
69 if (val >= pow10(5)) {
70 val /= pow10(5);
71 log += 5;
72 }
73
74 return @as(OutT, @intCast(log + less_than_5(@as(u32, @intCast(val)))));
75}
76
77fn pow10(comptime y: comptime_int) comptime_int {
78 if (y == 0) return 1;
79
80 var squaring = 0;
81 var s = 1;
82
83 while (s <= y) : (s <<= 1) {
84 squaring += 1;
85 }
86
87 squaring -= 1;
88
89 var result = 10;
90
91 for (0..squaring) |_| {
92 result *= result;
93 }
94
95 const rest_exp = y - (1 << squaring);
96
97 return result * pow10(rest_exp);
98}
99
100inline fn log10_int_u8(x: u8) u32 {
101 // For better performance, avoid branches by assembling the solution
102 // in the bits above the low 8 bits.
103
104 // Adding c1 to val gives 10 in the top bits for val < 10, 11 for val >= 10
105 const C1: u32 = 0b11_00000000 - 10; // 758
106 // Adding c2 to val gives 01 in the top bits for val < 100, 10 for val >= 100
107 const C2: u32 = 0b10_00000000 - 100; // 412
108
109 // Value of top bits:
110 // +c1 +c2 1&2
111 // 0..=9 10 01 00 = 0
112 // 10..=99 11 01 01 = 1
113 // 100..=255 11 10 10 = 2
114 return ((x + C1) & (x + C2)) >> 8;
115}
116
117inline fn less_than_5(x: u32) u32 {
118 // Similar to log10u8, when adding one of these constants to val,
119 // we get two possible bit patterns above the low 17 bits,
120 // depending on whether val is below or above the threshold.
121 const C1: u32 = 0b011_00000000000000000 - 10; // 393206
122 const C2: u32 = 0b100_00000000000000000 - 100; // 524188
123 const C3: u32 = 0b111_00000000000000000 - 1000; // 916504
124 const C4: u32 = 0b100_00000000000000000 - 10000; // 514288
125
126 // Value of top bits:
127 // +c1 +c2 1&2 +c3 +c4 3&4 ^
128 // 0..=9 010 011 010 110 011 010 000 = 0
129 // 10..=99 011 011 011 110 011 010 001 = 1
130 // 100..=999 011 100 000 110 011 010 010 = 2
131 // 1000..=9999 011 100 000 111 011 011 011 = 3
132 // 10000..=99999 011 100 000 111 100 100 100 = 4
133 return (((x + C1) & (x + C2)) ^ ((x + C3) & (x + C4))) >> 17;
134}
135
136test log10_int {
137 inline for (
138 .{ u8, u16, u32, u64, u128, u256, u512 },
139 .{ 2, 4, 9, 19, 38, 77, 154 },
140 ) |T, max_exponent| {
141 for (0..max_exponent + 1) |exponent_usize| {
142 const exponent: std.math.Log2Int(T) = @intCast(exponent_usize);
143 const power_of_ten = try std.math.powi(T, 10, exponent);
144
145 if (exponent > 0) {
146 try testing.expectEqual(exponent - 1, log10_int(power_of_ten - 9));
147 try testing.expectEqual(exponent - 1, log10_int(power_of_ten - 1));
148 }
149 try testing.expectEqual(exponent, log10_int(power_of_ten));
150 try testing.expectEqual(exponent, log10_int(power_of_ten + 1));
151 try testing.expectEqual(exponent, log10_int(power_of_ten + 8));
152 }
153 try testing.expectEqual(max_exponent, log10_int(@as(T, std.math.maxInt(T))));
154 }
155}
156
157test "log10 with comptime types" {
158 try testing.expectEqual(0, log10(2));
159 try testing.expectEqual(2.0, log10(100.0));
160 try testing.expectEqual(2, log10(123));
161 try testing.expectEqual(3.0, log10(1000.0));
162}