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