LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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 "mparam.h"
24#include "impl/mul_hard.h"
25#include "lmmp/lmmpn.h"
26
27
28/*
29 Areas where the different toom algorithms can be called
300 1/6 1/5 1/4 1/3 2/5 9/20 1/2 5/9 3/5 2/3 3/4 4/5 9/10 1 nb/na
31
32 (-------------------(xxxxxxxxxx| toom22
33 (----------------(xxxxxxxxxxxxxxx|----------) toom32
34 (----(xxxxxxxxxxxxxxxx|-------) toom42
35 (-------(xxxxxxxxxx| toom33
36(xxxxxxxxxxxxxxxxxxx| toom42-unblanced
37
38 (---(xxxxxxxxxx| toom44
39 (-------(xxxxxxxxxxx|----------) toom43
40 (---(xxxxxxxxxxxx|-------) toom53
41 (--------(xxxxxxx|----) toom52
42 (----(xxxxxxxx|---) toom62
43(xxxxxxxxxx| toom62-unblanced
44
45 (xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| toom6h
46
47 (xxxxxx|-----------------------------------------) toom8h
48 6/17
490 1/6 1/5 1/4 1/3 2/5 9/20 1/2 5/9 3/5 2/3 3/4 4/5 9/10 1 nb/na
50*/
51
53 lmmp_param_assert(na >= nb);
54 lmmp_param_assert(nb > 0);
55 if (na == nb) {
56 if (numa == numb)
57 lmmp_sqr_(dst, numa, na);
58 else
59 lmmp_mul_n_(dst, numa, numb, na);
60 } else if (nb < MUL_TOOM22_THRESHOLD && !(4 * na < 5 * nb)) {
61 lmmp_mul_basecase_(dst, numa, na, numb, nb);
62 } else if (((na + nb) >> 1) < MUL_TOOM44_THRESHOLD || 2 * nb < MUL_TOOM44_THRESHOLD) {
63 if (na < 3 * nb) {
64 if (4 * na < 5 * nb) {
65 if (nb < MUL_TOOM33_THRESHOLD)
66 lmmp_mul_toom22_(dst, numa, na, numb, nb);
67 else
68 lmmp_mul_toom33_(dst, numa, na, numb, nb);
69 } else if (5 * na < 9 * nb)
70 lmmp_mul_toom32_(dst, numa, na, numb, nb);
71 else
72 lmmp_mul_toom42_(dst, numa, na, numb, nb);
73 } else
74 lmmp_mul_toom42_unbalance_(dst, numa, na, numb, nb);
75 } else if (((na + nb) >> 1) < MUL_FFT_THRESHOLD || 3 * nb < MUL_FFT_THRESHOLD) {
76 if (nb >= MUL_TOOM6H_THRESHOLD && na < 4 * nb) {
77 if (nb < MUL_TOOM8H_THRESHOLD && 6 * na < 17 * nb)
78 lmmp_mul_toom6h_(dst, numa, na, numb, nb);
79 else
80 lmmp_mul_toom8h_(dst, numa, na, numb, nb);
81 } else if (na < 5 * nb) {
82 if (4 * na < 5 * nb)
83 lmmp_mul_toom44_(dst, numa, na, numb, nb);
84 else if (3 * na < 5 * nb)
85 lmmp_mul_toom43_(dst, numa, na, numb, nb);
86 else if (9 * na < 20 * nb)
87 lmmp_mul_toom53_(dst, numa, na, numb, nb);
88 else if (na < 3 * nb)
89 lmmp_mul_toom52_(dst, numa, na, numb, nb);
90 else
91 lmmp_mul_toom62_(dst, numa, na, numb, nb);
92 } else
93 lmmp_mul_toom62_unbalance_(dst, numa, na, numb, nb);
94 } else {
95 if (na < 6 * nb)
96 lmmp_mul_fft_(dst, numa, na, numb, nb);
97 else
98 lmmp_mul_fft_unbalance_(dst, numa, na, numb, nb);
99 }
100}
101
104 lmmp_mul_hard_n_(dst, numa, numb, n);
105 else if (n < MUL_TOOM33_THRESHOLD)
106 lmmp_mul_toom22_(dst, numa, n, numb, n);
107 else if (n < MUL_TOOM44_THRESHOLD)
108 lmmp_mul_toom33_(dst, numa, n, numb, n);
109 else if (n < MUL_TOOM6H_THRESHOLD)
110 lmmp_mul_toom44_(dst, numa, n, numb, n);
111 else if (n < MUL_TOOM8H_THRESHOLD)
112 lmmp_mul_toom6h_(dst, numa, n, numb, n);
113 else if (n < MUL_FFT_THRESHOLD)
114 lmmp_mul_toom8h_(dst, numa, n, numb, n);
115 else
116 lmmp_mul_fft_(dst, numa, n, numb, n);
117}
118
120 if (na < SQR_TOOM22_THRESHOLD)
121 lmmp_sqr_hard_n_(dst, numa, na);
122 else if (na < SQR_TOOM33_THRESHOLD)
123 lmmp_sqr_toom2_(dst, numa, na);
124 else if (na < SQR_TOOM44_THRESHOLD)
125 lmmp_sqr_toom3_(dst, numa, na);
126 else if (na < SQR_TOOM6_THRESHOLD)
127 lmmp_sqr_toom4_(dst, numa, na);
128 else if (na < SQR_TOOM8_THRESHOLD)
129 lmmp_sqr_toom6_(dst, numa, na);
130 else if (na < SQR_FFT_THRESHOLD)
131 lmmp_sqr_toom8_(dst, numa, na);
132 else
133 lmmp_sqr_fft_(dst, numa, na);
134}
#define lmmp_mul_n_
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
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
#define MUL_FFT_THRESHOLD
#define SQR_TOOM6_THRESHOLD
#define MUL_TOOM22_THRESHOLD
#define MUL_TOOM8H_THRESHOLD
#define SQR_FFT_THRESHOLD
#define SQR_TOOM44_THRESHOLD
#define MUL_TOOM33_THRESHOLD
#define SQR_TOOM8_THRESHOLD
#define MUL_TOOM6H_THRESHOLD
#define SQR_TOOM22_THRESHOLD
#define SQR_TOOM33_THRESHOLD
#define MUL_TOOM44_THRESHOLD
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]
void lmmp_mul_toom44_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-44乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom6h_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-6.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±4,...
void lmmp_mul_toom42_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-42乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_toom8_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-8平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±8,±4,±2,±1,±1/2,±1/4,±1/8,0,无inf点)
void lmmp_mul_toom42_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-42不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom43_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-43乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_basecase_(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_(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_sqr_fft_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
FFT平方运算 [dst,2*na] = [numa,na]^2
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]
void lmmp_mul_toom52_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-52乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom62_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-62乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_toom2_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-2平方运算 [dst,2*na] = [numa,na]^2
void lmmp_sqr_toom3_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-3平方运算 [dst,2*na] = [numa,na]^2
void lmmp_mul_fft_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom8h_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-8.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±8,...
void lmmp_mul_toom53_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-53乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_fft_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_toom6_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-6平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±4,±2,±1,±1/2,±1/4,0,无inf点)
void lmmp_mul_toom62_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-62不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom33_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-33乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_toom4_(mp_ptr dst, mp_srcptr numa, mp_size_t an)
Toom-4平方运算 [dst,2*na] = [numa,na]^2
#define lmmp_mul_hard_n_
#define lmmp_sqr_hard_n_
#define numb
#define n
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)