LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom32.c 文件参考
#include "impl/mul_hard.h"
#include "mparam.h"
#include "impl/tmp_alloc.h"
#include "lmmp/lmmpn.h"
mul_toom32.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define a0   numa
#define a1   (numa + n)
#define a2   (numa + 2 * n)
#define am1   (dst + 3 * n + 2)
#define ap1   (dst + 2 * n + 1)
#define b0   numb
#define b1   (numb + n)
#define bm1   (dst)
#define bp1   (dst + n)
#define lmmp_mul_n_(dst, numa, numb, n)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define r0   (dst)
#define r1   (dst + n)
#define r2   (dst + 2 * n)
#define r3   (dst + 3 * n)
#define v1   (tp)
#define vm1   (tp + 2 * n + 1)

函数

void lmmp_mul_toom32_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_srcptr restrict numb, mp_size_t nb)

宏定义说明

◆ a0

#define a0   numa

◆ a1

#define a1   (numa + n)

◆ a2

◆ am1

◆ ap1

◆ b0

#define b0   numb

◆ b1

#define b1   (numb + n)

◆ bm1

◆ bp1

◆ lmmp_mul_n_

#define lmmp_mul_n_ ( dst,
numa,
numb,
n )
值:
lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
else if ((n) < MUL_TOOM33_THRESHOLD) \
lmmp_mul_toom22_((dst), (numa), (n), (numb), (n)); \
else \
lmmp_mul_toom33_((dst), (numa), (n), (numb), (n))
#define MUL_TOOM22_THRESHOLD
#define MUL_TOOM33_THRESHOLD
#define numb
#define n

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 mul_toom32.c 第 29 行定义.

◆ r0

◆ r1

◆ r2

◆ r3

◆ v1

◆ vm1

函数说明

◆ lmmp_mul_toom32_()

void lmmp_mul_toom32_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_size_t na,
mp_srcptr restrict numb,
mp_size_t nb )

在文件 mul_toom32.c 第 51 行定义.

51 {
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_
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
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]
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 tp
#define s
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define SALLOC_TYPE(n, type)
#define TEMP_S_DECL
#define TEMP_S_FREE

引用了 a0, a1, a2, am1, ap1, b0, b1, bm1, bp1, lmmp_add_(), lmmp_add_1_(), lmmp_add_n_(), lmmp_add_n_sub_n_(), lmmp_cmp_(), lmmp_inc_1, lmmp_mul_(), lmmp_mul_n_, lmmp_mul_toom32_(), lmmp_param_assert, lmmp_shr1add_n_(), lmmp_shr1sub_n_(), lmmp_sub_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_zero, lmmp_zero_q_(), n, numb, r0, r1, r2, r3, restrict, s, SALLOC_TYPE, t, TEMP_S_DECL, TEMP_S_FREE, tp, v1 , 以及 vm1.

函数调用图: