52 out[1] = (
s == 0) ? 0 : (x >> (64 -
s));
55 out[1] = x << (
s - 64);
60 u64 seed = 0x6d2b79f5ull;
61 for (
int i = 0; i < 500; ++i) {
62 u64 a = xorshift64(&seed) | 1;
63 u64 b = xorshift64(&seed) | 1;
74 u64 seed = 0x3c6ef372fe94f82bull;
75 for (
size_t un = 1; un <= 40; ++un) {
76 for (
int iter = 0; iter < 20; ++iter) {
77 mp_ptr u = alloc_limbs(un);
78 random_limbs(u, un, &seed);
79 u64 v = xorshift64(&seed) | 1;
91 u64 seed = 0x9e3779b97f4a7c15ull;
92 mp_ptr u = alloc_limbs(2), v = alloc_limbs(2), dst = alloc_limbs(2), gr = alloc_limbs(2);
94 for (
int iter = 0; iter < 200; ++iter) {
95 random_limbs(u, 2, &seed);
96 random_limbs(v, 2, &seed);
104 for (
int iter = 0; iter < 100; ++iter) {
106 mp_ptr ub = alloc_limbs(un);
107 random_limbs(ub, un, &seed);
108 random_limbs(v, 2, &seed);
124 u64 seed = 0x51ce1b7ea4df7c21ull;
125 mp_ptr u = alloc_limbs(2), v = alloc_limbs(2), d = alloc_limbs(2), e = alloc_limbs(2);
126 for (
int a = 0; a <= 64; ++a) {
127 for (
int b = 0; b <= 64; b += 4) {
128 u64 x = (xorshift64(&seed) & (((
u64)1 << 63) - 1)) | 1;
129 u64 y = (xorshift64(&seed) & (((
u64)1 << 63) - 1)) | 1;
134 int m = a < b ? a : b;
143 {0, 1, 0, 3, 2, 0, 1},
144 {0, 9, 0, 6, 2, 0, 3},
145 {0, 2, 0, 6, 2, 0, 2},
146 {0, 1, 0, 1ull << 63, 2, 0, 1},
147 {1, 0, 3, 0, 1, 1, 0},
148 {12, 0, 18, 0, 1, 6, 0},
149 {0, 1, 5, 0, 1, 1, 0},
150 {7, 9, 7, 9, 2, 7, 9},
151 {10, 2, 0, 1, 1, 2, 0},
152 {0, 1, 0, 1, 2, 0, 1},
154 for (
size_t t_index = 0; t_index <
ARRAY_SIZE(fixed); ++t_index) {
155 const struct gcd_case
t = fixed[t_index];
156 u64 pu[2] = {
t.u0,
t.u1}, pv[2] = {
t.v0,
t.v1};
165 u64 seed = 0x2b44ae9d4d6c8f13ull;
166 for (
int iter = 0; iter < 20; ++iter) {
167 mp_ptr v = alloc_limbs(2);
168 random_limbs(v, 2, &seed);
169 u64 k = 3 + (xorshift64(&seed) & 0xf);
170 mp_ptr up = alloc_limbs(4);
174 mp_ptr d = alloc_limbs(2);
181 mp_ptr z = alloc_limbs(5);
191 const mp_size_t n_values[] = {2, 3, 5, 8, 16, 53, 64, 120, 200, 321};
192 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
221 TEST_RUN(
"numth/gcd", gcd_22_and_gcd_2);
222 TEST_RUN(
"numth/gcd", gcd_22_shapes);
223 TEST_RUN(
"numth/gcd", gcd_2_multiple_and_gcd_1_zero);
#define lmmp_zero(dst, n)
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
mp_size_t lmmp_gcd_lehmer_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(Lehmer算法)
mp_size_t lmmp_gcd_2_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp)
计算两个无符号整数的最大公约数
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
mp_size_t lmmp_gcd_hgcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
mp_limb_t lmmp_gcd_1_(mp_srcptr up, mp_size_t un, mp_limb_t v)
计算两个无符号整数的最大公约数
mp_size_t lmmp_gcd_22_(mp_ptr dst, mp_srcptr up, mp_srcptr vp)
计算两个无符号整数的最大公约数
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEST_CHECK_MSG(cond, msg)
#define TEST_CASE(category, name)
#define TEST_CHECK_EQ(a, b)
#define TEST_RUN(category, name)
static u64 gcd_u64(u64 a, u64 b)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void shifted_pair(u64 x, int s, mp_ptr out)