LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
ele_mul.h
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23#ifndef __LMMP_ELE_MUL_H__
24#define __LMMP_ELE_MUL_H__
25
26#include "lmmp/lmmpn.h"
27#include "lmmp/numth.h"
28#include "impl/tmp_alloc.h"
29
30
31typedef struct {
34 sint left; // 左节点索引
35 sint right; // 右节点索引
36} huff_node;
37
38typedef struct {
42} huff_tree;
43
44
45/**
46 * @brief 初始化哈夫曼乘法树
47 * @param ht 哈夫曼乘法树指针
48 * @param cap 需要插入的元素的最大数量
49 * @warning 0<cap<2^30, ht!=NULL
50 */
51static inline void lmmp_huff_tree_init_(huff_tree* ht, sint cap) {
52 lmmp_param_assert(cap > 0);
53 lmmp_param_assert(cap < (1 << 30));
54 lmmp_param_assert(ht != NULL);
55 ht->root = ALLOC_TYPE(2 * cap - 1, huff_node);
56 ht->cap = cap;
57 ht->size = 0;
58}
59
60/**
61 * @brief 释放哈夫曼树
62 * @param ht 哈夫曼树指针
63 * @warning ht->size==0, ht!=NULL
64 */
65static inline void lmmp_huff_tree_free_(huff_tree* ht) {
66 lmmp_param_assert(ht != NULL);
67 lmmp_free(ht->root);
68 ht->cap = 0;
69 ht->size = 0;
70 ht->root = NULL;
71}
72
73/**
74 * @brief 入队哈夫曼树
75 * @param ht 哈夫曼树指针
76 * @param np 待入队的元素指针
77 * @param nn 元素的 limb 长度
78 * @warning ht!=NULL, ht->size<ht->cap, np!=NULL, nn>0
79 * @note 传入乘法元素必须为非空元素,可以和其他乘法元素指向完全相同
80 */
81static inline void lmmp_huff_tree_push_(huff_tree* ht, mp_srcptr np, mp_size_t nn) {
82 lmmp_param_assert(ht != NULL);
83 lmmp_param_assert(ht->size < ht->cap);
84 lmmp_param_assert(np != NULL);
85 lmmp_param_assert(nn > 0);
86 ht->root[ht->size].np = np;
87 ht->root[ht->size].nn = nn;
88 ht->root[ht->size].left = -1;
89 ht->root[ht->size].right = -1;
90 ht->size++;
91}
92
93/**
94 * @brief 构建哈夫曼乘法树
95 * @param ht 哈夫曼乘法树指针
96 * @warning ht!=NULL
97 * @return 构建后的根节点索引
98 */
100
101/**
102 * @brief 将哈夫曼树中所有元素相乘
103 * @param ht 哈夫曼乘法树指针
104 * @param ridx 哈夫曼乘法树根节点索引
105 * @param dst 结果指针(缓冲区长度为根节点的nn值)
106 * @param tp 临时指针(缓冲区长度为根节点的nn值)
107 * @warning pq!=NULL, dst!=NULL, tp!=NULL, sep(dst,tp)
108 * @return 结果指针的 limb 长度
109 */
111
112/**
113 * @brief 计算limbs数组的累乘积
114 * @param dst 结果指针(长度为 n 个 limb)
115 * @param limbs 数组指针
116 * @param n limbs数组长度
117 * @param tp 临时指针(长度为 n 个 limb)
118 * @warning dst!=NULL, limbs!=NULL, n>0, tp!=NULL
119 * @return 结果指针的 limb 长度
120 * @note 建议将limbs数组的元素累计至较大,可以减少空间占用和乘法次数
121 */
123
124typedef struct fac_t {
125 uint f; // factor
126 uint j; // exp
128
129typedef fac_t* fac_ptr;
130
131/**
132 * @brief 计算因子的累乘,并将结果放入dst中
133 * @param dst 结果数组
134 * @param rn 结果数组的长度
135 * @param fac 因子数组(将会被递归覆盖)
136 * @param nfactors 因子数组的长度
137 * @warning 因子必须要单调递增,可以接受重复因子(但不推荐这样做),因子的贡献必须要大于0。
138 * 已假定进入朴素乘法时,因子数组元素都小于等于0xffff,同时假定了,因子数组为小因子大指数形式,
139 * 可以存在大的因子有略大的指数,但整体的趋势应是小因子大指数。
140 * 在组合数以及由阶乘和幂次构成的有理数中,暂未见不满足这些假设的例子。
141 * @return 结果数组的长度
142 */
144
145/**
146 * @brief 计算因子的累乘,并将结果放入dst中
147 * @param dst 结果数组
148 * @param rn 结果数组的长度
149 * @param fac 因子数组(将会被递归覆盖),且因子数组元素都不可超过ushort范围
150 * @param nfactors 因子数组的长度
151 * @warning 因子必须要单调递增,且因子数组元素都不可超过ushort范围,可以接受重复因子(但不推荐这样做),
152 * 已假定了,因子数组为小因子大指数形式,可以存在大的因子有略大的指数,但整体的趋势应是小因子大指数。
153 * 在组合数以及由阶乘和幂次构成的有理数中,暂未见不满足这些假设的例子。
154 * @return 结果数组的长度
155 */
157
158#endif // __LMMP_ELE_MUL_H__
mp_size_t lmmp_huff_tree_mul_(huff_tree *restrict ht, sint ridx, mp_ptr restrict dst, mp_ptr restrict tp)
sint lmmp_huff_tree_build_(huff_tree *restrict ht)
mp_size_t lmmp_elem_mul_ulong_(mp_ptr restrict dst, const ulongp restrict limbs, mp_size_t n, mp_ptr restrict tp)
huff_node * root
static void lmmp_huff_tree_push_(huff_tree *ht, mp_srcptr np, mp_size_t nn)
入队哈夫曼树
static void lmmp_huff_tree_free_(huff_tree *ht)
释放哈夫曼树
mp_size_t lmmp_factors_mul_ushort_(mp_ptr dst, mp_size_t rn, fac_ptr fac, ushort nfactors)
计算因子的累乘,并将结果放入dst中
mp_size_t nn
static void lmmp_huff_tree_init_(huff_tree *ht, sint cap)
初始化哈夫曼乘法树
mp_srcptr np
fac_t * fac_ptr
mp_size_t lmmp_factors_mul_(mp_ptr dst, mp_size_t rn, fac_ptr fac, uint nfactors)
计算因子的累乘,并将结果放入dst中
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define tp
#define n
uint64_t * ulongp
定义 numth.h:48
uint32_t uint
定义 numth.h:38
uint16_t ushort
定义 numth.h:36
int32_t sint
定义 numth.h:40
#define ALLOC_TYPE(n, type)