LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
div_divide.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/tmp_alloc.h"
25#include "lmmp/lmmpn.h"
26
27
28/**
29 * @brief 分治除法
30 * @param dstq 结果商指针([dstq,n]=[numa,2*n] div [numb,n])
31 * @param numa 被除数指针([numa,n]=[numa,2*n] mod [numb,n])
32 * @param numb 除数指针
33 * @param n 除数长度
34 * @param inv21 除数高128位的逆
35 * @param tp 临时工作区指针(需要 n 个 limb 的空间)
36 * @warning n>=6, MSB(numb)=1, inv21=(2^192-1)/[numb+n-2,2]-2^64, sep(dstq,numa,numb,tp)
37 * @return 除法结果最高位商
38 */
40 mp_ptr restrict dstq,
41 mp_ptr restrict numa,
44 mp_limb_t inv21,
46) {
47 lmmp_param_assert(n >= 6);
48 lmmp_param_assert(dstq != NULL && numa != NULL && numb != NULL);
50 mp_size_t lo = n >> 1, hi = n - lo;
51 mp_limb_t cy, qh, ql;
52
53 if (hi < DIV_DIVIDE_THRESHOLD) {
54 qh = lmmp_div_basecase_(dstq + lo, numa + 2 * lo, 2 * hi, numb + lo, hi, inv21);
55 } else {
56 qh = lmmp_div_divide_n_(dstq + lo, numa + 2 * lo, numb + lo, hi, inv21, tp);
57 }
58 lmmp_mul_(tp, dstq + lo, hi, numb, lo);
59
60 cy = lmmp_sub_n_(numa + lo, numa + lo, tp, n);
61 if (qh)
62 cy += lmmp_sub_n_(numa + n, numa + n, numb, lo);
63
64 while (cy) {
65 qh -= lmmp_sub_1_(dstq + lo, dstq + lo, hi, 1);
66 cy -= lmmp_add_n_(numa + lo, numa + lo, numb, n);
67 }
68
70 ql = lmmp_div_basecase_(dstq, numa + hi, 2 * lo, numb + hi, lo, inv21);
71 } else {
72 ql = lmmp_div_divide_n_(dstq, numa + hi, numb + hi, lo, inv21, tp);
73 }
74 lmmp_mul_(tp, numb, hi, dstq, lo);
75
76 cy = lmmp_sub_n_(numa, numa, tp, n);
77 if (ql)
78 cy += lmmp_sub_n_(numa + lo, numa + lo, numb, hi);
79
80 while (cy) {
81 lmmp_sub_1_(dstq, dstq, lo, 1);
82 cy -= lmmp_add_n_(numa, numa, numb, n);
83 }
84 return qh;
85}
86
88 mp_ptr restrict dstq,
89 mp_ptr restrict numa,
90 mp_size_t na,
92 mp_size_t nb,
93 mp_limb_t inv21
94) {
95 lmmp_param_assert(na >= 2 * nb);
96 lmmp_param_assert(nb >= 6);
98 mp_size_t nq = na - nb;
99
100 dstq += nq;
101 numa += nq;
102
103 do {
104 nq -= nb;
105 } while (nq >= nb);
106
107 dstq -= nq;
108 numa -= nq;
109
110 /* Perform the typically smaller block first. */
111 mp_limb_t qh = lmmp_div_s_(dstq, numa, nb + nq, numb, nb);
112
113 TEMP_DECL;
115 nq = na - nb - nq;
116
117 do {
118 dstq -= nb;
119 numa -= nb;
120 lmmp_div_divide_n_(dstq, numa, numb, nb, inv21, tp);
121 nq -= nb;
122 } while (nq > 0);
123
124 TEMP_FREE;
125 return qh;
126}
static mp_limb_t lmmp_div_divide_n_(mp_ptr restrict dstq, mp_ptr restrict numa, mp_srcptr restrict numb, mp_size_t n, mp_limb_t inv21, mp_ptr restrict tp)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define LIMB_B_2
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
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define DIV_DIVIDE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_div_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t 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]
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_div_basecase_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
基础除法运算
mp_limb_t lmmp_div_divide_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
分治除法运算
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 numb
#define tp
#define n
#define lo
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)