LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mat22_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 "lmmp/lmmpn.h"
24#include "mparam.h"
25#include "numth/mat22_mul.h"
26#include "impl/internal.h"
27
28/**
29 * @brief 带符号加法
30 * @param r 结果指针(长度为 maxabs(xs,ys)+1)
31 * @param x 第一个加数指针,长度为abs(xs)
32 * @param xs 绝对值表示第一个加数指针长度,符号表示此数正负
33 * @param y 第二个加数指针,长度为abs(ys)
34 * @param ys 绝对值表示第二个加数指针长度,符号表示此数正负
35 * @warning r!=NULL, x!=NULL, y!=NULL, eqsep(r,[xs|ys])
36 * @return 绝对值表示结果的实际长度,符号表示符号
37 */
39 int xneg = xs < 0;
40 int yneg = ys < 0;
41 mp_size_t xa = xs < 0 ? (mp_size_t)(-xs) : (mp_size_t)xs;
42 mp_size_t ya = ys < 0 ? (mp_size_t)(-ys) : (mp_size_t)ys;
43 if (xa == 0) {
44 if (r != y) {
45 lmmp_copy(r, y, ya);
46 }
47 return ys;
48 }
49 if (ya == 0) {
50 if (r != x) {
51 lmmp_copy(r, x, xa);
52 }
53 return xs;
54 }
55 if (xneg == yneg) {
56 /* 同号:较长春在前相加,进位落盘 */
57 mp_srcptr lp = xa >= ya ? x : y;
58 mp_srcptr sp = xa >= ya ? y : x;
59 mp_size_t m = xa >= ya ? xa : ya;
60 mp_limb_t c = lmmp_add_(r, lp, m, sp, xa >= ya ? ya : xa);
61 if (c != 0) {
62 r[m] = c;
63 ++m;
64 }
65 return xneg ? -(mp_ssize_t)m : (mp_ssize_t)m;
66 }
67 int xbig = xa > ya || (xa == ya && lmmp_cmp_(x, y, xa) >= 0);
68 mp_srcptr big = xbig ? x : y;
69 mp_srcptr sml = xbig ? y : x;
70 mp_size_t ba = xbig ? xa : ya;
71 mp_size_t sa = xbig ? ya : xa;
72 lmmp_sub_(r, big, ba, sml, sa);
73
74 while (ba > 0 && r[ba - 1] == 0) {
75 --ba;
76 }
77 int rneg = xbig ? xneg : yneg;
78 return rneg ? -(mp_ssize_t)ba : (mp_ssize_t)ba;
79}
80
81/**
82 * @brief 带符号乘法
83 * @param r 结果指针(长度为 abs(xs)+abs(ys))
84 * @param x 第一个乘数指针,长度为abs(xs)
85 * @param xs 绝对值表示第一个乘数指针长度,符号表示此数正负
86 * @param y 第二个乘数指针,长度为abs(ys)
87 * @param ys 绝对值表示第二个乘数指针长度,符号表示此数正负
88 * @warning r!=NULL, x!=NULL, y!=NULL, sep(r,[xs|ys])
89 * @return 绝对值表示结果的实际长度,符号表示符号
90 */
92 int neg = (xs < 0) != (ys < 0);
93 mp_size_t xa = xs < 0 ? (mp_size_t)(-xs) : (mp_size_t)xs;
94 mp_size_t ya = ys < 0 ? (mp_size_t)(-ys) : (mp_size_t)ys;
95 if (xa == 0 || ya == 0) {
96 return 0;
97 }
98 if (xa >= ya) {
99 lmmp_mul_(r, x, xa, y, ya);
100 } else {
101 lmmp_mul_(r, y, ya, x, xa);
102 }
103 mp_size_t l = xa + ya;
104 l -= (r[l - 1] == 0);
105 return neg ? -(mp_ssize_t)l : (mp_ssize_t)l;
106}
107
108/**
109 * @brief 无符号加法
110 * @param r 结果指针(长度为 max(xs,ys)+1)
111 * @param x 第一个加数指针,长度为xs
112 * @param xs 第一个加数指针长度
113 * @param y 第二个加数指针,长度为ys
114 * @param ys 第二个加数指针长度
115 * @warning r!=NULL, x!=NULL, y!=NULL, eqsep(r,[xs|ys])
116 * @return 结果的实际长度
117 * @note 零操作数(长度 0)时和为另一操作数,拷贝返回其长度
118 */
120 if (xs == 0) {
121 if (r != y) {
122 lmmp_copy(r, y, ys);
123 }
124 return ys;
125 }
126 if (ys == 0) {
127 if (r != x) {
128 lmmp_copy(r, x, xs);
129 }
130 return xs;
131 }
132 if (xs > ys) {
133 mp_limb_t c = lmmp_add_(r, x, xs, y, ys);
134 r[xs] = c;
135 return xs + ((c > 0) ? 1 : 0);
136 } else {
137 mp_limb_t c = lmmp_add_(r, y, ys, x, xs);
138 r[ys] = c;
139 return ys + ((c > 0) ? 1 : 0);
140 }
141}
142
143/**
144 * @brief 无符号乘法
145 * @param r 结果指针(长度为 abs(xs)+abs(ys))
146 * @param x 第一个乘数指针,长度为abs(xs)
147 * @param xs 第一个乘数指针长度
148 * @param y 第二个乘数指针,长度为abs(ys)
149 * @param ys 第二个乘数指针长度
150 * @warning r!=NULL, x!=NULL, y!=NULL, sep(r,[xs|ys])
151 * @return 结果的实际长度
152 */
154 if (xs == 0 || ys == 0) {
155 return 0;
156 }
157 if (xs >= ys) {
158 lmmp_mul_(r, x, xs, y, ys);
159 } else {
160 lmmp_mul_(r, y, ys, x, xs);
161 }
162 mp_size_t l = xs + ys;
163 l -= (r[l - 1] == 0);
164 return l;
165}
166
167/**
168 * @brief 无符号平方
169 * @param r 结果指针(长度为 2*xs)
170 * @param x 源指针,长度为xs
171 * @param xs 源指针长度
172 * @warning r!=NULL, x!=NULL, sep(r,x)
173 * @return 结果的实际长度
174 * @note xs==0 时结果为零(lmmp_sqr_ 对零长度不安全,须在此拦截)
175 */
177 if (xs == 0) {
178 return 0;
179 }
180 lmmp_sqr_(r, x, xs);
181 mp_size_t l = 2 * xs;
182 l -= (r[l - 1] == 0);
183 return l;
184}
185
186/**
187 * @brief 元素长度最大值
188 * @param a 输入矩阵
189 * @warning a!=NULL
190 * @return 返回 a 矩阵的元素长度最大值
191 */
193 mp_size_t mx = 0;
194 if (a->n[0][0] > mx)
195 mx = a->n[0][0];
196 if (a->n[0][1] > mx)
197 mx = a->n[0][1];
198 if (a->n[1][0] > mx)
199 mx = a->n[1][0];
200 if (a->n[1][1] > mx)
201 mx = a->n[1][1];
202 return mx;
203}
204
206 return l < 0 ? (mp_size_t)(-l) : (mp_size_t)l;
207}
208
209/**
210 * @brief 计算 D <- A*B(2x2 非负矩阵朴素乘法)
211 * @param dst 结果矩阵,各个元素结果写入 dst->p 中的数组,对应实际长度被写入到 dst->n 中
212 * @param a 左矩阵(元素长度为 a->n[i][j],可与 dst 别名,即支持 D <- D*B)
213 * @param b 右矩阵(元素长度为 b->n[i][j],不可与 dst 别名)
214 * @param tp 临时空间(4*(mx(a)+mx(b)) 个limb)
215 * @warning dst!=NULL, a!=NULL, b!=NULL, tp!=NULL, sep(dst,b), eqsep(dst,a),
216 * dst 各元素缓冲容量至少为 mx(a)+mx(b)+1
217 */
218static void mat22_mul_basecase_(lmmp_mat22_t* dst, const lmmp_mat22_t* a, const lmmp_mat22_t* b, mp_ptr tp) {
220 for (int i = 0; i < 2; ++i) {
221 mp_ptr pA = tp, pB = tp + pn, pC = tp + 2 * pn, pD = tp + 3 * pn;
222 mp_size_t lA = mat22_mul_(pA, a->p[i][0], a->n[i][0], b->p[0][0], b->n[0][0]);
223 mp_size_t lB = mat22_mul_(pB, a->p[i][1], a->n[i][1], b->p[1][0], b->n[1][0]);
224 mp_size_t lC = mat22_mul_(pC, a->p[i][0], a->n[i][0], b->p[0][1], b->n[0][1]);
225 mp_size_t lD = mat22_mul_(pD, a->p[i][1], a->n[i][1], b->p[1][1], b->n[1][1]);
226 /* a 行元素(可能即 dst 行缓冲)的读取已完毕,结果直写 */
227 dst->n[i][0] = mat22_add_(dst->p[i][0], pA, lA, pB, lB);
228 dst->n[i][1] = mat22_add_(dst->p[i][1], pC, lC, pD, lD);
229 }
230}
231
232/*
233 Winograd-Strassen 乘法
234
235 A = /a00 a01\,B = /b00 b01\。组合量与乘积安置在 9 个变宽槽位:每个组合量
236 \a10 a11/ \b10 b11/
237
238 s1 = a11+a01 t1 = b11+b01 p1 = s1*t1 p2 = s2*t2 p3 = s3*t3
239 s2 = a11-a10 t2 = b11-b10 p4 = a00*b00 p5 = a01*b10
240 s3 = s2+a01 t3 = t2+b01 p6 = s4*b01 p7 = a10*t4
241 s4 = s3-a00 t4 = t3-b00
242 U1 = p3+p5
243 U2 = p1-U1
244 U3 = U1-p2
245
246 C00 = p4+p5
247 C01 = U3-p6
248 C10 = U2-p7
249 C11 = p2+U2
250
251 C = A*B = /c00 c01\
252 \c10 c11/
253*/
254
255/**
256 * @brief 计算 D <- A*B(2x2 非负矩阵 Winograd-Strassen 乘法,7 次大数乘)
257 * @param dst 结果矩阵,各个元素结果写入 dst->p 中的数组,对应实际长度被写入到 dst->n 中
258 * @param a 左矩阵(元素长度为 a->n[i][j],可与 dst 别名,即支持 D <- D*B)
259 * @param b 右矩阵(元素长度为 b->n[i][j],不可与 dst 别名)
260 * @param tp 临时空间(8*(mx(a)+mx(b))+16 个limb)
261 * @warning dst!=NULL, a!=NULL, b!=NULL, tp!=NULL, sep(dst,b), eqsep(dst,a),
262 * dst 各元素缓冲容量至少为 mx(a)+mx(b)+4
263 * @note 各段长度界限与槽位分配(mxa = mx(a),mxb = mx(b)):
264 *
265 * [s1,mxa+1] 无符号加法,长度至多+1
266 * [s2,mxa] 带符号减法,长度不会增加
267 * [s3,mxa+1] 带符号加法,长度至多+1
268 * [s4,mxa+2] 带符号加法,长度至多+1
269 * t1~t4 同构(mxa 换为 mxb)
270 *
271 * [p1,mxa+mxb+2] = [s1]*[t1](乘积长度为因子长度之和)
272 * [p2,mxa+mxb] = [s2]*[t2]
273 * [p3,mxa+mxb+2] = [s3]*[t3]
274 * [p4,mxa+mxb] = a00*b00(原始元素非负,无符号乘法)
275 * [p5,mxa+mxb] = a01*b10(同上)
276 * [p6,mxa+mxb+2] = [s4]*b01
277 * [p7,mxa+mxb+2] = a10*[t4]
278 *
279 * [U1,mxa+mxb+3] = p3+p5(带符号加法,长度至多 max+1)
280 * [U2,mxa+mxb+4] = p1-U1
281 * [U3,mxa+mxb+4] = U1-p2
282 *
283 * 槽位(按驻留内容的最大写入范围计宽,顺序分配):
284 * s1槽(后驻 p2) mxa+mxb
285 * s2槽(后驻 p3,U1,U3)mxa+mxb+4
286 * s3槽(后驻 p6) mxa+mxb+2
287 * s4槽(仅组合量) mxa+2
288 * t1槽(后驻 p4) mxa+mxb
289 * t2槽(后驻 p5) mxa+mxb
290 * t3槽(后驻 p7) mxa+mxb+2
291 * t4槽(仅组合量) mxb+2
292 * 空槽(驻 p1,U2) mxa+mxb+4
293 * 合计 8*(mxa+mxb)+16 limbs。最终结果直写 dst:C00 = p4+p5 为
294 * 无符号加法;其余三个经带符号加法,瞬态写入范围至多
295 * mx(a)+mx(b)+4(U3/U2 的归一化长度由恒等式 U3=C01+p6、
296 * U2=C10+p7 与结果界限定于 mxa+mxb+3,加法至多再+1)
297 */
298static void mat22_mul_strassen_(lmmp_mat22_t* dst, const lmmp_mat22_t* a, const lmmp_mat22_t* b, mp_ptr tp) {
299 mp_size_t mxa = mat22_maxlen_(a);
300 mp_size_t mxb = mat22_maxlen_(b);
301 mp_size_t off = 0;
302 mp_ptr s1 = tp + off;
303 off += mxa + mxb; /* s1 槽,后驻 p2 */
304 mp_ptr s2 = tp + off;
305 off += mxa + mxb + 4; /* s2 槽,后驻 p3、U1、U3 */
306 mp_ptr s3 = tp + off;
307 off += mxa + mxb + 2; /* s3 槽,后驻 p6 */
308 mp_ptr s4 = tp + off;
309 off += mxa + 2; /* s4 槽,仅组合量 */
310 mp_ptr t1 = tp + off;
311 off += mxa + mxb; /* t1 槽,后驻 p4 */
312 mp_ptr t2 = tp + off;
313 off += mxa + mxb; /* t2 槽,后驻 p5 */
314 mp_ptr t3 = tp + off;
315 off += mxa + mxb + 2; /* t3 槽,后驻 p7 */
316 mp_ptr t4 = tp + off;
317 off += mxb + 2; /* t4 槽,仅组合量 */
318 mp_ptr spare = tp + off; /* 空槽,驻 p1、U2,宽 mxa+mxb+4 */
319 mp_ssize_t ns1, ns2, ns3, ns4, nt1, nt2, nt3, nt4;
320
321 ns1 = mat22_add_(s1, a->p[1][1], a->n[1][1], a->p[0][1], a->n[0][1]);
322 ns2 = mat22_addsg_(s2, a->p[1][1], (mp_ssize_t)a->n[1][1], a->p[1][0], -(mp_ssize_t)a->n[1][0]);
323 ns3 = mat22_addsg_(s3, s2, ns2, a->p[0][1], (mp_ssize_t)a->n[0][1]);
324 ns4 = mat22_addsg_(s4, s3, ns3, a->p[0][0], -(mp_ssize_t)a->n[0][0]);
325
326 nt1 = mat22_add_(t1, b->p[1][1], b->n[1][1], b->p[0][1], b->n[0][1]);
327 nt2 = mat22_addsg_(t2, b->p[1][1], (mp_ssize_t)b->n[1][1], b->p[1][0], -(mp_ssize_t)b->n[1][0]);
328 nt3 = mat22_addsg_(t3, t2, nt2, b->p[0][1], (mp_ssize_t)b->n[0][1]);
329 nt4 = mat22_addsg_(t4, t3, nt3, b->p[0][0], -(mp_ssize_t)b->n[0][0]);
330
331 /* 乘积槽位:p1 用空槽;p2/p3/p6 回填已消耗的 s 槽;p4/p5/p7 占 t 槽。
332 p1/p4/p5 的因子均非负(s1/t1 无符号和,a0j/bj0 原始元素),用无符号乘法 */
333 mp_ptr p1 = spare, p2 = s1, p3 = s2, p4 = t1, p5 = t2, p6 = s3, p7 = t3;
334 mp_ssize_t np1 = mat22_mul_(p1, s1, ns1, t1, nt1);
335 mp_ssize_t np2 = mat22_mulsg_(p2, s2, ns2, t2, nt2); /* s2、t2 已消耗 */
336 mp_ssize_t np3 = mat22_mulsg_(p3, s3, ns3, t3, nt3); /* s3、t3 已消耗 */
337 mp_ssize_t np4 = mat22_mul_(p4, a->p[0][0], a->n[0][0], b->p[0][0], b->n[0][0]);
338 mp_ssize_t np5 = mat22_mul_(p5, a->p[0][1], a->n[0][1], b->p[1][0], b->n[1][0]);
339 mp_ssize_t np6 = mat22_mulsg_(p6, s4, ns4, b->p[0][1], (mp_ssize_t)b->n[0][1]); /* s4 已消耗 */
340 mp_ssize_t np7 = mat22_mulsg_(p7, a->p[1][0], (mp_ssize_t)a->n[1][0], t4, nt4); /* t4 已消耗 */
341
342 /* U 链安置在已消耗的槽位内 */
343 mp_ssize_t nu1 = mat22_addsg_(p3, p3, np3, p5, np5); /* U1 = p3+p5,存 p3 槽 */
344 mp_ssize_t nu2 = mat22_addsg_(p1, p1, np1, p3, -nu1); /* U2 = p1-U1,存 p1 槽 */
345 mp_ssize_t nu3 = mat22_addsg_(p3, p3, nu1, p2, -np2); /* U3 = U1-p2,存 p3 槽 */
346
347 /* C00 = p4+p5 两非负积之和,无符号加法直写;其余带符号 */
348 dst->n[0][0] = mat22_add_(dst->p[0][0], p4, np4, p5, np5);
349 dst->n[0][1] = mat22_abslen_(mat22_addsg_(dst->p[0][1], p3, nu3, p6, -np6)); /* C01 = U3-p6 */
350 dst->n[1][0] = mat22_abslen_(mat22_addsg_(dst->p[1][0], p1, nu2, p7, -np7)); /* C10 = U2-p7 */
351 dst->n[1][1] = mat22_abslen_(mat22_addsg_(dst->p[1][1], p2, np2, p1, nu2)); /* C11 = p2+U2 */
352}
353
354/**
355 * @brief 计算 D <- A*A(2x2 非负矩阵朴素平方,5 次大数乘)
356 * @param dst 结果矩阵,各个元素结果写入 dst->p 中的数组,对应实际长度被写入到 dst->n 中
357 * @param a 源矩阵(元素长度为 a->n[i][j],可与 dst 别名)
358 * @param tp 临时空间(5*mx(a)+2 个limb)
359 * @warning dst!=NULL, a!=NULL, tp!=NULL, eqsep(dst,a),
360 * dst 各元素缓冲容量至少为 2*mx(a)+2
361 * @note 各段长度界限与槽位分配(mxa = mx(a),全部无符号):
362 *
363 * [s,mxa+1] = a00+a11,无符号加法,长度至多+1
364 * [cross,2mxa] = a01*a10
365 * [C01,2mxa+1] = a01*s,即 [mxa]*[mxa+1]
366 * [C10,2mxa+1] = a10*s,同上
367 * [对角元,2mxa+1] = a00^2/a11^2 [2mxa] 加 cross,长度至多+1
368 *
369 * 槽位(顺序分配):cross 槽 2mxa、s 槽 mxa+1、tmp 中转槽
370 * 2mxa+1(容纳最大乘积的写入范围)→ 合计 5mxa+2 limbs。
371 * 别名安全性:s 与 cross 先行完成对 a 全部元素的复用读取;
372 * C01/C10 的因子 a01/a10 各仅参与自身结果与 cross,末读后经
373 * tmp 拷入 dst;对角元的直写发生在 a00/a11 末读之后
374 */
376 mp_size_t mxa = mat22_maxlen_(a);
377 mp_size_t off = 0;
378 mp_ptr cross = tp + off;
379 off += 2 * mxa; /* cross 槽 */
380 mp_ptr s = tp + off;
381 off += mxa + 1; /* s 槽 */
382 mp_ptr tmp = tp + off; /* tmp 中转槽,宽 2mxa+1 */
383
384 mp_size_t ls = mat22_add_(s, a->p[0][0], a->n[0][0], a->p[1][1], a->n[1][1]);
385 mp_size_t lcross = mat22_mul_(cross, a->p[0][1], a->n[0][1], a->p[1][0], a->n[1][0]);
386
387 mp_size_t l01 = mat22_mul_(tmp, a->p[0][1], a->n[0][1], s, ls);
388 dst->n[0][1] = l01;
389 lmmp_copy(dst->p[0][1], tmp, l01);
390 mp_size_t l10 = mat22_mul_(tmp, a->p[1][0], a->n[1][0], s, ls);
391 dst->n[1][0] = l10;
392 lmmp_copy(dst->p[1][0], tmp, l10);
393
394 mp_size_t l00 = mat22_sqr_(tmp, a->p[0][0], a->n[0][0]);
395 dst->n[0][0] = mat22_add_(dst->p[0][0], tmp, l00, cross, lcross);
396 mp_size_t l11 = mat22_sqr_(tmp, a->p[1][1], a->n[1][1]);
397 dst->n[1][1] = mat22_add_(dst->p[1][1], tmp, l11, cross, lcross);
398}
399
400/**
401 * @brief 计算 D <- A*A(2x2 非负矩阵 Winograd-Strassen 平方,7 次大数乘中 4 次为平方)
402 * @param dst 结果矩阵,各个元素结果写入 dst->p 中的数组,对应实际长度被写入到 dst->n 中
403 * @param a 源矩阵(元素长度为 a->n[i][j],可与 dst 别名)
404 * @param tp 临时空间(15*mx(a)+14 个limb)
405 * @warning dst!=NULL, a!=NULL, tp!=NULL, eqsep(dst,a),
406 * dst 各元素缓冲容量至少为 2*mx(a)+4
407 * @note 各段长度界限与槽位分配(mxa = mx(a),组合量对称 t_i = s_i):
408 *
409 * [s1,mxa+1] 无符号加法,长度至多+1
410 * [s2,mxa] 带符号减法,长度不会增加
411 * [s3,mxa+1] 带符号加法,长度至多+1
412 * [s4,mxa+2] 带符号加法,长度至多+1
413 *
414 * [p1,2mxa+2] = s1^2(s1 非负,无符号平方,平方对符号不敏感,
415 * 带符号组合量取绝对长度后同样走无符号平方)
416 * [p2,2mxa] = s2^2
417 * [p3,2mxa+2] = s3^2
418 * [p4,2mxa] = a00^2(原始元素非负,无符号平方)
419 * [p5,2mxa] = a01*a10(无符号乘法)
420 * [p6,2mxa+2] = [s4]*a01(带符号乘法)
421 * [p7,2mxa+2] = a10*[s4](带符号乘法)
422 *
423 * [U1,2mxa+3] = p3+p5(带符号加法,长度至多 max+1)
424 * [U2,2mxa+4] = p1-U1
425 * [U3,2mxa+4] = U1-p2
426 *
427 * 槽位(按驻留内容的最大写入范围计宽,顺序分配):
428 * s1槽(后驻 p2) 2mxa
429 * s2槽(后驻 p3,U1,U3)2mxa+4
430 * s3槽(后驻 p6) 2mxa+2
431 * s4槽(仅组合量) mxa+2
432 * 空槽(驻 p1,U2) 2mxa+4
433 * p4槽 2mxa
434 * p5槽 2mxa
435 * p7槽 2mxa+2
436 * 合计 15mxa+14 limbs。结果直写 dst:C00 = p4+p5 无符号加法,
437 * 其余带符号,瞬态写入范围至多 2*mx(a)+4(同乘法的恒等式论证)
438 */
440 mp_size_t mxa = mat22_maxlen_(a);
441 mp_size_t off = 0;
442 mp_ptr s1 = tp + off;
443 off += 2 * mxa; /* s1 槽,后驻 p2 */
444 mp_ptr s2 = tp + off;
445 off += 2 * mxa + 4; /* s2 槽,后驻 p3、U1、U3 */
446 mp_ptr s3 = tp + off;
447 off += 2 * mxa + 2; /* s3 槽,后驻 p6 */
448 mp_ptr s4 = tp + off;
449 off += mxa + 2; /* s4 槽,仅组合量 */
450 mp_ptr spare = tp + off;
451 off += 2 * mxa + 4; /* 空槽,驻 p1、U2 */
452 mp_ptr p4 = tp + off;
453 off += 2 * mxa; /* p4 槽 */
454 mp_ptr p5 = tp + off;
455 off += 2 * mxa; /* p5 槽 */
456 mp_ptr p7 = tp + off; /* p7 槽,宽 2mxa+2 */
457 mp_ssize_t ns1, ns2, ns3, ns4;
458
459 ns1 = mat22_add_(s1, a->p[1][1], a->n[1][1], a->p[0][1], a->n[0][1]);
460 ns2 = mat22_addsg_(s2, a->p[1][1], (mp_ssize_t)a->n[1][1], a->p[1][0], -(mp_ssize_t)a->n[1][0]);
461 ns3 = mat22_addsg_(s3, s2, ns2, a->p[0][1], (mp_ssize_t)a->n[0][1]);
462 ns4 = mat22_addsg_(s4, s3, ns3, a->p[0][0], -(mp_ssize_t)a->n[0][0]);
463
464 /* 平方对符号不敏感:带符号组合量取绝对长度走无符号平方 */
465 mp_ptr p1 = spare, p2 = s1, p3 = s2, p6 = s3;
466 mp_ssize_t np1 = (mp_ssize_t)mat22_sqr_(p1, s1, ns1);
467 mp_ssize_t np2 = (mp_ssize_t)mat22_sqr_(p2, s2, mat22_abslen_(ns2)); /* s2 已消耗 */
468 mp_ssize_t np3 = (mp_ssize_t)mat22_sqr_(p3, s3, mat22_abslen_(ns3)); /* s3 已消耗 */
469 mp_ssize_t np4 = (mp_ssize_t)mat22_sqr_(p4, a->p[0][0], a->n[0][0]);
470 mp_ssize_t np5 = (mp_ssize_t)mat22_mul_(p5, a->p[0][1], a->n[0][1], a->p[1][0], a->n[1][0]);
471 mp_ssize_t np6 = mat22_mulsg_(p6, s4, ns4, a->p[0][1], (mp_ssize_t)a->n[0][1]); /* s4 尚需用于 p7 */
472 mp_ssize_t np7 = mat22_mulsg_(p7, a->p[1][0], (mp_ssize_t)a->n[1][0], s4, ns4); /* 对称 t4=s4,此后 s4 已消耗 */
473
474 mp_ssize_t nu1 = mat22_addsg_(p3, p3, np3, p5, np5); /* U1 = p3+p5 */
475 mp_ssize_t nu2 = mat22_addsg_(p1, p1, np1, p3, -nu1); /* U2 = p1-U1 */
476 mp_ssize_t nu3 = mat22_addsg_(p3, p3, nu1, p2, -np2); /* U3 = U1-p2 */
477 /* C00 = p4+p5 两非负积之和,无符号加法直写;其余带符号
478 (别名安全性同乘法:末次原元素读取在 np7) */
479 dst->n[0][0] = mat22_add_(dst->p[0][0], p4, np4, p5, np5);
480 dst->n[0][1] = mat22_abslen_(mat22_addsg_(dst->p[0][1], p3, nu3, p6, -np6)); /* C01 = U3-p6 */
481 dst->n[1][0] = mat22_abslen_(mat22_addsg_(dst->p[1][0], p1, nu2, p7, -np7)); /* C10 = U2-p7 */
482 dst->n[1][1] = mat22_abslen_(mat22_addsg_(dst->p[1][1], p2, np2, p1, nu2)); /* C11 = p2+U2 */
483}
484
485static int mat22_all_big_(const lmmp_mat22_t* x, mp_size_t th) {
486 for (int i = 0; i < 2; ++i) {
487 for (int j = 0; j < 2; ++j) {
488 if (x->n[i][j] < th) {
489 return 0;
490 }
491 }
492 }
493 return 1;
494}
495
497 lmmp_param_assert(dst != NULL && a != NULL && b != NULL && tp != NULL);
499 mat22_mul_strassen_(dst, a, b, tp);
500 } else {
501 mat22_mul_basecase_(dst, a, b, tp);
502 }
503}
504
506 lmmp_param_assert(dst != NULL && a != NULL && tp != NULL);
508 mat22_sqr_strassen_(dst, a, tp);
509 } else {
510 mat22_sqr_basecase_(dst, a, tp);
511 }
512}
513
514LMMP_INTERNAL_ENTRY(void, lmmp_internal_numth_mat22_sqr_basecase,
515 (lmmp_mat22_t* dst, const lmmp_mat22_t* a, mp_ptr tp),
516 mat22_sqr_basecase_(dst, a, tp);)
517
518LMMP_INTERNAL_ENTRY(void, lmmp_internal_numth_mat22_sqr_strassen,
519 (lmmp_mat22_t* dst, const lmmp_mat22_t* a, mp_ptr tp),
520 mat22_sqr_strassen_(dst, a, tp);)
#define lmmp_sqr_
#define LMMP_INTERNAL_ENTRY(type, name, parameters,...)
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
int64_t mp_ssize_t
定义 lmmp.h:95
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
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]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
void lmmp_mat22_sqr_(lmmp_mat22_t *dst, const lmmp_mat22_t *a, mp_ptr tp)
计算 D <- A*A(2x2 非负矩阵平方)
static int mat22_all_big_(const lmmp_mat22_t *x, mp_size_t th)
static mp_size_t mat22_maxlen_(const lmmp_mat22_t *a)
元素长度最大值
static mp_size_t mat22_abslen_(mp_ssize_t l)
static void mat22_mul_strassen_(lmmp_mat22_t *dst, const lmmp_mat22_t *a, const lmmp_mat22_t *b, mp_ptr tp)
计算 D <- A*B(2x2 非负矩阵 Winograd-Strassen 乘法,7 次大数乘)
static mp_ssize_t mat22_addsg_(mp_ptr r, mp_srcptr x, mp_ssize_t xs, mp_srcptr y, mp_ssize_t ys)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static mp_size_t mat22_sqr_(mp_ptr r, mp_srcptr x, mp_size_t xs)
无符号平方
static mp_size_t mat22_mul_(mp_ptr r, mp_srcptr x, mp_size_t xs, mp_srcptr y, mp_size_t ys)
无符号乘法
static mp_ssize_t mat22_mulsg_(mp_ptr r, mp_srcptr x, mp_ssize_t xs, mp_srcptr y, mp_ssize_t ys)
带符号乘法
static mp_size_t mat22_add_(mp_ptr r, mp_srcptr x, mp_size_t xs, mp_srcptr y, mp_size_t ys)
无符号加法
static void mat22_sqr_strassen_(lmmp_mat22_t *dst, const lmmp_mat22_t *a, mp_ptr tp)
计算 D <- A*A(2x2 非负矩阵 Winograd-Strassen 平方,7 次大数乘中 4 次为平方)
static void mat22_sqr_basecase_(lmmp_mat22_t *dst, const lmmp_mat22_t *a, mp_ptr tp)
计算 D <- A*A(2x2 非负矩阵朴素平方,5 次大数乘)
static void mat22_mul_basecase_(lmmp_mat22_t *dst, const lmmp_mat22_t *a, const lmmp_mat22_t *b, mp_ptr tp)
计算 D <- A*B(2x2 非负矩阵朴素乘法)
void lmmp_mat22_mul_(lmmp_mat22_t *dst, const lmmp_mat22_t *a, const lmmp_mat22_t *b, mp_ptr tp)
计算 D <- A*B(2x2 非负矩阵乘法)
mp_ptr p[2][2]
mp_size_t n[2][2]
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define tp
#define s
#define tmp
#define MAT22_SQR_STRASSEN_THRESHOLD
#define MAT22_MUL_STRASSEN_THRESHOLD