LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom22.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#define MAYBE_mul_toom22 (MUL_TOOM33_THRESHOLD >= 2 * MUL_TOOM22_THRESHOLD)
29
30#define lmmp_mul_n_(dst, numa, numb, n) \
31 if (!MAYBE_mul_toom22 || (n) < MUL_TOOM22_THRESHOLD) \
32 lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
33 else \
34 lmmp_mul_toom22_((dst), (numa), (n), (numb), (n))
35
36/*
37Evaluate in: -1, 0, +inf
38
39 <-s--><--n-->
40 |-a1-|--a0--|
41 |b1-|--b0--|
42 <-t-><--n-->
43
44v0 = a0 * b0 # A(0)*B(0)
45vm1 = (a0-a1)*(b0-b1) # A(-1)*B(-1)
46vinf= a1 * b1 # A(inf)*B(inf)
47*/
48
50 lmmp_param_assert(nb >= 5);
51 lmmp_param_assert(na >= nb);
52 lmmp_param_assert(2 * nb > na);
54 mp_size_t s = na >> 1, n = na - s, t = nb - n;
57 int vm1_neg = 0;
58 mp_slimb_t cy, cy2;
59
60#define a0 numa
61#define a1 (numa + n)
62#define b0 numb
63#define b1 (numb + n)
64#define asm1 dst
65#define bsm1 (dst + n)
66
67 if (s == n) {
68 if (lmmp_cmp_(a0, a1, n) < 0) {
70 vm1_neg = 1;
71 } else
73 } else { // s==n-1
74 if (a0[s] == 0 && lmmp_cmp_(a0, a1, s) < 0) {
76 asm1[s] = 0;
77 vm1_neg = 1;
78 } else
79 asm1[s] = a0[s] - lmmp_sub_n_(asm1, a0, a1, s);
80 }
81
82 if (t == n) {
83 if (lmmp_cmp_(b0, b1, n) < 0) {
85 vm1_neg ^= 1;
86 } else
88 } else {
89 if (lmmp_zero_q_(b0 + t, n - t) && lmmp_cmp_(b0, b1, t) < 0) {
91 lmmp_zero(bsm1 + t, n - t);
92 vm1_neg ^= 1;
93 } else
94 lmmp_sub_(bsm1, b0, n, b1, t);
95 }
96
98
99#undef asm1
100#undef bsm1
101#define v0 dst
102#define vinf (dst + 2 * n)
103
104 lmmp_mul_n_(v0, a0, b0, n);
105
106 lmmp_mul_(vinf, a1, s, b1, t);
107
108 cy = lmmp_add_n_(dst + 2 * n, v0 + n, vinf, n);
109 cy2 = cy + lmmp_add_n_(dst + n, dst + 2 * n, v0, n);
110 cy += lmmp_add_(dst + 2 * n, dst + 2 * n, n, vinf + n, s + t - n);
111
112 if (vm1_neg)
113 cy += lmmp_add_n_(dst + n, dst + n, vm1, 2 * n);
114 else
115 cy -= lmmp_sub_n_(dst + n, dst + n, vm1, 2 * n);
116
117 // no overflow, if s+t>n. proved.
118 lmmp_inc_1(dst + 2 * n, cy2);
119
120 if (cy < 0)
121 lmmp_dec(dst + 3 * n);
122 else
123 lmmp_inc_1(dst + 3 * n, cy);
125}
#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
int64_t mp_slimb_t
定义 lmmp.h:94
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
void lmmp_mul_toom22_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-22乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
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]
#define lmmp_dec(p)
减1宏(预期无借位)
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_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
#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 v0
#define bsm1
#define asm1
#define vinf
#define vm1
#define t
#define numb
#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