LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
ele_mul.c
浏览该文件的文档.
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#include "numth/ele_mul.h"
24#include "mparam.h"
25
26#define INSERTION_SORT_THRESHOLD 16
27
28static inline void swap_huff_node(huff_node* a, huff_node* b) {
29 mp_srcptr tp = a->np;
30 mp_size_t tn = a->nn;
31 a->np = b->np;
32 a->nn = b->nn;
33 b->np = tp;
34 b->nn = tn;
35}
36
37/**
38 * @brief 在闭区间 [low, high] 上进行插入排序
39 */
40static void insertion_sort(huff_node arr[], sint low, sint high) {
41 for (sint i = low + 1; i <= high; ++i) {
42 mp_srcptr np = arr[i].np;
43 mp_size_t nn = arr[i].nn;
44 sint j = i - 1;
45 while (j >= low && arr[j].nn > nn) {
46 arr[j + 1].np = arr[j].np;
47 arr[j + 1].nn = arr[j].nn;
48 --j;
49 }
50 arr[j + 1].np = np;
51 arr[j + 1].nn = nn;
52 }
53}
54
55/**
56 * @brief 返回 arr[a]、arr[b]、arr[c] 三个索引中对应值的中位数的索引
57 */
58static inline sint median_of_three(const huff_node arr[], sint a, sint b, sint c) {
59 mp_size_t va = arr[a].nn, vb = arr[b].nn, vc = arr[c].nn;
60 if (va < vb) {
61 if (vb < vc)
62 return b;
63 else if (va < vc)
64 return c;
65 else
66 return a;
67 } else {
68 if (va < vc)
69 return a;
70 else if (vb < vc)
71 return c;
72 else
73 return b;
74 }
75}
76
77/**
78 * @brief 递归的三路快速排序,对闭区间 [low, high] 排序
79 */
80static void quicksort_rec(huff_node arr[], sint low, sint high) {
81 if (high - low + 1 <= INSERTION_SORT_THRESHOLD) {
82 insertion_sort(arr, low, high);
83 return;
84 }
85
86 sint mid = low + (high - low) / 2;
87 sint pivot_index = median_of_three(arr, low, mid, high);
88 if (pivot_index != low) {
89 swap_huff_node(&arr[low], &arr[pivot_index]);
90 }
91 mp_size_t pivot = arr[low].nn;
92
93 sint lt = low; // 小于区域的右边界(开)
94 sint gt = high; // 大于区域的左边界(开)
95 sint i = low + 1;
96
97 while (i <= gt) {
98 if (arr[i].nn < pivot) {
99 swap_huff_node(&arr[lt], &arr[i]);
100 ++lt;
101 ++i;
102 } else if (arr[i].nn > pivot) {
103 swap_huff_node(&arr[i], &arr[gt]);
104 --gt;
105 } else {
106 ++i;
107 }
108 }
109
110 quicksort_rec(arr, low, lt - 1);
111 quicksort_rec(arr, gt + 1, high);
112}
113
115 lmmp_param_assert(ht != NULL);
116 lmmp_param_assert(ht->root != NULL && ht->size > 0);
117 sint n = ht->size;
118 huff_node* arr = ht->root;
119
120 if (n == 1) {
121 return 0;
122 }
123
124 quicksort_rec(arr, 0, n - 1);
125
126 sint i = 0, j = n, k = n;
127
128 while (k < (2 * n - 1)) {
129 sint idx1, idx2;
130
131 if (i < n && (j >= k || arr[i].nn <= arr[j].nn)) {
132 idx1 = i++;
133 } else {
134 idx1 = j++;
135 }
136
137 if (i < n && (j >= k || arr[i].nn <= arr[j].nn)) {
138 idx2 = i++;
139 } else {
140 idx2 = j++;
141 }
142 // 非叶子节点的np不会被访问,此赋值不会影响结果
143 //arr[k].np = NULL;
144 arr[k].nn = arr[idx1].nn + arr[idx2].nn;
145 arr[k].left = idx1;
146 arr[k].right = idx2;
147 k++;
148 }
149
150 return 2 * n - 2;
151}
152
154 if (ht->root[ridx].left == -1) {
155 lmmp_copy(dst, ht->root[ridx].np, ht->root[ridx].nn);
156 return ht->root[ridx].nn;
157 } else {
158 sint idx = ht->root[ridx].left;
159 mp_size_t halfn = ht->root[idx].nn; // 左子树的limb缓冲区长度
160 mp_size_t n1 = lmmp_huff_tree_mul_(ht, ht->root[ridx].left, tp, dst);
161 mp_size_t n2 = lmmp_huff_tree_mul_(ht, ht->root[ridx].right, tp + halfn, dst + halfn);
162 if (n1 > n2)
163 lmmp_mul_(dst, tp, n1, tp + halfn, n2);
164 else
165 lmmp_mul_(dst, tp + halfn, n2, tp, n1);
166 n1 += n2;
167 n1 -= dst[n1 - 1] == 0 ? 1 : 0;
168 return n1;
169 }
170}
171
174 lmmp_param_assert(n > 0);
175 dst[0] = limbs[0];
176 mp_size_t rn = 1;
177 for (mp_size_t i = 1; i < n; i++) {
178 dst[rn] = lmmp_mul_1_(dst, dst, rn, limbs[i]);
179 rn++;
180 rn -= dst[rn - 1] == 0 ? 1 : 0;
181 }
182 return rn;
183 }
184 mp_size_t halfn = n / 2;
185 mp_size_t n1 = lmmp_elem_mul_ulong_(tp, limbs, halfn, dst);
186 mp_size_t n2 = lmmp_elem_mul_ulong_(tp + halfn, limbs + halfn, n - halfn, dst + halfn);
187 if (n1 > n2)
188 lmmp_mul_(dst, tp, n1, tp + halfn, n2);
189 else
190 lmmp_mul_(dst, tp + halfn, n2, tp, n1);
191 n = n1 + n2;
192 n -= dst[n - 1] == 0 ? 1 : 0;
193 return n;
194}
#define k
#define INSERTION_SORT_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
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)
static void insertion_sort(huff_node arr[], sint low, sint high)
在闭区间 [low, high] 上进行插入排序
static void quicksort_rec(huff_node arr[], sint low, sint high)
递归的三路快速排序,对闭区间 [low, high] 排序
static sint median_of_three(const huff_node arr[], sint a, sint b, sint c)
返回 arr[a]、arr[b]、arr[c] 三个索引中对应值的中位数的索引
mp_size_t lmmp_elem_mul_ulong_(mp_ptr restrict dst, const ulongp restrict limbs, mp_size_t n, mp_ptr restrict tp)
static void swap_huff_node(huff_node *a, huff_node *b)
mp_size_t nn
mp_srcptr np
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define lmmp_param_assert(x)
定义 lmmp.h:509
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义 mul_1.c:27
#define tp
#define n
#define ELEM_MUL_BASECASE_THRESHOLD
uint64_t * ulongp
定义 numth.h:48
int32_t sint
定义 numth.h:40
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)