mul.c 文件参考

#include "../../include/lammp/lmmpn.h"
#include "../../include/lammp/impl/mparam.h"

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

浏览源代码.

函数
void	lmmp_mul_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_srcptr restrict numb, mp_size_t nb)
void	lmmp_mul_n_ (mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
	等长大数乘法操作 [dst,2*n] = [numa,n] * [numb,n]

函数说明

lmmp_mul_()

void lmmp_mul_	(	mp_ptr restrict	dst,
		mp_srcptr restrict	numa,
		mp_size_t	na,
		mp_srcptr restrict	numb,
		mp_size_t	nb
	)

在文件 mul.c 第 30 行定义.

                                                                                                                  {
    lmmp_param_assert(na >= nb);
    lmmp_param_assert(nb > 0);
    if (na == nb) {
        if (numa == numb)
            lmmp_sqr_(dst, numa, na);
        else
            lmmp_mul_n_(dst, numa, numb, na);
    } else if ((nb < MUL_TOOM22_THRESHOLD || nb < MUL_TOOMX2_THRESHOLD) && !(4 * na < 5 * nb)) {
        if (na <= PART_SIZE || nb <= 2)
            lmmp_mul_basecase_(dst, numa, na, numb, nb);
        else {
            mp_limb_t tp[MUL_TOOMX2_THRESHOLD];
            lmmp_mul_basecase_(dst, numa, PART_SIZE, numb, nb);
            dst += PART_SIZE;
            numa += PART_SIZE;
            na -= PART_SIZE;
            lmmp_copy(tp, dst, nb);
            while (na > PART_SIZE) {
                lmmp_mul_basecase_(dst, numa, PART_SIZE, numb, nb);
                if (lmmp_add_n_(dst, dst, tp, nb))
                    lmmp_inc(dst + nb);
                dst += PART_SIZE;
                numa += PART_SIZE;
                na -= PART_SIZE;
                lmmp_copy(tp, dst, nb);
            }
            if (na >= nb)
                lmmp_mul_basecase_(dst, numa, na, numb, nb);
            else
                lmmp_mul_basecase_(dst, numb, nb, numa, na);
            if (lmmp_add_n_(dst, dst, tp, nb))
                lmmp_inc(dst + nb);
        }
    } else if (((na + nb) >> 1) < MUL_TOOM44_THRESHOLD || 2 * nb < MUL_TOOM44_THRESHOLD) {
        if (na < 3 * nb) {
            if (4 * na < 5 * nb) {
                if (nb < MUL_TOOM33_THRESHOLD)
                    lmmp_mul_toom22_(dst, numa, na, numb, nb);
                else
                    lmmp_mul_toom33_(dst, numa, na, numb, nb);
            } else if (5 * na < 9 * nb)
                lmmp_mul_toom32_(dst, numa, na, numb, nb);
            else
                lmmp_mul_toom42_(dst, numa, na, numb, nb);
        } else 
            lmmp_mul_toom42_unbalance_(dst, numa, na, numb, nb);
    } else if (((na + nb) >> 1) < MUL_FFT_THRESHOLD || 2 * nb < MUL_FFT_THRESHOLD) {
        if (na < 5 * nb) {
            if (4 * na < 5 * nb) 
                lmmp_mul_toom44_(dst, numa, na, numb, nb);
            else if (3 * na < 5 * nb)
                lmmp_mul_toom43_(dst, numa, na, numb, nb);
            else if (9 * na < 20 * nb)
                lmmp_mul_toom53_(dst, numa, na, numb, nb);
            else if (na < 3 * nb)
                lmmp_mul_toom52_(dst, numa, na, numb, nb);
            else 
                lmmp_mul_toom62_(dst, numa, na, numb, nb);
        } else 
            lmmp_mul_toom62_unbalance_(dst, numa, na, numb, nb);
    } else {
        if (na < 8 * nb)
            lmmp_mul_fft_(dst, numa, na, numb, nb);
        else 
            lmmp_mul_fft_unbalance_(dst, numa, na, numb, nb);
    }
}

引用了 lmmp_add_n_(), lmmp_copy, lmmp_inc, lmmp_mul_basecase_(), lmmp_mul_fft_(), lmmp_mul_fft_unbalance_(), lmmp_mul_n_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_unbalance_(), lmmp_mul_toom43_(), lmmp_mul_toom44_(), lmmp_mul_toom52_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_unbalance_(), lmmp_param_assert, lmmp_sqr_(), MUL_FFT_THRESHOLD, MUL_TOOM22_THRESHOLD, MUL_TOOM33_THRESHOLD, MUL_TOOM44_THRESHOLD, MUL_TOOMX2_THRESHOLD, PART_SIZE , 以及 tp.

函数调用图:

lmmp_mul_n_()

void lmmp_mul_n_	(	mp_ptr	dst,
		mp_srcptr	numa,
		mp_srcptr	numb,
		mp_size_t	n
	)

等长大数乘法操作 [dst,2*n] = [numa,n] * [numb,n]

警告

n>0, sep(dst,[numa|numb]) 特殊情况: n==1时dst<=numa+1是允许的 n==2时dst<=numa是允许的

参数

dst	乘积结果输出指针（需要 2*n 的 limb 长度）
numa	第一个乘数指针
numb	第二个乘数指针
n	limb长度

在文件 mul.c 第 99 行定义.

                                                                          {
    if (n < MUL_TOOM22_THRESHOLD)
        lmmp_mul_basecase_(dst, numa, n, numb, n);
    else if (n < MUL_TOOM33_THRESHOLD)
        lmmp_mul_toom22_(dst, numa, n, numb, n);
    else if (n < MUL_TOOM44_THRESHOLD)
        lmmp_mul_toom33_(dst, numa, n, numb, n);
    else if (n < MUL_FFT_THRESHOLD)
        lmmp_mul_toom44_(dst, numa, n, numb, n);
    else
        lmmp_mul_fft_(dst, numa, n, numb, n);
}

引用了 lmmp_mul_basecase_(), lmmp_mul_fft_(), lmmp_mul_toom22_(), lmmp_mul_toom33_(), lmmp_mul_toom44_(), MUL_FFT_THRESHOLD, MUL_TOOM22_THRESHOLD, MUL_TOOM33_THRESHOLD , 以及 MUL_TOOM44_THRESHOLD.

被这些函数引用 binvert_mulhi_(), lmmp_div_mulinv_(), lmmp_invappr_newton_(), lmmp_invsqrt_newton_(), lmmp_mul_(), lmmp_mul_fermat_recurse_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom43_(), lmmp_mul_toom44_(), lmmp_mul_toom52_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_() , 以及 lmmp_mullo_dc_().

函数调用图:

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