LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
log2_exp2.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 "numth/log2_exp2.h"
24#include "impl/longlong.h"
25
26/*
27 记 B = 2^64,x 为 [0,1) 上的小数(64bit 或 128bit 定点),本文件计算
28 log2(1+x) 与 2^x - 1 的定点值。结构为“查表约简 + 短泰勒级数”:
29 log2 查表索引为 5bit(级数 27/14 项),exp2 为 7bit 且 Q 表由
30 16/128 两级表运行时合成(级数 13/7 项)。
31
32 约简恒等式(i 为索引,xl 为剩余低位):
33
34 log2(1+x) = L[i] + log2(1+u),u = xl/(2^k*(32+i)) < 2^-5
35 2^x - 1 = Q * (2^t),Q = 2^(i/128),t < 2^-7
36
37 u 由倒数表(2^128/(32+i) 的定点值 lg2_R32)一次乘法获得。级数
38 按奇偶次幂分组(w = u^2 或 t^2,均为正系数规避符号分支):
39
40 log2(1+u) = u*B(w) - w*A(w)
41 2^t - 1 = t*B(w) + w*A(w)
42
43 项数由首个截断项 < 2^-66(64bit 输出)/ 2^-130(128bit 输出)
44 确定:log2 侧 u < 2^-5 故 m 项覆盖 m*5 个 bit(27/14 项),exp2
45 侧 m*7(13/7 项)。lg2 系数按 2^191 尺度截取高 2 limb 存储(c1 =
46 1/ln2 > 1 超出定点范围,链与收尾按半尺度 2^63/2^127 推进、结果
47 左移 1 位恢复;低 limb 为死数据不存);xp2 系数均 < 1,按满尺度
48 2^192 截取高 2 limb 存储。求值形态:64bit log2 用 Estrin 树
49 (w2/w4 预平方,关键路径 6 级 mul -> 3 级);128bit 版 B/A 链
50 全展开,非收尾步用 3 乘法舍入 hi128(umul128_tohi128_r,省去
51 a0*b0 全积、以交叉和顶位舍入,|e| <= 1 ulp 且均值近零),每步
52 误差被后续 w^j 衰减(log2 侧 2^-10j、exp2 侧 2^-14j)至预算
53 之下,收尾 1~2 步保留全精度 floor。exp2_64 的 Q 表合成同样用
54 舍入式 hi128(其 1 ulp 误差经 >>64 后 < 2^-63)。
55
56 舍入控制:约简变量 u 的定点化为误差主源(~0.7 ulp),其余各级
57 floor 系统性偏负,故 64bit 版 B/A 链取 floor 而收尾以 +2^63 /
58 舍入位中心化,exp2 的表合成(T16/T8 四舍五入存、T8 运行时再舍入
59 取高位)与 s、Q*s 项亦取舍入值。接口承诺 |e| <= 2 ulp。
60
61 常量表由纯整数高精度脚本离线生成(scripts/lmmp/gen_log2_exp2.py,
62 atanh/exp 级数求值,ln2 取 768bit 定点),每张表首行为 i=0。
63*/
64
65static const uint64_t lg2_L32[32][3] = {
66 {0x0000000000000000ull, 0x0000000000000000ull, 0x0000000000000000ull},
67 {0x6366f25ae368399cull, 0x9b03784b5be08490ull, 0x0b5d69bac77ec398ull},
68 {0xca507cfab1d27f98ull, 0xcc53826144575ac3ull, 0x1663f6fac913167cull},
69 {0x9e77fd40e0401d05ull, 0x4f78dfa14aa5157aull, 0x2118b119b4f3c72cull},
70 {0x49e7cd4744b36080ull, 0x401624140d175ba2ull, 0x2b803473f7ad0f3full},
71 {0x41057dd4287e22f1ull, 0xc23d9780306c696aull, 0x359ebc5b69d927dfull},
72 {0x99eaddb5a9520d6aull, 0x51b3314f09de6be4ull, 0x3f782d7204d01447ull},
73 {0x41e86a7632602708ull, 0x16e52e91300efeefull, 0x49101eac381ce609ull},
74 {0x65b157f8deceb53aull, 0x24afdbfd36bf6d33ull, 0x5269e12f346e2bf9ull},
75 {0x9f890503285f6d81ull, 0x35482d13dc0f110cull, 0x5b8887367433795eull},
76 {0x5dba8beba3cb180bull, 0xcad415ae1a715618ull, 0x646eea247c5c22d2ull},
77 {0x14a805ee427197fcull, 0x51bbe3f6289e3ab7ull, 0x6d1fafdce20a8290ull},
78 {0x3e730bb7410e895bull, 0xfaf866415554d6bfull, 0x759d4f80cba83bf8ull},
79 {0xaf992540238215bbull, 0x64c6001143d6c8d5ull, 0x7dea15a32c1b3b38ull},
80 {0x3f2869dd6be1d1ccull, 0x12ba94db12ef0aa8ull, 0x86082806b1d532c4ull},
81 {0xeac6aab2e0ef8a67ull, 0xa89d4ee66c3700e3ull, 0x8df988f4ae806f1dull},
82 {0x24f3e6a3a259b040ull, 0xa00b120a068badd1ull, 0x95c01a39fbd6879full},
83 {0x718d4a9002e2cf95ull, 0x5592074827cb508eull, 0x9d5d9fd5010b3666ull},
84 {0xcb62aff1bd9d6a74ull, 0x495fb7fa6d7eda66ull, 0xa4d3c25e68dc57f2ull},
85 {0xef44639e542c2fd8ull, 0x6c5e946b4ae30894ull, 0xac241134c4e99e1cull},
86 {0x1cf483d2900676c7ull, 0x76da1c872983511eull, 0xb35004723c465e69ull},
87 {0xbf0dfbe6ebff7d3bull, 0x2bc1fe8a8648e9ebull, 0xba58feb2703a9e37ull},
88 {0x6edbb3eae70d10c1ull, 0xe021361e13a30973ull, 0xc1404eadf38396deull},
89 {0xa42463b01fdd3e95ull, 0x1fa8423e8c1443f2ull, 0xc80730b0001667f2ull},
90 {0x38c6a548017167caull, 0x2ac903a413e5a847ull, 0xceaecfea80859b33ull},
91 {0xbedec4594babbdabull, 0xf1be4359106a19b5ull, 0xd53847ac00a69be6ull},
92 {0x05d84c6e2eadff07ull, 0x5b8a19b1c637671full, 0xdba4a47aa996d25aull},
93 {0x712f104646b61eb0ull, 0x4c5a724dbd8180f8ull, 0xe1f4e5170d02a99bull},
94 {0x8aa53e9c8128657aull, 0xc4baee073d4b1b04ull, 0xe829fb693044b398ull},
95 {0xa7bd10d27c064978ull, 0x39d5d6a218c6339full, 0xee44cd59ffab62f3ull},
96 {0x06c1f1d26c710872ull, 0x0d1e3f80fbc71454ull, 0xf446359b13539551ull},
97 {0x82ae728f4624c84bull, 0x6adf27b820fd03e9ull, 0xfa2f045e7832aa72ull}
98};
99
100static const uint64_t lg2_R32[32][2] = {
101 {0x0000000000000000ull, 0x0800000000000000ull},
102 {0x7c1f07c1f07c1f07ull, 0x07c1f07c1f07c1f0ull},
103 {0x8787878787878787ull, 0x0787878787878787ull},
104 {0x7507507507507507ull, 0x0750750750750750ull},
105 {0x71c71c71c71c71c7ull, 0x071c71c71c71c71cull},
106 {0x5306eb3e45306eb3ull, 0x06eb3e45306eb3e4ull},
107 {0xf286bca1af286bcaull, 0x06bca1af286bca1aull},
108 {0x6906906906906906ull, 0x0690690690690690ull},
109 {0x6666666666666666ull, 0x0666666666666666ull},
110 {0x63e7063e7063e706ull, 0x063e7063e7063e70ull},
111 {0x6186186186186186ull, 0x0618618618618618ull},
112 {0xf417d05f417d05f4ull, 0x05f417d05f417d05ull},
113 {0x5d1745d1745d1745ull, 0x05d1745d1745d174ull},
114 {0x5b05b05b05b05b05ull, 0x05b05b05b05b05b0ull},
115 {0x21642c8590b21642ull, 0x0590b21642c8590bull},
116 {0x882b9310572620aeull, 0x0572620ae4c415c9ull},
117 {0x5555555555555555ull, 0x0555555555555555ull},
118 {0x0a72f05397829cbcull, 0x05397829cbc14e5eull},
119 {0x51eb851eb851eb85ull, 0x051eb851eb851eb8ull},
120 {0x0505050505050505ull, 0x0505050505050505ull},
121 {0x4ec4ec4ec4ec4ec4ull, 0x04ec4ec4ec4ec4ecull},
122 {0x4873ecade304d487ull, 0x04d4873ecade304dull},
123 {0xf684bda12f684bdaull, 0x04bda12f684bda12ull},
124 {0x4a7904a7904a7904ull, 0x04a7904a7904a790ull},
125 {0x4924924924924924ull, 0x0492492492492492ull},
126 {0xf7047dc11f7047dcull, 0x047dc11f7047dc11ull},
127 {0x69ee58469ee58469ull, 0x0469ee58469ee584ull},
128 {0x15b1e5f75270d045ull, 0x0456c797dd49c341ull},
129 {0x4444444444444444ull, 0x0444444444444444ull},
130 {0x4325c53ef368eb04ull, 0x04325c53ef368eb0ull},
131 {0x4210842108421084ull, 0x0421084210842108ull},
132 {0x4104104104104104ull, 0x0410410410410410ull}
133};
134
135static const uint64_t xp2_T16[16][2] = {
136 {0x0000000000000000ull, 0x0000000000000000ull},
137 {0x8b92b71842a98364ull, 0x0b5586cf9890f629ull},
138 {0xf7c8c50eb14a7920ull, 0x172b83c7d517adcdull},
139 {0x1fadb1c15cb593b0ull, 0x2387a6e75623866cull},
140 {0x8d5a46305c85ededull, 0x306fe0a31b7152deull},
141 {0x41223e13d773fba3ull, 0x3dea64c12342235bull},
142 {0x397afec42e20e036ull, 0x4bfdad5362a271d4ull},
143 {0x93015191eb345d89ull, 0x5ab07dd48542958cull},
144 {0xb2fb1366ea957d3eull, 0x6a09e667f3bcc908ull},
145 {0x51023f6cda1f5ef4ull, 0x7a11473eb0186d7dull},
146 {0x7c55a192c9bb3e6full, 0x8ace5422aa0db5baull},
147 {0xc46b071f2be58ddbull, 0x9c49182a3f0901c7ull},
148 {0x734d1773205a7fbcull, 0xae89f995ad3ad5e8ull},
149 {0x0cb12a091ba66794ull, 0xc199bdd85529c222ull},
150 {0xa05aeb66e0dca9f6ull, 0xd5818dcfba48725dull},
151 {0xf73a18f5db301f87ull, 0xea4afa2a490d9858ull}
152};
153
154static const uint64_t xp2_T8[8][3] = {
155 {0x0000000000000000ull, 0x0000000000000000ull, 0x0000000000000000ull},
156 {0x03ec04c360be2404ull, 0x4a66ae336dcdfa40ull, 0x0163da9fb33356d8ull},
157 {0x3d70a2cabc5cb89cull, 0xf7caca4f7a29bde9ull, 0x02c9a3e778060ee6ull},
158 {0x40bb4bfc05af6456ull, 0x38f9a20da47e6ed0ull, 0x04315e86e7f84bd7ull},
159 {0x53e3495f7df4baf8ull, 0x7c548eb68ca417feull, 0x059b0d31585743aeull},
160 {0xcb8b092ac75e3117ull, 0xc403a9d87b27ed07ull, 0x0706b29ddf6ddc6dull},
161 {0x1b2d6829d8993a0dull, 0x35f25d9427fa2b04ull, 0x0874518759bc808cull},
162 {0x2e023da730e7fccbull, 0x1e060c584d6b74baull, 0x09e3ecac6f383452ull}
163};
164
165static const uint64_t lg2_c27[27][2] = {
166 {0xbe87fed0691d3e88ull, 0xb8aa3b295c17f0bbull},
167 {0xdf43ff68348e9f44ull, 0x5c551d94ae0bf85dull},
168 {0x3f82aa45785f14d8ull, 0x3d8e13b87407fae9ull},
169 {0xefa1ffb41a474fa2ull, 0x2e2a8eca5705fc2eull},
170 {0x594e6629ae9f72e8ull, 0x24eed8a1df37fcf2ull},
171 {0x9fc15522bc2f8a6cull, 0x1ec709dc3a03fd74ull},
172 {0x645c921dc5df9b38ull, 0x1a61762a7aded93full},
173 {0x77d0ffda0d23a7d1ull, 0x171547652b82fe17ull},
174 {0x6a80e36c7d7506f2ull, 0x1484b13d7c02a8f8ull},
175 {0x2ca73314d74fb974ull, 0x12776c50ef9bfe79ull},
176 {0x5723a2cd20d41cf5ull, 0x10c9a84994022d28ull},
177 {0x4fe0aa915e17c536ull, 0x0f6384ee1d01febaull},
178 {0x711e274b1bc72c31ull, 0x0e347ab4698bb00eull},
179 {0xb22e490ee2efcd9cull, 0x0d30bb153d6f6c9full},
180 {0x731a220de4dfd0f8ull, 0x0c4f9d8b4a67fefbull},
181 {0xbbe87fed0691d3e8ull, 0x0b8aa3b295c17f0bull},
182 {0xa1cbc3b1e810c771ull, 0x0adcd64dba1f86a1ull},
183 {0x354071b63eba8379ull, 0x0a42589ebe01547cull},
184 {0x4d65793363d91e3dull, 0x09b81e0fa687ff32ull},
185 {0x9653998a6ba7dcbaull, 0x093bb62877cdff3cull},
186 {0x76c98609ec9fde68ull, 0x08cb27637e4a486aull},
187 {0x2b91d166906a0e7aull, 0x0864d424ca011694ull},
188 {0x77969bc6475a50a1ull, 0x080766bf04010a77ull},
189 {0x27f05548af0be29bull, 0x07b1c2770e80ff5dull},
190 {0xab76146ebc864a2eull, 0x0762f8205fd7ff63ull},
191 {0x388f13a58de39618ull, 0x071a3d5a34c5d807ull},
192 {0xce2af6797f270250ull, 0x06d6e5bf29563852ull}
193};
194
195static const uint64_t xp2_c[13][2] = {
196 {0xc9e3b39803f2f6afull, 0xb17217f7d1cf79abull},
197 {0xde2d60dd92e6bf95ull, 0x3d7f7bff058b1d50ull},
198 {0x99d3b15d995e96f7ull, 0x0e35846b82505fc5ull},
199 {0x39977c16a7dd58a0ull, 0x0276556df749cee5ull},
200 {0x41c5fda69452fb0cull, 0x005761ff9e299cc4ull},
201 {0xb7a58544c3591a0full, 0x000a184897c363c3ull},
202 {0x34358a8e643ec734ull, 0x0000ffe5fe2c4586ull},
203 {0x23fd8ffe606da77cull, 0x0000162c0223a5c8ull},
204 {0x7c3da4a70e5a4ff9ull, 0x000001b5253d395eull},
205 {0x8ec9f6fda1d952e7ull, 0x0000001e4cf5158bull},
206 {0x1bb24c0f57995e47ull, 0x00000001e8cac735ull},
207 {0xfc2985e2b5687e17ull, 0x000000001c3bd650ull},
208 {0x166d0f96281ac300ull, 0x0000000001816193ull}
209};
210
211
212// hi128(a*b):128bit 定点积的最高 128bit
213static inline __uint128_t umul128_tohi128(__uint128_t a, __uint128_t b) {
214 uint64_t a0 = (uint64_t)a, a1 = (uint64_t)(a >> 64);
215 uint64_t b0 = (uint64_t)b, b1 = (uint64_t)(b >> 64);
216 __uint128_t p01 = (__uint128_t)a0 * b1;
217 __uint128_t p10 = (__uint128_t)a1 * b0;
218 __uint128_t p11 = (__uint128_t)a1 * b1;
219 __uint128_t w1 = (__uint128_t)(uint64_t)(((__uint128_t)a0 * b0) >> 64) + (uint64_t)p01 + (uint64_t)p10;
220 __uint128_t w2 = (p01 >> 64) + (p10 >> 64) + (uint64_t)p11 + (uint64_t)(w1 >> 64);
221 return ((__uint128_t)((uint64_t)(p11 >> 64) + (uint64_t)(w2 >> 64)) << 64) | (uint64_t)w2;
222}
223
224/*
225 hi128(a*b) 的 3 乘法舍入近似(省去 a0*b0):精确值 = p11 + cy +
226 (mid>>64) + floor((mid_lo + hi(a0*b0))/2^64),末项进位 ∈{0,1};
227 以 round(mid_lo/2^64)(mid_lo 顶位)替代,两者均 ∈{0,1},故
228 |e| <= 1 ulp、均值近零。用于级数链非收尾步——该误差随后被 w
229 的幂衰减到输出预算之下。
230*/
231static inline __uint128_t umul128_tohi128_r(__uint128_t a, __uint128_t b) {
232 uint64_t a0 = (uint64_t)a, a1 = (uint64_t)(a >> 64);
233 uint64_t b0 = (uint64_t)b, b1 = (uint64_t)(b >> 64);
234 __uint128_t p01 = (__uint128_t)a0 * b1;
235 __uint128_t p10 = (__uint128_t)a1 * b0;
236 __uint128_t mid = p01 + p10;
237 uint64_t cy = (mid < p01);
238 return ((__uint128_t)a1 * b1) + (mid >> 64) + ((__uint128_t)cy << 64) + ((uint64_t)mid >> 63);
239}
240
241// r = x + y(128 位;调用点均为 r==x 就地模式,r==y 会丢失进位)
242#define add_u128(r, x, y) \
243 do { \
244 (r)[0] = (x)[0] + (y)[0]; \
245 (r)[1] = (x)[1] + (y)[1] + ((r)[0] < (y)[0] ? 1 : 0); \
246 } while (0)
247
248// r = x - y(128 位;同上)
249#define sub_u128(r, x, y) \
250 do { \
251 uint64_t _b_ = (x)[0] < (y)[0]; \
252 (r)[0] = (x)[0] - (y)[0]; \
253 (r)[1] = (x)[1] - (y)[1] - _b_; \
254 } while (0)
255
256// i += j(192 位;同上)
257#define add_u192(i, j) \
258 do { \
259 (i)[0] += (j)[0]; \
260 uint64_t _c_ = ((i)[0] < (j)[0]) ? 1 : 0; \
261 (i)[1] += _c_; \
262 _c_ = ((i)[1] < _c_) ? 1 : 0; \
263 (i)[1] += (j)[1]; \
264 _c_ += ((i)[1] < (j)[1]) ? 1 : 0; \
265 (i)[2] += _c_ + (j)[2]; \
266 } while (0)
267
268// i -= j(192 位;同上)
269#define sub_u192(i, j) \
270 do { \
271 uint64_t _b_ = ((i)[0] < (j)[0]) ? 1 : 0; \
272 (i)[0] -= (j)[0]; \
273 uint64_t _b1_ = ((i)[1] < (j)[1]) ? 1 : 0; \
274 (i)[1] -= (j)[1]; \
275 _b1_ += ((i)[1] < _b_) ? 1 : 0; \
276 (i)[1] -= _b_; \
277 (i)[2] = (i)[2] - ((j)[2] + _b1_); \
278 } while (0)
279
280
281uint64_t log2_fixed_64(uint64_t x) {
282 unsigned i = (unsigned)(x >> 59);
283 uint64_t xl = x & 0x07FFFFFFFFFFFFFFull;
284
285 /*
286 v = u*2^128 = xl*2^69/(32+i),u < 2^-5。乘子 iv = floor(2^69/(32+i))
287 由 128bit 倒数表右移导出;i=0 时精确值 2^64 超出单 limb,钳位为
288 2^64-1(v 误差 < xl < 2^59,相对 < 2^-64,可忽略)。xl*iv <
289 2^59*2^64 = 2^123,128bit 全积恰为 v 本身(尺度已对齐)。
290 */
291 uint64_t v[2];
292 uint64_t iv = i ? ((lg2_R32[i][1] << 5) | (lg2_R32[i][0] >> 59)) : UINT64_MAX;
293 _umul64to128_(xl, iv, &v[0], &v[1]);
294
295 // w = u^2*2^64(链乘子),wf = u^2*2^128(收尾乘子)
296 uint64_t rr[4];
297 _usqr128to256_(v[1], v[0], rr);
298 uint64_t w = rr[3];
299
300 /*
301 64bit 输出下 B 误差预算 ~2^-59(经 u 因子放大前),w 每层衰减
302 2^-10,整条链单 limb(2^63 半尺度)即可:链值取 lg2_c27 顶
303 limb。B 为奇次项(m=1..13),A 为偶次项(m=2..14),首个截断
304 项 m=15 < 2^-75 < 2^-66 预算。
305 */
306 /*
307 Estrin 求值树(w2=w^2, w4=w^4):B/A 各 7/6 次 mulhi 不变,
308 乘法关键路径 6 级 -> 3 级,B/A 两树独立并行。
309 */
310 uint64_t w2 = _umul64to64hi_(w, w);
311 uint64_t w4 = _umul64to64hi_(w2, w2);
312 uint64_t b01 = _umul64to64hi_(lg2_c27[2][1], w) + lg2_c27[0][1];
313 uint64_t b23 = _umul64to64hi_(lg2_c27[6][1], w) + lg2_c27[4][1];
314 uint64_t b45 = _umul64to64hi_(lg2_c27[10][1], w) + lg2_c27[8][1];
315 uint64_t a01 = _umul64to64hi_(lg2_c27[3][1], w) + lg2_c27[1][1];
316 uint64_t a23 = _umul64to64hi_(lg2_c27[7][1], w) + lg2_c27[5][1];
317 uint64_t a45 = _umul64to64hi_(lg2_c27[11][1], w) + lg2_c27[9][1];
318 uint64_t b03 = _umul64to64hi_(b23, w2) + b01;
319 uint64_t a03 = _umul64to64hi_(a23, w2) + a01;
320 uint64_t b46 = _umul64to64hi_(lg2_c27[12][1], w2) + b45;
321 uint64_t a46 = _umul64to64hi_(lg2_c27[13][1], w2) + a45;
322 uint64_t B = _umul64to64hi_(b46, w4) + b03;
323 uint64_t A = _umul64to64hi_(a46, w4) + a03;
324
325 // t1 = (v*B)>>64、t2 = (wf*A)>>64,均取 2^127 半尺度
326 uint64_t p[2], q[2], t1[2], t2[2];
327 _umul64to128_(v[1], B, &p[0], &p[1]);
328 _umul64to128_(v[0], B, &q[0], &q[1]);
329 t1[0] = q[1] + p[0];
330 t1[1] = p[1] + (t1[0] < q[1]);
331 _umul64to128_(rr[3], A, &p[0], &p[1]);
332 _umul64to128_(rr[2], A, &q[0], &q[1]);
333 t2[0] = q[1] + p[0];
334 t2[1] = p[1] + (t2[0] < q[1]);
335
336 // result = (L[i] + 2*(t1-t2))>>64,溢出 2^128 时钳位;L 复用 L32 高 2 limb
337 sub_u128(t1, t1, t2);
338 t1[0] = (t1[0] << 1) | (t1[1] >> 63);
339 t1[1] <<= 1;
340 add_u128(t1, t1, lg2_L32[i] + 1);
341 if (t1[1] < lg2_L32[i][2]) return UINT64_MAX;
342 return t1[1];
343}
344
345uint64_t exp2_fixed_64(uint64_t x) {
346 unsigned i = (unsigned)(x >> 57);
347 uint64_t t = x & 0x01FFFFFFFFFFFFFFull;
348
349 // w = t^2*2^64,z = t^4*2^64
350 uint64_t wf[2];
351 _umul64to128_(t, t, &wf[0], &wf[1]);
352 uint64_t w = wf[1];
353 uint64_t z = _umul64to64hi_(w, w);
354
355 // B = (b0+w*b1) + z*(b2+w*b3),A = a0+w*(a1+w*a2),单 limb 满尺度链
356 uint64_t p1 = _umul64to64hi_(xp2_c[2][1], w) + xp2_c[0][1];
357 uint64_t p2 = _umul64to64hi_(xp2_c[6][1], w) + xp2_c[4][1];
358 uint64_t B = _umul64to64hi_(p2, z) + p1;
359 uint64_t A = _umul64to64hi_(xp2_c[5][1], w) + xp2_c[3][1];
360 A = _umul64to64hi_(A, w) + xp2_c[1][1];
361
362 // S = s*2^128 = t*B + w*A,sh = round(s*2^64)
363 uint64_t s0[2], s1[2];
364 _umul64to128_(t, B, &s0[0], &s0[1]);
365 _umul64to128_(w, A, &s1[0], &s1[1]);
366 uint64_t sl = s0[0] + s1[0];
367 uint64_t sh = s0[1] + s1[1] + (sl < s0[0]) + (sl >> 63);
368
369 /*
370 q = (2^(i/128)-1)*2^64:两级表 128bit 全量合成(丢弃表低位分数
371 会被 T16 的大因子放大 ~1ulp,须完整求和),舍入取高 64bit。
372 mm 同样舍入化,全链误差 |e| <= 2。
373 */
374 unsigned k = i >> 3, m = i & 7;
375 uint64_t t8h = xp2_T8[m][1] + (xp2_T8[m][0] >> 63);
376 __uint128_t t8t = ((__uint128_t)(xp2_T8[m][2] + (t8h < xp2_T8[m][1])) << 64) | t8h;
377 // qq 仅供 2^128 尺度合成后舍入取高 64bit,hi128 的 1 ulp(2^-128)
378 // 误差经 >>64 后 < 2^-63,用 3 乘法舍入式即可
379 __uint128_t qq = umul128_tohi128_r(((__uint128_t)xp2_T16[k][1] << 64) | xp2_T16[k][0], t8t);
380 uint64_t q0 = xp2_T16[k][0] + (uint64_t)qq;
381 uint64_t cy = (q0 < (uint64_t)qq);
382 q0 += (uint64_t)t8t;
383 cy += (q0 < (uint64_t)t8t);
384 uint64_t q = xp2_T16[k][1] + (uint64_t)(t8t >> 64) + (uint64_t)(qq >> 64) + cy + (q0 >> 63);
385 uint64_t ml, mh;
386 _umul64to128_(q, sh, &ml, &mh);
387 uint64_t r = q + sh + mh + (ml >> 63);
388 if (r < sh) return UINT64_MAX;
389 return r;
390}
391
392void log2_fixed_128(uint64_t* dst, uint64_t high, uint64_t low) {
393 unsigned i = (unsigned)(high >> 59);
394 uint64_t h2 = high & 0x07FFFFFFFFFFFFFFull;
395
396 // xls = xl*2^5(128bit 对齐),v = u*2^128 = hi128(xls*R32[i])
397 uint64_t xls[2] = {low << 5, (h2 << 5) | (low >> 59)};
398 uint64_t rr[4];
399 _umul128to256_(xls[1], xls[0], lg2_R32[i][1], lg2_R32[i][0], rr);
400 uint64_t v[2] = {rr[2], rr[3]};
401
402 // wf = u^2*2^128(链乘子)
403 _usqr128to256_(v[1], v[0], rr);
404 __uint128_t wf = ((__uint128_t)rr[3] << 64) | rr[2];
405
406 /*
407 交错 Horner:B 奇链 c25 -> c1(lg2_c27[24] -> [0]),A 偶链
408 c26 -> c2([25] -> [1]),单循环双累加器维持 ILP=2。128bit 输出
409 下 B 误差预算 ~2^-122,链取双 limb(2^127 半尺度);首个截断项
410 m=27 < 2^-135 < 2^-130 预算。链值以 __uint128_t 局部量保活,
411 避免数组形态在循环内产生栈回读写。
412 非收尾步用 3 乘法舍入 hi128(umul128_tohi128_r):每步 <= 1 ulp
413 误差被后续 wf^j(<= 2^-10j)衰减,j >= 1 即 <= 2^-138,远低于
414 预算;收尾 2 步保留全精度 floor。乘法数 104 -> 84。
415 */
416 __uint128_t B = ((__uint128_t)lg2_c27[24][1] << 64) | lg2_c27[24][0];
417 __uint128_t A = ((__uint128_t)lg2_c27[25][1] << 64) | lg2_c27[25][0];
418 for (int k = 22; k >= 5; k -= 2) {
419 B = umul128_tohi128_r(B, wf) + (((__uint128_t)lg2_c27[k][1] << 64) | lg2_c27[k][0]);
420 A = umul128_tohi128_r(A, wf) + (((__uint128_t)lg2_c27[k + 1][1] << 64) | lg2_c27[k + 1][0]);
421 }
422 B = umul128_tohi128_r(B, wf) + (((__uint128_t)lg2_c27[4][1] << 64) | lg2_c27[4][0]);
423 A = umul128_tohi128_r(A, wf) + (((__uint128_t)lg2_c27[5][1] << 64) | lg2_c27[5][0]);
424 B = umul128_tohi128(B, wf) + (((__uint128_t)lg2_c27[2][1] << 64) | lg2_c27[2][0]);
425 A = umul128_tohi128(A, wf) + (((__uint128_t)lg2_c27[3][1] << 64) | lg2_c27[3][0]);
426 B = umul128_tohi128(B, wf) + (((__uint128_t)lg2_c27[0][1] << 64) | lg2_c27[0][0]);
427 A = umul128_tohi128(A, wf) + (((__uint128_t)lg2_c27[1][1] << 64) | lg2_c27[1][0]);
428
429 // P = 2*(u*B - wf*A),t1/t2 取 256bit 积的高 192bit(2^191 半尺度)
430 uint64_t t1[3], t2[3];
431 _umul128to256_(v[1], v[0], (uint64_t)(B >> 64), (uint64_t)B, rr);
432 t1[0] = rr[1];
433 t1[1] = rr[2];
434 t1[2] = rr[3];
435 _umul128to256_((uint64_t)(wf >> 64), (uint64_t)wf, (uint64_t)(A >> 64), (uint64_t)A, rr);
436 t2[0] = rr[1];
437 t2[1] = rr[2];
438 t2[2] = rr[3];
439 sub_u192(t1, t2);
440 t1[2] = (t1[2] << 1) | (t1[1] >> 63);
441 t1[1] = (t1[1] << 1) | (t1[0] >> 63);
442 t1[0] <<= 1;
443
444 // result192 = L32[i] + P,加 2^63 使 >>64 截断舍入化,输出高 128bit
445 add_u192(t1, lg2_L32[i]);
446 if (t1[2] < lg2_L32[i][2]) {
447 dst[0] = dst[1] = UINT64_MAX;
448 return;
449 }
450 t1[0] += 0x8000000000000000ull;
451 if (t1[0] < 0x8000000000000000ull) {
452 if (++t1[1] == 0 && ++t1[2] == 0) {
453 dst[0] = dst[1] = UINT64_MAX;
454 return;
455 }
456 }
457 dst[0] = t1[1];
458 dst[1] = t1[2];
459}
460
461void exp2_fixed_128(uint64_t* dst, uint64_t high, uint64_t low) {
462 unsigned i = (unsigned)(high >> 57);
463 uint64_t W[2] = {low, high & 0x01FFFFFFFFFFFFFFull}; // W = t*2^128(精确)
464
465 // wf = t^2*2^128(链乘子)
466 uint64_t rr[4], zz[4];
467 _usqr128to256_(W[1], W[0], rr);
468 __uint128_t wfe = ((__uint128_t)rr[3] << 64) | rr[2];
469
470 /*
471 交错 Horner:B 奇链 c13 -> c1(xp2_c[12] -> [0]),A 偶链
472 c12 -> c2([11] -> [1]),链双 limb(2^128 满尺度,xp2 系数
473 均 < 1);首个截断项 m=15 < 2^-133 < 2^-130 预算。
474 */
475 // 非收尾步用 3 乘法舍入 hi128:每步 <= 1 ulp 误差被后续 wfe^j
476 // (<= 2^-14j)衰减,j >= 1 即 <= 2^-142;收尾步全精度。48 -> 38 乘法。
477 __uint128_t B = ((__uint128_t)xp2_c[12][1] << 64) | xp2_c[12][0];
478 __uint128_t A = ((__uint128_t)xp2_c[11][1] << 64) | xp2_c[11][0];
479 B = umul128_tohi128_r(B, wfe) + (((__uint128_t)xp2_c[10][1] << 64) | xp2_c[10][0]);
480 A = umul128_tohi128_r(A, wfe) + (((__uint128_t)xp2_c[9][1] << 64) | xp2_c[9][0]);
481 B = umul128_tohi128_r(B, wfe) + (((__uint128_t)xp2_c[8][1] << 64) | xp2_c[8][0]);
482 A = umul128_tohi128_r(A, wfe) + (((__uint128_t)xp2_c[7][1] << 64) | xp2_c[7][0]);
483 B = umul128_tohi128_r(B, wfe) + (((__uint128_t)xp2_c[6][1] << 64) | xp2_c[6][0]);
484 A = umul128_tohi128_r(A, wfe) + (((__uint128_t)xp2_c[5][1] << 64) | xp2_c[5][0]);
485 B = umul128_tohi128_r(B, wfe) + (((__uint128_t)xp2_c[4][1] << 64) | xp2_c[4][0]);
486 A = umul128_tohi128_r(A, wfe) + (((__uint128_t)xp2_c[3][1] << 64) | xp2_c[3][0]);
487 B = umul128_tohi128_r(B, wfe) + (((__uint128_t)xp2_c[2][1] << 64) | xp2_c[2][0]);
488 A = umul128_tohi128_r(A, wfe) + (((__uint128_t)xp2_c[1][1] << 64) | xp2_c[1][0]);
489 B = umul128_tohi128(B, wfe) + (((__uint128_t)xp2_c[0][1] << 64) | xp2_c[0][0]);
490
491 // S = s*2^192 = t*B + w*A(取 256bit 积高 192bit),sh = s*2^128
492 uint64_t S[3], u2[3];
493 _umul128to256_(W[1], W[0], (uint64_t)(B >> 64), (uint64_t)B, rr);
494 S[0] = rr[1];
495 S[1] = rr[2];
496 S[2] = rr[3];
497 _umul128to256_((uint64_t)(wfe >> 64), (uint64_t)wfe, (uint64_t)(A >> 64), (uint64_t)A, zz);
498 u2[0] = zz[1];
499 u2[1] = zz[2];
500 u2[2] = zz[3];
501 add_u192(S, u2);
502 uint64_t sh[2];
503 sh[0] = S[1] + (S[0] >> 63);
504 sh[1] = S[2] + (sh[0] < S[1]);
505
506 // q = (2^(i/128)-1)*2^128 = T16 + T8高2limb(舍入) + hi128(T16*T8)
507 unsigned k = i >> 3, m = i & 7;
508 uint64_t t8h = xp2_T8[m][1] + (xp2_T8[m][0] >> 63);
509 uint64_t t8t[2] = {t8h, xp2_T8[m][2] + (t8h < xp2_T8[m][1])};
510 uint64_t q[2], m2[2];
511 _umul128to256_(xp2_T16[k][1], xp2_T16[k][0], t8t[1], t8t[0], rr);
512 m2[0] = rr[2] + (rr[1] >> 63);
513 m2[1] = rr[3] + (m2[0] < rr[2]);
514 q[0] = xp2_T16[k][0];
515 q[1] = xp2_T16[k][1];
516 add_u128(q, q, t8t);
517 add_u128(q, q, m2);
518
519 /*
520 result = q + sh + round128(q*sh):q/sh 的构造与 m 的 hi128 均已
521 舍入化,加 1 中心化后全链 |e| <= 2。
522 */
523 _umul128to256_(q[1], q[0], sh[1], sh[0], rr);
524 m2[0] = rr[2] + (rr[1] >> 63);
525 m2[1] = rr[3] + (m2[0] < rr[2]);
526 uint64_t r0 = q[0], r1 = q[1], cy;
527 r0 += sh[0], cy = (r0 < sh[0]);
528 r1 += cy, cy = (r1 < cy);
529 r1 += sh[1], cy += (r1 < sh[1]);
530 if (cy) {
531 dst[0] = dst[1] = UINT64_MAX;
532 return;
533 }
534 r0 += m2[0], cy = (r0 < m2[0]);
535 r1 += cy, cy = (r1 < cy);
536 r1 += m2[1], cy += (r1 < m2[1]);
537 dst[0] = r0;
538 dst[1] = r1;
539}
#define k
#define B
#define A
void exp2_fixed_128(uint64_t *dst, uint64_t high, uint64_t low)
计算 floor(exp2(x/B)*B-B), B=2^128
static const uint64_t xp2_T8[8][3]
static const uint64_t lg2_L32[32][3]
Copyright (C) 2026 HJimmyK (Jericho Knox)
static const uint64_t xp2_c[13][2]
static __uint128_t umul128_tohi128_r(__uint128_t a, __uint128_t b)
#define sub_u128(r, x, y)
void log2_fixed_128(uint64_t *dst, uint64_t high, uint64_t low)
计算 floor(log2(1+x/B)*B), B=2^128
#define add_u192(i, j)
#define add_u128(r, x, y)
static __uint128_t umul128_tohi128(__uint128_t a, __uint128_t b)
static const uint64_t xp2_T16[16][2]
uint64_t exp2_fixed_64(uint64_t x)
计算 floor(exp2(x/B)*B-B), B=2^64
static const uint64_t lg2_c27[27][2]
static const uint64_t lg2_R32[32][2]
uint64_t log2_fixed_64(uint64_t x)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define sub_u192(i, j)
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
static void _umul128to256_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4])
static void _usqr128to256_(uint64_t a_high, uint64_t a_low, uint64_t rr[4])
#define b0
#define b1
#define a0
#define a1
#define r1
#define r0
#define t
#define w2