gcd_basecase.c 文件参考

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

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

浏览源代码.

宏定义
#define	an   un
#define	bn   vn

函数
mp_size_t	lmmp_gcd_basecase_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
	计算两个无符号整数的最大公约数（不建议使用此算法，更高版本可能被彻底弃用）

宏定义说明

an

#define an   un

bn

#define bn   vn

函数说明

lmmp_gcd_basecase_()

mp_size_t lmmp_gcd_basecase_	(	mp_ptr	dst,
		mp_srcptr	up,
		mp_size_t	un,
		mp_srcptr	vp,
		mp_size_t	vn
	)

计算两个无符号整数的最大公约数（不建议使用此算法，更高版本可能被彻底弃用）

参数

dst	结果指针（长度至少为 min(un,vn)）
up	第一个无符号整数指针
un	第一个无符号整数的 limb 长度
vp	第二个无符号整数指针
vn	第二个无符号整数的 limb 长度

警告

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

注解

朴素的辗转相除法，与Lehmer算法具有相似的渐进时间复杂度，但Lehmer算法绝大多数场合更加优秀

返回

dst 的实际 limb 长度

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

                                                                                                 {
    lmmp_param_assert(un > 0 && vn > 0);
    if (un < vn) {
        LMMP_SWAP(up, vp, mp_srcptr);
        LMMP_SWAP(un, vn, mp_size_t);
    } else if (un == vn) {
        int cmp = lmmp_cmp_(up, vp, un);
        if (cmp < 0) {
            LMMP_SWAP(up, vp, mp_srcptr);
        } else if (cmp == 0) {
            lmmp_copy(dst, up, un);
            return un;
        }
    }
    TEMP_DECL;
#define an un
#define bn vn
    mp_ptr a = TALLOC_TYPE(an, mp_limb_t);
    mp_ptr b = TALLOC_TYPE(bn, mp_limb_t);
    lmmp_copy(a, up, an);
    lmmp_copy(b, vp, bn);
    while (bn > 0 || (bn == 1 && b[0] == 0)) {
        // dst = a % b;
        lmmp_div_(NULL, dst, a, an, b, bn);
        lmmp_copy(a, b, bn);
        an = bn;
        while (dst[bn - 1] == 0 && bn > 0) {
            --bn;
        }
        lmmp_copy(b, dst, bn);
    }
    lmmp_copy(dst, a, an);
    TEMP_FREE;
    return an;
#undef an
#undef bn
}

引用了 an, bn, lmmp_cmp_(), lmmp_copy, lmmp_div_(), lmmp_param_assert, LMMP_SWAP, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

函数调用图: