LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom32.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 "impl/mul_hard.h"
24#include "mparam.h"
25#include "impl/tmp_alloc.h"
26#include "lmmp/lmmpn.h"
27
28
29#define lmmp_mul_n_(dst, numa, numb, n) \
30 if ((n) < MUL_TOOM22_THRESHOLD) \
31 lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
32 else if ((n) < MUL_TOOM33_THRESHOLD) \
33 lmmp_mul_toom22_((dst), (numa), (n), (numb), (n)); \
34 else \
35 lmmp_mul_toom33_((dst), (numa), (n), (numb), (n))
36
37/*
38Evaluate in: -1, 0, +1, +inf
39
40<-s-><--n--><--n-->
41|a2-|---a1-|---a0-|
42 |-b1-|---b0-|
43 <-t--><--n-->
44
45v0 = a0 * b0 # A(0)*B(0)
46v1 = (a0+a1+a2)*(b0+b1) # A(1)*B(1) ah <= 2 bh <= 1
47vm1 = (a0-a1+a2)*(b0-b1) # A(-1)*B(-1) |ah| <= 1 bh = 0
48vinf= a2 * b1 # A(inf)*B(inf)
49*/
50
52 lmmp_param_assert(nb >= 12);
53 lmmp_param_assert(3 * nb > na);
54 lmmp_param_assert(na > nb);
56 mp_size_t n = 1 + (2 * na >= 3 * nb ? (na - 1) / 3 : (nb - 1) >> 1), s = na - 2 * n, t = nb - n;
57 int vm1_neg;
60 lmmp_param_assert(s + t >= n + 2);
61 mp_limb_t cy, hi;
63
64#define a0 numa
65#define a1 (numa + n)
66#define a2 (numa + 2 * n)
67#define b0 numb
68#define b1 (numb + n)
69 // nb>=12, so that s+t>=n+2
70#define bm1 (dst) //[dst,n]
71#define bp1 (dst + n) //[dst+n,n+1]
72#define ap1 (dst + 2 * n + 1) //[dst+2*n+1,n+1]
73#define am1 (dst + 3 * n + 2) //[dst+3*n+2,n]:hi
74#define v1 (tp) //[tp,2*n+1]
75#define vm1 (tp + 2 * n + 1) //[tp+2*n+1,2*n+1]
76#define r0 (dst)
77#define r1 (dst + n)
78#define r2 (dst + 2 * n)
79#define r3 (dst + 3 * n)
80
81 // ap1=a0+a1+a3, am1=a0-a1+a3
82 ap1[n] = lmmp_add_(ap1, a0, n, a2, s);
83 if (ap1[n] == 0 && lmmp_cmp_(ap1, a1, n) < 0) {
84 ap1[n] = lmmp_add_n_sub_n_(ap1, am1, a1, ap1, n) >> 1;
85 hi = 0;
86 vm1_neg = 1;
87 } else {
88 cy = lmmp_add_n_sub_n_(ap1, am1, ap1, a1, n);
89 hi = ap1[n] - (cy & 1);
90 ap1[n] += (cy >> 1);
91 vm1_neg = 0;
92 }
93
94 // bp1=b0+b1, bm1=b0-b1
95 if (t == n) {
96 if (lmmp_cmp_(b0, b1, n) < 0) {
97 bp1[n] = lmmp_add_n_sub_n_(bp1, bm1, b1, b0, n) >> 1;
98 vm1_neg ^= 1;
99 } else {
100 bp1[n] = lmmp_add_n_sub_n_(bp1, bm1, b0, b1, n) >> 1;
101 }
102 } else {
103 if (lmmp_zero_q_(b0 + t, n - t) && lmmp_cmp_(b0, b1, t) < 0) {
104 cy = lmmp_add_n_sub_n_(bp1, bm1, b1, b0, t);
105 lmmp_zero(bm1 + t, n - t);
106 vm1_neg ^= 1;
107 } else {
108 cy = lmmp_add_n_sub_n_(bp1, bm1, b0, b1, t);
109 lmmp_sub_1_(bm1 + t, b0 + t, n - t, cy & 1);
110 }
111 bp1[n] = lmmp_add_1_(bp1 + t, b0 + t, n - t, cy >> 1);
112 }
113
114 // v1=ap1*bp1
115 lmmp_mul_n_(v1, ap1, bp1, n + 1);
116
117 // vm=am1*bm1
118 lmmp_mul_n_(vm1, am1, bm1, n);
119 if (hi)
120 hi = lmmp_add_n_(vm1 + n, vm1 + n, bm1, n);
121 vm1[2 * n] = hi;
122
123 // r0=a0*b0
124 // r3=a2*b1
125 lmmp_mul_n_(r0, a0, b0, n);
126 if (s > t)
127 lmmp_mul_(r3, a2, s, b1, t);
128 else
129 lmmp_mul_(r3, b1, t, a2, s);
130
131 // v1=(v1+vm1)/2, (=a0*b0+a2*b0+a1*b1)
132 // vm1=v1-vm1, (=a1*b0+a0*b1+a2*b1)
133 if (vm1_neg) {
134 lmmp_shr1sub_n_(v1, v1, vm1, 2 * n + 1);
135 lmmp_add_n_(vm1, v1, vm1, 2 * n + 1);
136 } else {
137 lmmp_shr1add_n_(v1, v1, vm1, 2 * n + 1);
138 lmmp_sub_n_(vm1, v1, vm1, 2 * n + 1);
139 }
140
141 // vm1-=r3, (=r1)
142 // v1-=r0, (=r2)
143 lmmp_sub_(vm1, vm1, 2 * n + 1, r3, s + t);
144 v1[2 * n] -= lmmp_sub_n_(v1, v1, r0, 2 * n);
145
146 // r=r0+vm1*B+v1*B^2+r3*B^4
147 cy = vm1[2 * n] + lmmp_add_(r1, vm1, 2 * n, r1, n);
148 lmmp_add_(r2, r2, n + s + t, v1, 2 * n + 1);
149 lmmp_inc_1(r3, cy);
151}
#define lmmp_mul_n_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
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]
mp_limb_t lmmp_shr1add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法后右移1位 [dst,n] = ([numa,n] + [numb,n]) >> 1
定义 shr.c:65
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
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]
void lmmp_mul_toom32_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-32乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
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]
mp_limb_t lmmp_add_n_sub_n_(mp_ptr dsta, mp_ptr dstb, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])
static mp_limb_t lmmp_sub_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
减单精度数静态内联函数 [dst,na]=[numa,na]-x
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
mp_limb_t lmmp_shr1sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
减法后右移1位 [dst,n] = ([numa,n] - [numb,n]) >> 1
定义 shr.c:87
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
#define b0
#define b1
#define a0
#define a1
#define r2
#define am1
#define ap1
#define bp1
#define vm1
#define r1
#define bm1
#define a2
#define v1
#define r3
#define r0
#define t
#define numb
#define tp
#define s
#define n
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define SALLOC_TYPE(n, type)
#define TEMP_S_DECL
#define TEMP_S_FREE