LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_fib.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 "lmmp/lmmpn.h"
24#include "lmmp/numth.h"
25#include "cases.h"
27
28/*
29 斐波那契验证(库内交叉 + 恒等式 + 写死常数):
30 1. 写死锚点:F(10)=55、F(50)=12586269025、F(93)=12200160415121876738
31 2. 链式递推:fibonacci2_(n) 的 F[n-1]/F[n] 与 fibonacci2_(n+1) 的
32 F[n]/F[n+1] 逐档衔接,且 F[n+1] == F[n] + F[n-1](库内加法)
33 3. 大规模抽查:递推链 + Cassini 恒等式(全库内,见下)
34*/
35
36TEST_CASE("numth/fib", small_exhaustive) {
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}
70
71/* 大规模抽查:递推链 F[n]=F[n-1]+F[n-2] 与 Cassini 恒等式 F[n-1]*F[n+1]-F[n]^2=(-1)^n,
72 均以库内加/乘法验证,覆盖奇偶、2 的幂、fibonacci_ 合并路径中 2F[k] 溢出的位组合 */
73
74TEST_CASE("numth/fib", large_recurrence_and_cassini) {
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}
128
129void test_fib(void) {
130 TEST_RUN("numth/fib", small_exhaustive);
131 TEST_RUN("numth/fib", large_recurrence_and_cassini);
132}
#define k
#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
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
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
void test_fib(void)
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(cond)
定义 test.h:37
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_CHECK_EQ(a, b)
定义 test.h:39
#define TEST_RUN(category, name)
定义 test.h:36