LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
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
31
typedef
struct
{
32
mp_srcptr
np
;
33
mp_size_t
nn
;
34
sint
left
;
// 左节点索引
35
sint
right
;
// 右节点索引
36
}
huff_node
;
37
38
typedef
struct
{
39
huff_node
*
root
;
40
sint
cap
;
41
sint
size
;
42
}
huff_tree
;
43
44
45
/**
46
* @brief 初始化哈夫曼乘法树
47
* @param ht 哈夫曼乘法树指针
48
* @param cap 需要插入的元素的最大数量
49
* @warning 0<cap<2^30, ht!=NULL
50
*/
51
static
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
*/
65
static
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
*/
81
static
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
*/
99
sint
lmmp_huff_tree_build_
(
huff_tree
* ht);
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
*/
110
mp_size_t
lmmp_huff_tree_mul_
(
huff_tree
* ht,
sint
ridx,
mp_ptr
dst,
mp_ptr
tp
);
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
*/
122
mp_size_t
lmmp_elem_mul_ulong_
(
mp_ptr
dst,
const
ulongp
limbs,
mp_size_t
n
,
mp_ptr
tp
);
123
124
typedef
struct
fac_t
{
125
uint
f
;
// factor
126
uint
j
;
// exp
127
}
fac_t
;
128
129
typedef
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
*/
143
mp_size_t
lmmp_factors_mul_
(
mp_ptr
dst,
mp_size_t
rn,
fac_ptr
fac,
uint
nfactors);
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
*/
156
mp_size_t
lmmp_factors_mul_ushort_
(
mp_ptr
dst,
mp_size_t
rn,
fac_ptr
fac,
ushort
nfactors);
157
158
#endif
// __LMMP_ELE_MUL_H__
lmmp_huff_tree_mul_
mp_size_t lmmp_huff_tree_mul_(huff_tree *restrict ht, sint ridx, mp_ptr restrict dst, mp_ptr restrict tp)
定义
ele_mul.c:153
lmmp_huff_tree_build_
sint lmmp_huff_tree_build_(huff_tree *restrict ht)
定义
ele_mul.c:114
lmmp_elem_mul_ulong_
mp_size_t lmmp_elem_mul_ulong_(mp_ptr restrict dst, const ulongp restrict limbs, mp_size_t n, mp_ptr restrict tp)
定义
ele_mul.c:172
huff_tree::root
huff_node * root
定义
ele_mul.h:39
huff_tree::cap
sint cap
定义
ele_mul.h:40
lmmp_huff_tree_push_
static void lmmp_huff_tree_push_(huff_tree *ht, mp_srcptr np, mp_size_t nn)
入队哈夫曼树
定义
ele_mul.h:81
lmmp_huff_tree_free_
static void lmmp_huff_tree_free_(huff_tree *ht)
释放哈夫曼树
定义
ele_mul.h:65
lmmp_factors_mul_ushort_
mp_size_t lmmp_factors_mul_ushort_(mp_ptr dst, mp_size_t rn, fac_ptr fac, ushort nfactors)
计算因子的累乘,并将结果放入dst中
huff_node::nn
mp_size_t nn
定义
ele_mul.h:33
lmmp_huff_tree_init_
static void lmmp_huff_tree_init_(huff_tree *ht, sint cap)
初始化哈夫曼乘法树
定义
ele_mul.h:51
huff_node::np
mp_srcptr np
定义
ele_mul.h:32
fac_ptr
fac_t * fac_ptr
定义
ele_mul.h:129
huff_node::right
sint right
定义
ele_mul.h:35
huff_tree::size
sint size
定义
ele_mul.h:41
fac_t::f
uint f
定义
ele_mul.h:125
fac_t::j
uint j
定义
ele_mul.h:126
huff_node::left
sint left
定义
ele_mul.h:34
lmmp_factors_mul_
mp_size_t lmmp_factors_mul_(mp_ptr dst, mp_size_t rn, fac_ptr fac, uint nfactors)
计算因子的累乘,并将结果放入dst中
huff_tree
定义
ele_mul.h:38
fac_t
定义
ele_mul.h:124
huff_node
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
ele_mul.h:31
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
lmmp_free
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
定义
memory.c:437
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
lmmpn.h
tp
#define tp
n
#define n
numth.h
ulongp
uint64_t * ulongp
定义
numth.h:48
uint
uint32_t uint
定义
numth.h:38
ushort
uint16_t ushort
定义
numth.h:36
sint
int32_t sint
定义
numth.h:40
tmp_alloc.h
ALLOC_TYPE
#define ALLOC_TYPE(n, type)
定义
tmp_alloc.h:199
src
lmmp
numth
ele_mul.h
生成于
, 为 LMMP使用
1.18.0