multinomial.c 文件参考

#include "../../../include/lammp/impl/ele_mul.h"
#include "../../../include/lammp/impl/prime_table.h"
#include "../../../include/lammp/impl/longlong.h"
#include "../../../include/lammp/impl/mparam.h"

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

浏览源代码.

宏定义
#define	MULTINOMIAL_INT_LIMIT   (0xffffffff)
#define	MULTINOMIAL_SHORT_LIMIT   (0xffff)

函数
static uint	count_factors (fac_ptr fac, uint nfactors, uint n, const uintp r, uint m, uint p)
static uint	factor_size_int (mp_size_t rn, uint n)
static uint	factor_size_short (mp_size_t rn)
mp_size_t	lmmp_multinomial_ (mp_ptr restrict dst, mp_size_t rn, uint n, const uintp restrict r, uint m)
mp_size_t	lmmp_multinomial_size_ (const uintp r, uint m, ulong *restrict n)
static mp_size_t	lmmp_odd_multinomial_uint_ (mp_ptr restrict dst, mp_size_t rn, uint n, const uintp restrict r, uint m)
static mp_size_t	lmmp_odd_multinomial_ushort_ (mp_ptr restrict dst, mp_size_t rn, uint n, const uintp restrict r, uint m)

宏定义说明

MULTINOMIAL_INT_LIMIT

#define MULTINOMIAL_INT_LIMIT   (0xffffffff)

在文件 multinomial.c 第 121 行定义.

MULTINOMIAL_SHORT_LIMIT

#define MULTINOMIAL_SHORT_LIMIT   (0xffff)

在文件 multinomial.c 第 120 行定义.

函数说明

count_factors()

static uint count_factors ( fac_ptr  fac, uint  nfactors, uint  n, const uintp  r, uint  m, uint  p  )

inlinestatic

在文件 multinomial.c 第 28 行定义.

                                                                                                    {
    uint pn = n;
    uint e = 0;
    ulong inv = MP_ULONG_MAX / p + 1;
    while (pn > 0) {
        _udiv32by32_q_preinv(pn, pn, inv);
        e += pn;
    }
    for (uint i = 0; i < m; ++i) {
        uint pn = r[i];
        while (pn > 0) {
            _udiv32by32_q_preinv(pn, pn, inv);
            e -= pn;
        }
    }
    if (e > 0) {
        fac[nfactors].f = p;
        fac[nfactors++].j = e;
    }
    return nfactors;
}

引用了 _udiv32by32_q_preinv, fac_t::f, fac_t::j , 以及 MP_ULONG_MAX.

被这些函数引用 lmmp_odd_multinomial_uint_() , 以及 lmmp_odd_multinomial_ushort_().

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

factor_size_int()

static uint factor_size_int ( mp_size_t  rn, uint  n  )

inlinestatic

在文件 multinomial.c 第 50 行定义.

                                                         {
    /*
     使用类似组合数的思路来估计缓冲区大小。
    */
    uint approx1 = rn * 8;
    uint approx2 = lmmp_prime_size_(n);
    return approx1 < approx2 ? approx1 : approx2;
}

引用了 lmmp_prime_size_().

被这些函数引用 lmmp_odd_multinomial_uint_().

函数调用图:

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

factor_size_short()

static uint factor_size_short ( mp_size_t  rn )

inlinestatic

在文件 multinomial.c 第 59 行定义.

                                                   {
    return rn * 10;
}

被这些函数引用 lmmp_odd_multinomial_ushort_().

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

lmmp_multinomial_()

mp_size_t lmmp_multinomial_	(	mp_ptr restrict	dst,
		mp_size_t	rn,
		uint	n,
		const uintp restrict	r,
		uint	m
	)

在文件 multinomial.c 第 123 行定义.

                                                                                                       {
    mp_size_t shl = n - lmmp_limb_popcnt_(n);
    for (uint j = 0; j < m; ++j) {
        shl += lmmp_limb_popcnt_(r[j]);
        shl -= r[j];
    }
    mp_size_t shw = shl / LIMB_BITS;
    shl %= LIMB_BITS;
    lmmp_zero(dst, shw);
    if (n <= MULTINOMIAL_SHORT_LIMIT) {
        rn = lmmp_odd_multinomial_ushort_(dst + shw, rn - shw, n, r, m);
    } else {
        rn = lmmp_odd_multinomial_uint_(dst + shw, rn - shw, n, r, m);
    }
 
    if (shl > 0) {
        dst[shw + rn] = lmmp_shl_(dst + shw, dst + shw, rn, shl);
        rn += shw + 1;
        rn -= dst[rn - 1] == 0 ? 1 : 0;
    } else {
        rn += shw;
    }
    return rn;
}

引用了 LIMB_BITS, lmmp_limb_popcnt_(), lmmp_odd_multinomial_uint_(), lmmp_odd_multinomial_ushort_(), lmmp_shl_(), lmmp_zero , 以及 MULTINOMIAL_SHORT_LIMIT.

函数调用图:

lmmp_multinomial_size_()

mp_size_t lmmp_multinomial_size_	(	const uintp	r,
		uint	m,
		ulong *restrict	n
	)

在文件 multinomial.c 第 12 行定义.

                                                                           {
    *n = 0;
    uint i = 0;
    for (; i < m; ++i) *n += r[i];
 
    double logr = lgamma(*n + 1.0);
    
    for (i = 0; i < m; ++i) 
        logr -= lgamma(r[i] + 1.0);
 
    logr /= LOG2_;
 
    mp_size_t rn = ceil(logr / LIMB_BITS) + 2;
    return rn;
}

引用了 LIMB_BITS , 以及 LOG2_.

lmmp_odd_multinomial_uint_()

static mp_size_t lmmp_odd_multinomial_uint_ ( mp_ptr restrict  dst, mp_size_t  rn, uint  n, const uintp restrict  r, uint  m  )

static

在文件 multinomial.c 第 97 行定义.

                                                                                                                       {
    lmmp_prime_int_table_init_(n);
    TEMP_B_DECL;
    uint nfactors = factor_size_int(rn, n);
    fac_ptr restrict fac = BALLOC_TYPE(nfactors, fac_t);
 
    nfactors = 0;
    prime_cache_t cache;
    lmmp_prime_cache_init_(&cache, n);
    while (cache.is_end == 0) {
        lmmp_prime_cache_next_(&cache);
        for (uint i = 0; i < cache.size; ++i) {
            nfactors = count_factors(fac, nfactors, n, r, m, cache.pp[i]);
        }
    }
    lmmp_prime_cache_free_(&cache);
 
    rn = lmmp_factors_mul_(dst, rn, fac, nfactors);
 
    TEMP_B_FREE;
    return rn;
}

引用了 BALLOC_TYPE, count_factors(), factor_size_int(), prime_cache_t::is_end, lmmp_factors_mul_(), lmmp_prime_cache_free_(), lmmp_prime_cache_init_(), lmmp_prime_cache_next_(), lmmp_prime_int_table_init_(), prime_cache_t::pp, prime_cache_t::size, TEMP_B_DECL , 以及 TEMP_B_FREE.

被这些函数引用 lmmp_multinomial_().

函数调用图:

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

lmmp_odd_multinomial_ushort_()

static mp_size_t lmmp_odd_multinomial_ushort_ ( mp_ptr restrict  dst, mp_size_t  rn, uint  n, const uintp restrict  r, uint  m  )

static

在文件 multinomial.c 第 63 行定义.

  {
    if (n < ODD_FACTORIAL_SIZE) {
        lmmp_odd_nPr_ushort_(dst, rn, n, n);
        mp_limb_t t = 0;
        for (uint i = 0; i < m; ++i) {
            lmmp_odd_nPr_ushort_(&t, 1, r[i], r[i]);
            dst[0] /= t;
        }
        return 1;
    } else {
        TEMP_DECL;
        uint primen = lmmp_prime_cnt16_(n);
        uint nfactors = factor_size_short(rn);
        nfactors = primen < nfactors ? primen : nfactors;
        fac_ptr restrict fac = TALLOC_TYPE(nfactors, fac_t);
        nfactors = 0;
        for (uint i = 1; i < primen; ++i) {
            uint p = prime_short_table[i];
            nfactors = count_factors(fac, nfactors, n, r, m, p);
        }
 
        rn = lmmp_factors_mul_(dst, rn, fac, nfactors);
 
        TEMP_FREE;
        return rn;
    }
}

引用了 count_factors(), factor_size_short(), lmmp_factors_mul_(), lmmp_odd_nPr_ushort_(), lmmp_prime_cnt16_(), ODD_FACTORIAL_SIZE, prime_short_table, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 lmmp_multinomial_().

函数调用图:

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