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

浏览该文件的源代码.

函数

 TEST_CASE ("numth/fib", large_recurrence_and_cassini)
 TEST_CASE ("numth/fib", small_exhaustive)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
void test_fib (void)

函数说明

◆ TEST_CASE() [1/2]

TEST_CASE ( "numth/fib" ,
large_recurrence_and_cassini  )

在文件 test_fib.c 第 74 行定义.

74 {
75 const ulong n_values[] = {94ul, 95ul, 187ul, 371ul, 373ul, 925ul, 1000ul, 4181ul, 65536ul, 65537ul,
76 100001ul, 131072ul, 150000ul};
77 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
78 ulong n = n_values[n_index];
80 mp_ptr a = alloc_limbs((size_t)rn); // F[n-1]
81 mp_ptr b = alloc_limbs((size_t)rn); // F[n]
82 mp_ptr c = alloc_limbs((size_t)rn); // F[n+1]
83 mp_ptr t = alloc_limbs((size_t)(2 * rn)); // fibonacci2_ 副输出 / F[n]^2
84 mp_ptr s = alloc_limbs((size_t)(2 * rn));
85
86 lmmp_zero(a, rn); lmmp_zero(b, rn); lmmp_zero(c, rn);
87 mp_size_t lb = lmmp_fibonacci2_(b, a, rn, n);
88 lmmp_zero(b + lb, rn - lb); lmmp_zero(a + lb, rn - lb);
89 mp_size_t lc = lmmp_fibonacci2_(c, t, rn, n + 1);
90 lmmp_zero(c + lc, rn - lc);
91
92 // 递推链:F[n+1] == F[n] + F[n-1]
93 lmmp_zero(s, 2 * rn);
94 mp_limb_t carry = lmmp_add_(s, b, rn, a, rn);
95 TEST_CHECK_MSG(carry == 0, "recurrence no carry");
96 TEST_CHECK_MSG(norm_len(s, 2 * rn) == lc, "recurrence size");
97 for (mp_size_t i = 0; i < lc; ++i) {
98 if (s[i] != c[i]) {
99 TEST_CHECK_MSG(false, "recurrence value");
100 break;
101 }
102 }
103
104 // fibonacci_ 与 fibonacci2_ 一致
105 mp_ptr d = alloc_limbs((size_t)lmmp_fibonacci_size_(n));
107 TEST_CHECK_MSG(ld == lb, "consistency size");
108 bool same = true;
109 for (mp_size_t i = 0; i < ld; ++i) same = same && (d[i] == b[i]);
110 TEST_CHECK_MSG(same, "consistency value");
111
112 // Cassini:F[n-1]*F[n+1] - F[n]^2 == (-1)^n
113 lmmp_mul_(s, a, rn, c, rn);
114 lmmp_sqr_(t, b, rn);
115 mp_limb_t borrow = lmmp_sub_(s, s, 2 * rn, t, 2 * rn);
116 if (n % 2 == 0) {
117 TEST_CHECK_MSG(borrow == 0 && s[0] == 1 && norm_len(s, 2 * rn) == 1, "Cassini +1");
118 } else {
119 // -1 即 2*rn 个全 F limb
120 bool allf = true;
121 for (mp_size_t i = 0; i < 2 * rn; ++i) allf = allf && (s[i] == LIMB_MAX);
122 TEST_CHECK_MSG(borrow == 1 && allf, "Cassini -1");
123 }
124
126 }
127}
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
#define LIMB_MAX
定义 lmmp.h:105
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,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_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
#define t
#define s
#define n
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]
uint64_t ulong
定义 numth.h:39
mp_size_t lmmp_fibonacci_size_(ulong n)
计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度
mp_size_t lmmp_fibonacci_(mp_ptr dst, mp_size_t rn, ulong n)
计算 Fibonacci 数 [dst,rn] = F[n]
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38

引用了 ARRAY_SIZE, LIMB_MAX, lmmp_add_(), lmmp_fibonacci2_(), lmmp_fibonacci_(), lmmp_fibonacci_size_(), lmmp_free(), lmmp_mul_(), lmmp_sqr_, lmmp_sub_(), lmmp_zero, n, s, t, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [2/2]

TEST_CASE ( "numth/fib" ,
small_exhaustive  )

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

在文件 test_fib.c 第 36 行定义.

36 {
37 // 写死常数锚点(值均 < 2^64)
38 struct known_result { ulong n; u64 v; } known[] = {
39 {10, 55ull}, {50, 12586269025ull},
40 {93, 12200160415121876738ull}, // FIB_TABLE_LIMIT 档(最后单 limb 表项)
41 };
42 for (size_t k_index = 0; k_index < ARRAY_SIZE(known); ++k_index) {
43 const struct known_result k = known[k_index];
44 mp_ptr d = alloc_limbs(2);
45 lmmp_zero(d, 2);
46 lmmp_fibonacci_(d, 2, k.n);
47 TEST_CHECK_EQ(d[0], k.v);
48 lmmp_free(d);
49 }
50
51 // 链式递推:F[n+1] == F[n] + F[n-1],两档 fibonacci2_ 输出衔接
52 const ulong NLIM = 500;
53 for (ulong n = 1; n <= NLIM; n += 7) {
54 mp_size_t rn = lmmp_fibonacci_size_(n + 1) + 1;
55 mp_ptr fa = alloc_limbs((size_t)rn), fb = alloc_limbs((size_t)rn);
56 mp_ptr fc = alloc_limbs((size_t)rn), fd = alloc_limbs((size_t)rn);
57 mp_ptr s = alloc_limbs((size_t)rn + 1);
58 lmmp_zero(fa, rn); lmmp_zero(fb, rn); lmmp_zero(fc, rn); lmmp_zero(fd, rn);
59
60 lmmp_fibonacci2_(fb, fa, rn, n); // fa = F[n-1], fb = F[n]
61 lmmp_fibonacci2_(fd, fc, rn, n + 1); // fc = F[n], fd = F[n+1]
62 TEST_CHECK(mpn_eq(fb, rn, fc, rn)); // 两档衔接:同 n 输出一致
63 lmmp_zero(s, rn + 1);
64 lmmp_add_(s, fb, rn, fa, rn);
65 TEST_CHECK(mpn_eq(s, rn + 1, fd, rn)); // F[n]+F[n-1] == F[n+1]
66
67 lmmp_free(fa); lmmp_free(fb); lmmp_free(fc); lmmp_free(fd); lmmp_free(s);
68 }
69}
#define k
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CHECK_EQ(a, b)
定义 test.h:39

引用了 ARRAY_SIZE, k, lmmp_add_(), lmmp_fibonacci2_(), lmmp_fibonacci_(), lmmp_fibonacci_size_(), lmmp_free(), lmmp_zero, n, s, TEST_CASE, TEST_CHECK , 以及 TEST_CHECK_EQ.

函数调用图:

◆ test_fib()

void test_fib ( void )

在文件 test_fib.c 第 129 行定义.

129 {
130 TEST_RUN("numth/fib", small_exhaustive);
131 TEST_RUN("numth/fib", large_recurrence_and_cassini);
132}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_fib() , 以及 TEST_RUN.

被这些函数引用 main() , 以及 test_fib().

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