最大公约数(https://mathworld.wolfram.com/GreatestCommonDivisor.html)
std.math.gcd.gcd
函数
返回不同时为零的两个无符号整数(a 和 b)的最大公约数(GCD)。
例如,8 和 12 的最大公约数是 4,即 gcd(8, 12) == 4。
pub fn gcd(a: anytype, b: anytype) @TypeOf(a, b)
用法示例
test gcd {
const expectEqual = std.testing.expectEqual;
try expectEqual(gcd(0, 5), 5);
try expectEqual(gcd(5, 0), 5);
try expectEqual(gcd(8, 12), 4);
try expectEqual(gcd(12, 8), 4);
try expectEqual(gcd(33, 77), 11);
try expectEqual(gcd(77, 33), 11);
try expectEqual(gcd(49865, 69811), 9973);
try expectEqual(gcd(300_000, 2_300_000), 100_000);
try expectEqual(gcd(90000000_000_000_000_000_000, 2), 2);
try expectEqual(gcd(@as(u80, 90000000_000_000_000_000_000), 2), 2);
try expectEqual(gcd(300_000, @as(u32, 2_300_000)), 100_000);
}
std.math.gcd.std
别名
别名目标 std
源码
std/math/gcd.zig
//! 最大公约数(https://mathworld.wolfram.com/GreatestCommonDivisor.html)
const std = @import("std");
/// 返回不同时为零的两个无符号整数(`a` 和 `b`)的最大公约数(GCD)。
/// 例如,`8` 和 `12` 的最大公约数是 `4`,即 `gcd(8, 12) == 4`。
pub fn gcd(a: anytype, b: anytype) @TypeOf(a, b) {
const N = switch (@TypeOf(a, b)) {
// 为 @ctz 将 comptime_int 转换为某个固定大小整数类型。
comptime_int => std.math.IntFittingRange(@min(a, b), @max(a, b)),
else => |T| T,
};
if (@typeInfo(N) != .int or @typeInfo(N).int.signedness != .unsigned) {
@compileError("`a` and `b` must be usigned integers");
}
// 使用优化形式的 Stein 算法:
// https://en.wikipedia.org/wiki/Binary_GCD_algorithm
std.debug.assert(a != 0 or b != 0);
if (a == 0) return b;
if (b == 0) return a;
var x: N = a;
var y: N = b;
const xz = @ctz(x);
const yz = @ctz(y);
const shift = @min(xz, yz);
x >>= @intCast(xz);
y >>= @intCast(yz);
var diff = y -% x;
while (diff != 0) : (diff = y -% x) {
// ctz 在取负操作下保持不变,
// 将其放在这里以减轻数据依赖,
// 使 CPU 执行更顺畅。
const zeros = @ctz(diff);
if (x > y) diff = -%diff;
y = @min(x, y);
x = diff >> @intCast(zeros);
}
return y << @intCast(shift);
}
test gcd {
const expectEqual = std.testing.expectEqual;
try expectEqual(gcd(0, 5), 5);
try expectEqual(gcd(5, 0), 5);
try expectEqual(gcd(8, 12), 4);
try expectEqual(gcd(12, 8), 4);
try expectEqual(gcd(33, 77), 11);
try expectEqual(gcd(77, 33), 11);
try expectEqual(gcd(49865, 69811), 9973);
try expectEqual(gcd(300_000, 2_300_000), 100_000);
try expectEqual(gcd(90000000_000_000_000_000_000, 2), 2);
try expectEqual(gcd(@as(u80, 90000000_000_000_000_000_000), 2), 2);
try expectEqual(gcd(300_000, @as(u32, 2_300_000)), 100_000);
}