gcd_2.c 文件参考

#include "../../../include/lammp/impl/longlong.h"
#include "../../../include/lammp/lmmpn.h"
#include "../../../include/lammp/numth.h"

gcd_2.c 的引用(Include)关系图:

浏览源代码.

函数
mp_size_t	lmmp_gcd_22_ (mp_ptr dst, mp_srcptr up, mp_srcptr vp)
	计算两个无符号整数的最大公约数
mp_size_t	lmmp_gcd_2_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp)
	计算两个无符号整数的最大公约数

函数说明

lmmp_gcd_22_()

mp_size_t lmmp_gcd_22_	(	mp_ptr	dst,
		mp_srcptr	up,
		mp_srcptr	vp
	)

计算两个无符号整数的最大公约数

参数

up	第一个无符号整数指针，长度为 2
vp	第二个无符号整数指针，长度为 2
dst	结果指针（长度为 2，两个 limb 都会进行写入，即使最高位可能为0）

警告

up!=NULL, vp!=NULL, [up,2]!=0, [vp,2]!=0, dst!=NULL, eqsep(dst,[up|vp])

注解

我们不要求 up 和 vp 的高位不为 0，但要求两个数均不可以高低位全为 0

返回

dst 的实际 limb 长度

在文件 gcd_2.c 第 11 行定义.

                                                               {
    lmmp_param_assert(dst != NULL);
    lmmp_param_assert(up != NULL);
    lmmp_param_assert(vp != NULL);
    lmmp_param_assert(!(up[1] == 0 && up[0] == 0));
    lmmp_param_assert(!(vp[1] == 0 && vp[0] == 0));
    mp_limb_t u[2] = { up[0], up[1] };
    mp_limb_t v[2] = { vp[0], vp[1] };
    int k, cnt;
 
    if (u[1] == 0 && v[1] == 0) {
        dst[0] = lmmp_gcd_11_(u[0], v[0]);
        dst[1] = 0;
        return 1;
    } else if (u[1] == 0) {
        cnt = lmmp_tailing_zeros_(u[0] | v[0]);
        u[0] = u[0] >> lmmp_tailing_zeros_(u[0]);
        goto gcd_1_2;
    } else if (v[1] == 0) {
        cnt = lmmp_tailing_zeros_(u[0] | v[0]);
        v[0] = v[0] >> lmmp_tailing_zeros_(v[0]);
        goto gcd_2_1;
    }
 
    if (u[0] == 0 && v[0] == 0) {
        dst[0] = lmmp_gcd_11_(u[1], v[1]); 
        dst[1] = 0;
        return 1;
    } else if (u[0] == 0) {
        u[0] = u[1] >> lmmp_tailing_zeros_(u[1]);
        cnt = lmmp_tailing_zeros_(v[0]);
        goto gcd_1_2;
    } else if (v[0] == 0) {
        v[0] = v[1] >> lmmp_tailing_zeros_(v[1]);
        cnt = lmmp_tailing_zeros_(u[0]);
        goto gcd_2_1;
    }
    cnt = lmmp_tailing_zeros_(u[0] | v[0]);
    k = lmmp_tailing_zeros_(u[0]);
 
    if (k > 0)
        _u128lshr(u, u, k);
    k = lmmp_tailing_zeros_(v[0]);
    if (k > 0)
        _u128lshr(v, v, k);
    while (!(u[0] == v[0] && u[1] == v[1])) {
        if (u[1] == 0 && v[1] != 0) goto gcd_1_2;
        if (v[1] == 0 && u[1] != 0) goto gcd_2_1;
        if (u[1] == 0 && v[1] == 0) goto gcd_1_1;
 
        if (_u128cmp(u, v)) {
            _u128sub(v, v, u);
            if (v[0] == 0) {
                v[0] = v[1] >> lmmp_tailing_zeros_(v[1]);
                goto gcd_2_1;
            } else if (v[1] == 0) {
                v[0] = v[0] >> lmmp_tailing_zeros_(v[0]);
                goto gcd_2_1;
            }
            k = lmmp_tailing_zeros_(v[0]);
            // k > 0
            _u128lshr(v, v, k);
        } else {
            _u128sub(u, u, v);
            if (u[0] == 0) {
                u[0] = u[1] >> lmmp_tailing_zeros_(u[1]);
                goto gcd_1_2;
            } else if (u[1] == 0) {
                u[0] = u[0] >> lmmp_tailing_zeros_(u[0]);
                goto gcd_1_2;
            }
            k = lmmp_tailing_zeros_(u[0]);
            // k > 0
            _u128lshr(u, u, k);
        }
    }
    dst[0] = u[0];
    dst[1] = u[1];
    if (cnt > 0)
        _u128lshl(dst, dst, cnt);
    return 2;
 
    gcd_1_2:   // [u,1]  ,  [v,2]
        k = lmmp_tailing_zeros_(v[0]);
        if (k > 0)
            _u128lshr(v, v, k);
        while (v[1] != 0) {
            _u128sub64(v, v, u[0]);
            if (v[1] == 0) 
                goto gcd_1_1;
            if (v[0] == 0) {
                v[0] = v[1] >> lmmp_tailing_zeros_(v[1]);
                goto gcd_1_1;
            }
            k = lmmp_tailing_zeros_(v[0]);
            // k > 0
            _u128lshr(v, v, k);
        }
        goto gcd_1_1;
 
    gcd_2_1:   // [u,2]  ,  [v,1]
        k = lmmp_tailing_zeros_(u[0]);
        if (k > 0)
            _u128lshr(u, u, k);
        while (u[1] != 0) {
            _u128sub64(u, u, v[0]);
            if (u[1] == 0)
                goto gcd_1_1;
            if (u[0] == 0) {
                u[0] = u[1] >> lmmp_tailing_zeros_(u[1]);
                goto gcd_1_1;
            }
            k = lmmp_tailing_zeros_(u[0]);
            // k > 0
            _u128lshr(u, u, k);
        }
        goto gcd_1_1;
 
    gcd_1_1:   // [u,1]  ,  [v,1]
        while (u[0] != v[0]) {
            if (u[0] > v[0]) {
                u[0] -= v[0];
                u[0] >>= lmmp_tailing_zeros_(u[0]);
            } else {
                v[0] -= u[0];
                v[0] >>= lmmp_tailing_zeros_(v[0]);
            }
        }
        dst[0] = u[0];
        dst[1] = 0;
        if (cnt > 0)
            _u128lshl(dst, dst, cnt);
        return dst[1] == 0 ?  1  :  2;
}

引用了 _u128cmp, _u128lshl, _u128lshr, _u128sub, _u128sub64, k, lmmp_gcd_11_(), lmmp_param_assert , 以及 lmmp_tailing_zeros_().

被这些函数引用 lmmp_gcd_2_().

函数调用图:

这是这个函数的调用关系图:

lmmp_gcd_2_()

mp_size_t lmmp_gcd_2_	(	mp_ptr	dst,
		mp_srcptr	up,
		mp_size_t	un,
		mp_srcptr	vp
	)

计算两个无符号整数的最大公约数

参数

up	第一个无符号整数指针
un	第一个无符号整数的 limb 长度
vp	第二个无符号整数指针，长度为 2
dst	结果指针（长度至少为 2，两个 limb 都会进行写入，即使最高位可能为0）

警告

up!=NULL, un>2, vp!=NULL, vp[1]!=0, dst!=NULL, eqsep(dst,[up|vp])

返回

dst 的实际 limb 长度

在文件 gcd_2.c 第 146 行定义.

                                                                            {
    lmmp_param_assert(dst != NULL);
    lmmp_param_assert(up != NULL);
    lmmp_param_assert(vp != NULL);
    lmmp_param_assert(un > 2);
    lmmp_param_assert(vp[1] != 0);
    mp_limb_t u[2] = {vp[0], vp[1]};
    lmmp_mod_2_(up, un, u);
    if (u[1] == 0 && u[0] == 0) {
        dst[0] = vp[0];
        dst[1] = vp[1];
        return 2;
    } else {
        return lmmp_gcd_22_(dst, vp, u);
    }
}

引用了 lmmp_gcd_22_(), lmmp_mod_2_() , 以及 lmmp_param_assert.

函数调用图: