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

浏览该文件的源代码.

宏定义

#define FIB_LOG2PHI_FP   (0xb1b9d68a8e53425eull)
#define FIB_TABLE_LIMIT   93
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

static mp_size_t fib2_core_ (mp_ptr fp, mp_ptr f1p, mp_ptr tp, mp_size_t alloc, ulong n)
 Fibonacci 数对倍增核心:fp <- F[n],f1p <- F[n-1]
static mp_size_t fib_limbs_bound_ (ulong m)
 计算 F[m] 的 limb 长度紧上界
mp_size_t lmmp_fibonacci2_ (mp_ptr dst, mp_ptr dst2, mp_size_t rn, ulong n)
 计算 Fibonacci 数对:[dst,rn] = F[n],[dst2,rn] = F[n-1]
mp_size_t lmmp_fibonacci_ (mp_ptr dst, mp_size_t rn, ulong n)
 计算 Fibonacci 数 [dst,rn] = F[n]
mp_size_t lmmp_fibonacci_size_ (ulong n)
 计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度

变量

static const mp_limb_t fib_table [93+2]

宏定义说明

◆ FIB_LOG2PHI_FP

#define FIB_LOG2PHI_FP   (0xb1b9d68a8e53425eull)

在文件 fibonacci.c 第 83 行定义.

被这些函数引用 fib_limbs_bound_().

◆ FIB_TABLE_LIMIT

#define FIB_TABLE_LIMIT   93

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

在文件 fibonacci.c 第 80 行定义.

被这些函数引用 fib2_core_(), lmmp_fibonacci2_(), lmmp_fibonacci_() , 以及 lmmp_fibonacci_size_().

函数说明

◆ fib2_core_()

mp_size_t fib2_core_ ( mp_ptr fp,
mp_ptr f1p,
mp_ptr tp,
mp_size_t alloc,
ulong n )
static

Fibonacci 数对倍增核心:fp <- F[n],f1p <- F[n-1]

参数
fpF[n] 输出指针
f1pF[n-1] 输出指针
tp临时空间(alloc 个limb)
allocfp、f1p、tp 的公共容量(limb数)
n下标
警告
fp!=NULL, f1p!=NULL, tp!=NULL, sep(fp,f1p,tp), alloc >= 2*(limbs(F[n>>1])+1)+1
返回
F[n] 的实际 limb 长度(n==0 时 fp[0]==0); F[n-1] 至多多写一个高位0,实际长度为 ret-(f1p[ret-1]==0)

在文件 fibonacci.c 第 141 行定义.

141 {
142 ulong nfirst, mask;
143
144 /* 自顶截去低位直至落入查表范围,mask 对齐到 n 的剩余最高位 */
145 mask = 1;
146 for (nfirst = n; nfirst > FIB_TABLE_LIMIT; nfirst >>= 1) {
147 mask <<= 1;
148 }
149
150 f1p[0] = fib_table[nfirst]; /* F[nfirst-1] */
151 fp[0] = fib_table[nfirst + 1]; /* F[nfirst] */
152 mp_size_t size = 1;
153
154 if (mask == 1) {
155 return size;
156 }
157
158 do {
159 /* 此处 fp == F[k],f1p == F[k-1],k 为 n 自 mask 位向上的位串;
160 fp 归一化,f1p 至多一个高位0 */
161 lmmp_debug_assert(alloc >= 2 * size);
162 lmmp_sqr_(tp, fp, size); /* tp = F[k]^2 */
163 lmmp_sqr_(fp, f1p, size); /* fp = F[k-1]^2 */
164 size <<= 1;
165 size -= (tp[size - 1] == 0); /* fp 归一化故 tp 至多一个高位0 */
166
167 /* F[2k-1] = F[k]^2 + F[k-1]^2 */
168 f1p[size] = lmmp_add_n_(f1p, tp, fp, size);
169
170 /* F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k,n&mask 即 k 的最低位 */
171 lmmp_debug_assert((fp[0] & 2) == 0); /* fp 为平方数,bit1 必为0 */
172 fp[0] |= (n & mask ? 2 : 0); /* k 奇:给被减数加2即结果减2 */
173 mp_limb_t c = lmmp_shl_(tp, tp, size, 2); /* tp = 4*F[k]^2(溢出位入c)*/
174 tp[0] |= (n & mask ? 0 : 2); /* k 偶:4*F[k]^2 加2 */
175 fp[size] = c - lmmp_sub_n_(fp, tp, fp, size);
176 lmmp_debug_assert(alloc >= size + 1);
177 size += (fp[size] != 0);
178
179 /* 下一位 n&(mask>>1):为1则推进到 (F[2k+1], F[2k]),
180 为0则推进到 (F[2k], F[2k-1]),F[2k] = F[2k+1] - F[2k-1] */
181 mask >>= 1;
182 if (n & mask) {
183 lmmp_sub_n_(f1p, fp, f1p, size);
184 } else {
185 lmmp_sub_n_(fp, fp, f1p, size);
186 size -= (fp[size - 1] == 0);
187 }
188 } while (mask != 1);
189
190 return size;
191}
#define FIB_TABLE_LIMIT
Copyright (C) 2026 HJimmyK (Jericho Knox)
static const mp_limb_t fib_table[93+2]
#define lmmp_sqr_
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
uint64_t mp_limb_t
定义 lmmp.h:92
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_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_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 tp
#define n
uint64_t ulong
定义 numth.h:39

引用了 fib2_core_(), fib_table, FIB_TABLE_LIMIT, lmmp_add_n_(), lmmp_debug_assert, lmmp_shl_(), lmmp_sqr_, lmmp_sub_n_(), n , 以及 tp.

被这些函数引用 fib2_core_(), lmmp_fibonacci2_() , 以及 lmmp_fibonacci_().

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

◆ fib_limbs_bound_()

mp_size_t fib_limbs_bound_ ( ulong m)
inlinestatic

计算 F[m] 的 limb 长度紧上界

参数
mFibonacci 数列的下标
警告
m>=0
返回
limbs(F[m]) <= ret,至多多算 1 个 limb

在文件 fibonacci.c 第 118 行定义.

118 {
119 return (mp_size_t)(lmmp_mulh_(m, FIB_LOG2PHI_FP) / LIMB_BITS) + 1;
120}
#define FIB_LOG2PHI_FP
#define lmmp_mulh_
#define LIMB_BITS
定义 lmmp.h:102

引用了 fib_limbs_bound_(), FIB_LOG2PHI_FP, LIMB_BITS , 以及 lmmp_mulh_.

被这些函数引用 fib_limbs_bound_(), lmmp_fibonacci_() , 以及 lmmp_fibonacci_size_().

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

◆ lmmp_fibonacci2_()

mp_size_t lmmp_fibonacci2_ ( mp_ptr dst,
mp_ptr dst2,
mp_size_t rn,
ulong n )

计算 Fibonacci 数对:[dst,rn] = F[n],[dst2,rn] = F[n-1]

参数
dstF[n] 结果指针
dst2F[n-1] 结果指针
rndst 与 dst2 各自的 limb 缓冲区长度
nFibonacci 数列的下标
警告
dst!=NULL, dst2!=NULL, sep(dst,dst2), rn>=lmmp_fibonacci_size_(n)
返回
F[n] 的实际 limb 长度(n==0时,返回1);F[n-1] 的实际长度为ret-(dst2[ret-1]==0),至多比返回值少1

在文件 fibonacci.c 第 193 行定义.

193 {
194 lmmp_param_assert(dst != NULL && dst2 != NULL);
195#if LMMP_DEBUG_PARAM_ASSERT_CHECK == 1
197 lmmp_param_assert(rn >= need);
198#endif
199 if (n <= FIB_TABLE_LIMIT) {
200 dst[0] = fib_table[n + 1]; /* F[n] */
201 dst2[0] = fib_table[n]; /* F[n-1],n==0 时即 F[-1]=1 */
202 return 1;
203 }
204 TEMP_DECL;
206 mp_size_t size = fib2_core_(dst, dst2, tp, rn, n);
207 TEMP_FREE;
208 return size;
209}
static mp_size_t fib2_core_(mp_ptr fp, mp_ptr f1p, mp_ptr tp, mp_size_t alloc, ulong n)
Fibonacci 数对倍增核心:fp <- F[n],f1p <- F[n-1]
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_param_assert(x)
定义 lmmp.h:509
mp_size_t lmmp_fibonacci_size_(ulong n)
计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 fib2_core_(), fib_table, FIB_TABLE_LIMIT, lmmp_fibonacci2_(), lmmp_fibonacci_size_(), lmmp_param_assert, n, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

被这些函数引用 fib_pair(), lmmp_fibonacci2_(), lmmp_pow_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

◆ lmmp_fibonacci_()

mp_size_t lmmp_fibonacci_ ( mp_ptr dst,
mp_size_t rn,
ulong n )

计算 Fibonacci 数 [dst,rn] = F[n]

参数
dst结果指针
rndst 的 limb 缓冲区长度
nFibonacci 数列的下标
警告
dst!=NULL, rn>=lmmp_fibonacci_size_(n)
返回
F[n] 的实际 limb 长度(n==0 时 返回 0)

在文件 fibonacci.c 第 211 行定义.

211 {
212 lmmp_param_assert(dst != NULL);
213#if LMMP_DEBUG_PARAM_ASSERT_CHECK == 1
215 lmmp_param_assert(rn >= need);
216#else
217 (void)rn;
218#endif
219 if (n <= FIB_TABLE_LIMIT) {
220 dst[0] = fib_table[n + 1]; /* F[n],n==0 时为0 */
221 return (n == 0) ? 0 : 1;
222 }
223
224 /* k = n/2,先算出 (F[k], F[k-1]),再一次乘法合并。
225 limbs_bound(n2)+2 同时覆盖核心循环(2*limbs(F[n2>>1])+1)与
226 合并操作数 xp/yp 的写入(size+2)*/
227 ulong n2 = n >> 1;
228 mp_size_t xalloc = fib_limbs_bound_(n2) + 2;
229 TEMP_DECL;
230 mp_ptr xp = TALLOC_TYPE(xalloc, mp_limb_t);
231 mp_ptr yp = TALLOC_TYPE(xalloc, mp_limb_t);
232 mp_ptr tp = TALLOC_TYPE(xalloc, mp_limb_t);
233 mp_size_t size = fib2_core_(xp, yp, tp, xalloc, n2);
234 mp_size_t xsize, ysize;
235
236 if (n & 1) {
237 /* F[2k+1] = (2F[k]+F[k-1]) * (2F[k]-F[k-1]) + 2*(-1)^k */
238 mp_limb_t c2 = lmmp_shl_(dst, xp, size, 1); /* dst 暂存 2F[k] 低 size 位 */
239 mp_limb_t c = lmmp_add_n_(xp, dst, yp, size);
240 c += c2; /* 2F[k] 的溢出位并入最高 limb,c=[0|1|2] */
241 xp[size] = c;
242 xsize = size + (c != 0);
243 c2 -= lmmp_sub_n_(yp, dst, yp, size); /* yp = 2F[k]-F[k-1],c2=[0|1] */
244 lmmp_debug_assert(c2 <= 1);
245 yp[size] = c2;
246 ysize = size + c2;
247
248 lmmp_mul_(dst, xp, xsize, yp, ysize);
249 size = xsize + ysize;
250 if (n & 2) {
251 mp_limb_t b = lmmp_sub_1_(dst, dst, size, 2);
252 lmmp_debug_assert(b == 0);
253 } else {
254 mp_limb_t c3 = lmmp_add_1_(dst, dst, size, 2);
255 lmmp_debug_assert(c3 == 0);
256 }
257 } else {
258 /* F[2k] = F[k] * (F[k] + 2F[k-1]) */
259 mp_limb_t c = lmmp_addshl1_n_(yp, xp, yp, size); /* yp = F[k]+2F[k-1] */
260 yp[size] = c;
261 ysize = size + (c != 0);
262
263 lmmp_mul_(dst, yp, ysize, xp, size);
264 size += ysize;
265 }
266
267 size -= (dst[size - 1] == 0);
268 TEMP_FREE;
269 return size;
270}
static mp_size_t fib_limbs_bound_(ulong m)
计算 F[m] 的 limb 长度紧上界
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
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]
mp_limb_t lmmp_addshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
定义 shl.c:53
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
#define xp

引用了 fib2_core_(), fib_limbs_bound_(), fib_table, FIB_TABLE_LIMIT, lmmp_add_1_(), lmmp_add_n_(), lmmp_addshl1_n_(), lmmp_debug_assert, lmmp_fibonacci_(), lmmp_fibonacci_size_(), lmmp_mul_(), lmmp_param_assert, lmmp_shl_(), lmmp_sub_1_(), lmmp_sub_n_(), n, TALLOC_TYPE, TEMP_DECL, TEMP_FREE, tp , 以及 xp.

被这些函数引用 bench_fib(), lmmp_fibonacci_(), lmmp_pow_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

◆ lmmp_fibonacci_size_()

mp_size_t lmmp_fibonacci_size_ ( ulong n)

计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度

参数
nFibonacci 数列的下标
返回
缓冲区长度,比 F[n] 的实际长度多 2-4 个 limb

在文件 fibonacci.c 第 122 行定义.

122 {
123 if (n <= FIB_TABLE_LIMIT) {
124 return 1;
125 }
126 return 2 * (fib_limbs_bound_(n >> 1) + 1) + 2;
127}

引用了 fib_limbs_bound_(), FIB_TABLE_LIMIT, lmmp_fibonacci_size_() , 以及 n.

被这些函数引用 bench_fib(), fib_pair(), lmmp_fibonacci2_(), lmmp_fibonacci_(), lmmp_fibonacci_size_(), lmmp_pow_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

变量说明

◆ fib_table

const mp_limb_t fib_table[93+2]
static
初始值:
= {
0x0000000000000001ull, 0x0000000000000000ull, 0x0000000000000001ull, 0x0000000000000001ull,
0x0000000000000002ull, 0x0000000000000003ull, 0x0000000000000005ull, 0x0000000000000008ull,
0x000000000000000dull, 0x0000000000000015ull, 0x0000000000000022ull, 0x0000000000000037ull,
0x0000000000000059ull, 0x0000000000000090ull, 0x00000000000000e9ull, 0x0000000000000179ull,
0x0000000000000262ull, 0x00000000000003dbull, 0x000000000000063dull, 0x0000000000000a18ull,
0x0000000000001055ull, 0x0000000000001a6dull, 0x0000000000002ac2ull, 0x000000000000452full,
0x0000000000006ff1ull, 0x000000000000b520ull, 0x0000000000012511ull, 0x000000000001da31ull,
0x000000000002ff42ull, 0x000000000004d973ull, 0x000000000007d8b5ull, 0x00000000000cb228ull,
0x0000000000148addull, 0x0000000000213d05ull, 0x000000000035c7e2ull, 0x00000000005704e7ull,
0x00000000008cccc9ull, 0x0000000000e3d1b0ull, 0x0000000001709e79ull, 0x0000000002547029ull,
0x0000000003c50ea2ull, 0x0000000006197ecbull, 0x0000000009de8d6dull, 0x000000000ff80c38ull,
0x0000000019d699a5ull, 0x0000000029cea5ddull, 0x0000000043a53f82ull, 0x000000006d73e55full,
0x00000000b11924e1ull, 0x000000011e8d0a40ull, 0x00000001cfa62f21ull, 0x00000002ee333961ull,
0x00000004bdd96882ull, 0x00000007ac0ca1e3ull, 0x0000000c69e60a65ull, 0x0000001415f2ac48ull,
0x000000207fd8b6adull, 0x0000003495cb62f5ull, 0x0000005515a419a2ull, 0x00000089ab6f7c97ull,
0x000000dec1139639ull, 0x000001686c8312d0ull, 0x000002472d96a909ull, 0x000003af9a19bbd9ull,
0x000005f6c7b064e2ull, 0x000009a661ca20bbull, 0x00000f9d297a859dull, 0x000019438b44a658ull,
0x000028e0b4bf2bf5ull, 0x000042244003d24dull, 0x00006b04f4c2fe42ull, 0x0000ad2934c6d08full,
0x0001182e2989ced1ull, 0x0001c5575e509f60ull, 0x0002dd8587da6e31ull, 0x0004a2dce62b0d91ull,
0x000780626e057bc2ull, 0x000c233f54308953ull, 0x0013a3a1c2360515ull, 0x001fc6e116668e68ull,
0x00336a82d89c937dull, 0x00533163ef0321e5ull, 0x00869be6c79fb562ull, 0x00d9cd4ab6a2d747ull,
0x016069317e428ca9ull, 0x023a367c34e563f0ull, 0x039a9fadb327f099ull, 0x05d4d629e80d5489ull,
0x096f75d79b354522ull, 0x0f444c01834299abull, 0x18b3c1d91e77decdull, 0x27f80ddaa1ba7878ull,
0x40abcfb3c0325745ull, 0x68a3dd8e61eccfbdull, 0xa94fad42221f2702ull,
}

在文件 fibonacci.c 第 85 行定义.

被这些函数引用 fib2_core_(), lmmp_fibonacci2_() , 以及 lmmp_fibonacci_().