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

浏览该文件的源代码.

函数

mp_limb_t lmmp_div_divide_ (mp_ptr restrict dstq, mp_ptr restrict numa, mp_size_t na, mp_srcptr restrict numb, mp_size_t nb, mp_limb_t inv21)
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)

函数说明

◆ lmmp_div_divide_()

mp_limb_t lmmp_div_divide_ ( mp_ptr restrict dstq,
mp_ptr restrict numa,
mp_size_t na,
mp_srcptr restrict numb,
mp_size_t nb,
mp_limb_t inv21 )

在文件 div_divide.c 第 87 行定义.

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
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
mp_limb_t lmmp_div_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法运算
#define numb
#define tp
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 LIMB_B_2, lmmp_div_divide_(), lmmp_div_divide_n_(), lmmp_div_s_(), lmmp_param_assert, numb, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

函数调用图:

◆ lmmp_div_divide_n_()

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 )
static

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

分治除法

参数
dstq结果商指针([dstq,n]=[numa,2*n] div [numb,n])
numa被除数指针([numa,n]=[numa,2*n] mod [numb,n])
numb除数指针
n除数长度
inv21除数高128位的逆
tp临时工作区指针(需要 n 个 limb 的空间)
警告
n>=6, MSB(numb)=1, inv21=(2^192-1)/[numb+n-2,2]-2^64, sep(dstq,numa,numb,tp)
返回
除法结果最高位商

在文件 div_divide.c 第 39 行定义.

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}
#define DIV_DIVIDE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
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_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 n
#define lo

引用了 DIV_DIVIDE_THRESHOLD, LIMB_B_2, lmmp_add_n_(), lmmp_div_basecase_(), lmmp_div_divide_n_(), lmmp_mul_(), lmmp_param_assert, lmmp_sub_1_(), lmmp_sub_n_(), lo, n, numb, restrict , 以及 tp.

被这些函数引用 lmmp_div_divide_() , 以及 lmmp_div_divide_n_().

函数调用图:
这是这个函数的调用关系图: