LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
to_decimal.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/str_conv.h"
24#include "impl/inlines.h"
25#include "mparam.h"
26#include "impl/tmp_alloc.h"
27#include "lmmp/lmmpn.h"
28
30
31
33 int mslbits = 0;
34 if (numa) {
35 do {
36 if (na == 0)
37 return 1;
38 } while (numa[--na] == 0);
39 mslbits = lmmp_limb_bits_(numa[na]);
40 }
41 return lmmp_mulh_(na * LIMB_BITS + mslbits, lmmp_bases_table[DEC_BASE - 2].inv_lg_base) + 1;
42}
43
44typedef struct {
46 int top; // 已构建的最高层下标,-1 表示未初始化
48
50 .top = -1,
51};
52
53// 初始化第 0 层:10^19 = lmmp_bases_table[DEC_BASE-2].large_base
54static void dec_pow_init_(void) {
56 p0->p = (mp_ptr)lmmp_alloc(sizeof(mp_limb_t));
58 p0->np = 1;
59 p0->zeros = 0;
61 int cnt = lmmp_leading_zeros_(p0->p[0]);
62 if ((p0->norm_cnt = cnt))
63 lmmp_shl_(p0->p, p0->p, 1, cnt);
64 p0->invp = NULL;
65 p0->ni = 0;
66 p0->base = DEC_BASE;
68}
69
70/*
71 * 由第 k-1 层平方构建第 k 层:pow[k] = pow[k-1]^2 = 10^(19*2^k)。
72 * 设第 k-1 层真值 T = v * B^zeros(v 为剥离尾部零 limb 后的奇 limb 数),
73 * v 的尾零 bit 数 = 19*2^(k-1) mod 64 < 64,故 v^2 的尾零 limb 至多 1 个,
74 * 剥离后新 zeros = 2*zeros + 剥离数 = floor(19*2^k / 64)。
75 */
76static void dec_pow_extend_(int k) {
77 mp_basepow_t* pre = &dec_pow_ctx_g.pow[k - 1];
78 mp_size_t np = pre->np;
80 // buf 布局:[v: np(非归一化真值)| sq: 2np(平方结果)]
81 mp_ptr buf = BALLOC_TYPE(3 * np + 2, mp_limb_t);
82 mp_ptr v = buf, sq = buf + np;
83
84 lmmp_copy(v, pre->p, np);
85 if (pre->norm_cnt)
86 lmmp_shr_(v, v, np, pre->norm_cnt);
87 lmmp_sqr_(sq, v, np);
88
89 mp_size_t nq = 2 * np;
90 nq -= sq[nq - 1] == 0;
91 mp_size_t zeros = 2 * pre->zeros;
92 while (sq[0] == 0) {
93 ++zeros;
94 ++sq;
95 --nq;
96 }
97
99 cur->p = (mp_ptr)lmmp_alloc((size_t)nq * sizeof(mp_limb_t));
100 lmmp_copy(cur->p, sq, nq);
101 int cnt = lmmp_leading_zeros_(cur->p[nq - 1]);
102 if ((cur->norm_cnt = cnt))
103 lmmp_shl_(cur->p, cur->p, nq, cnt);
104 cur->np = nq;
105 cur->zeros = zeros;
106 cur->digits = (mp_size_t)lmmp_bases_table[DEC_BASE - 2].digits_in_limb << k;
107 cur->base = DEC_BASE;
108 if (nq < DIV_MULINV_L_THRESHOLD) {
109 // 规模较小,使用基础除法,无需预计算逆元
110 cur->invp = NULL;
111 cur->ni = 0;
112 } else {
113 mp_size_t ni = lmmp_div_inv_size_(nq + zeros, nq);
114 cur->invp = (mp_ptr)lmmp_alloc((size_t)ni * sizeof(mp_limb_t));
115 lmmp_inv_prediv_(cur->invp, cur->p, nq, ni);
116 cur->ni = ni;
117 }
118
120}
121
123 lmmp_param_assert(grps > 1 && ctop != NULL);
124 if (dec_pow_ctx_g.top < 0)
126 // 最高有效层:2^need <= grps,即 need = floor(log2(grps))
127 int need = lmmp_limb_bits_((mp_limb_t)grps) - 1;
128 while (dec_pow_ctx_g.top < need) {
131 }
132 *ctop = need;
133 return dec_pow_ctx_g.pow;
134}
135
137 if (dec_pow_ctx_g.top < 0)
138 return;
139 for (int i = 0; i <= dec_pow_ctx_g.top; ++i) {
141 if (dec_pow_ctx_g.pow[i].invp)
143 }
144 dec_pow_ctx_g.top = -1;
145}
146
148 lmmp_param_assert(dst != NULL && numa != NULL);
149 do {
150 if (na == 0)
151 return 0;
152 } while (numa[--na] == 0);
153 ++na;
154
156 return lmmp_to_str_basecase_((mp_byte_t*)dst, numa, na, DEC_BASE, '0');
157
158 // 惰性获取全局幂表
159 mp_size_t digits = lmmp_to_str_len_(numa, na, DEC_BASE);
160 mp_size_t grps = (digits - 1) / lmmp_bases_table[DEC_BASE - 2].digits_in_limb + 1;
161 int ctop;
162 mp_basepow_t* pows = lmmp_dec_pow_table_(grps, &ctop);
163
165 // numa 拷贝空间(多 1 limb 预留规整移位)+ 各层商空间
166 mp_size_t alloc = na + 1;
167 for (int i = 1; i <= ctop; ++i)
168 alloc += pows[i].np + pows[i].zeros + 1;
169 mp_ptr tp = BALLOC_TYPE(alloc, mp_limb_t);
170
171 lmmp_copy(tp, numa, na);
172 digits = lmmp_to_str_divide_((mp_byte_t*)dst, tp, na, pows + ctop, tp + na + 1, '0');
173
175 return digits;
176}
#define k
#define lmmp_limb_bits_
#define lmmp_leading_zeros_
#define lmmp_sqr_
#define lmmp_mulh_
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint8_t mp_byte_t
定义 lmmp.h:91
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
uint64_t mp_size_t
定义 lmmp.h:93
void * lmmp_alloc(size_t size)
内存分配函数(调用lmmp_heap_alloc_fn)
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_VECT_CONSERVATIVE
定义 lmmp.h:201
#define LMMP_THREAD_LOCAL
定义 lmmp.h:114
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define DIV_MULINV_L_THRESHOLD
#define TO_STR_BASEPOW_THRESHOLD
static mp_size_t lmmp_div_inv_size_(mp_size_t nq, mp_size_t nb)
计算预计算逆元的尺寸
mp_size_t lmmp_to_decimal_(char *dst, mp_srcptr numa, mp_size_t na)
limb数组转十进制字符串 [numa,na,B] to [dst,return value,10]
void lmmp_inv_prediv_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t ni)
除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.c:26
mp_size_t lmmp_to_str_len_(mp_srcptr numa, mp_size_t na, int base)
计算转换为字节数组,字节数组需要的缓冲区长度
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
mp_size_t lmmp_to_decimal_len_(mp_srcptr numa, mp_size_t na)
计算转换为十进制字符串需要的缓冲区长度
#define tp
mp_size_t digits
mp_size_t lmmp_to_str_basecase_(mp_byte_t *dst, mp_srcptr numa, mp_size_t na, int base, mp_byte_t off)
basecase limb 数组转字节串引擎
mp_basepow_t * lmmp_dec_pow_table_(mp_size_t grps, int *ctop)
获取(惰性构建/扩展)全局十进制幂表
void lmmp_dec_pow_table_free_(void)
释放全局十进制幂表(可重入)
mp_size_t lmmp_to_str_divide_(mp_byte_t *dst, mp_ptr numa, mp_size_t na, mp_basepow_t *pow, mp_ptr tpq, mp_byte_t off)
分治 limb 数组转字节串引擎
const mp_base_t lmmp_bases_table[255]
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define DEC_BASE
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t large_base
mp_size_t zeros
#define TEMP_B_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_B_FREE
mp_basepow_t pow[64]
static void dec_pow_extend_(int k)
static void dec_pow_init_(void)
static __thread dec_pow_ctx_t dec_pow_ctx_g