c++ 用复数算法高效实现N个Fibonacci数

t9aqgxwy 于 2023-05-30 发布在其他

关注(0)|答案(4)|浏览(158)

我正在寻找一种更快的方法来计算前N个斐波那契数。我已经知道使用记忆法解决这个问题的递归方法，以及从1 - N迭代的更简单的方法。但是，有没有一种数学方法我可以解决这个问题;或者另一种算法，甚至可以使这个过程稍微短一点？
我目前使用memoization和递归的实现速度相当快，但它不能满足我的需求。

#include<bits/stdc++.h>
using namespace std;
 
int fib(int n) {
    int a = 0, b = 1, c, i;
    if( n == 0)
        return a;
    for(i = 2; i <= n; i++)
    {
       c = a + b;
       a = b;
       b = c;
    }
    return b;
}

int main()
{
    int n = 9;
    cout << fib(n);
}

c++

来源：https://stackoverflow.com/questions/76344624/efficient-implementation-of-the-n-fibonacci-numbers-using-complex-algorithm

4条答案

按热度按时间

oxcyiej71#

不要否认查找表的强大功能。

一般来说，绝对数学比较快。然而，本页中介绍和讨论的一些数学解决方案依赖于浮点数学和pow函数。两者都可能是不精确的。
Fib（46）开始接近32位有符号整数的极限。Fib（92）是有符号64位整数的极限。因此，简单地对答案进行硬编码是一件合理的事情。
我知道从计算的Angular 来看这不是你想要的答案。但是，如果你真的需要在现实世界中计算 fib（n），并且在不同的平台上使用合理的值不会导致溢出或浮点偏差，那么很难对此提出异议。

int fib32(int n) {
    const static int table[] = {
    0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,
    1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,
    1836311903 };

    if (n < 0 || n >= sizeof(table) / sizeof(table[0])) {
        return -1;
    }

    return table[n];
}

long long fib64(long long n) {
    const static long long table[] = {0LL, 1LL, 1LL, 2LL, 3LL, 5LL, 8LL, 13LL, 21LL, 34LL, 55LL, 89LL, 144LL, 233LL, 377LL, 610LL, 987LL, 1597LL, 2584LL, 4181LL, 6765LL, 10946LL, 17711LL, 28657LL, 46368LL, 75025LL, 121393LL, 196418LL, 317811LL, 514229LL, 832040LL, 1346269LL, 2178309LL,
        3524578LL, 5702887LL, 9227465LL, 14930352LL, 24157817LL, 39088169LL, 63245986LL, 102334155LL, 165580141LL, 267914296LL, 433494437LL, 701408733LL, 1134903170LL, 1836311903LL, 2971215073LL, 4807526976LL, 7778742049LL, 12586269025LL, 20365011074LL, 32951280099LL, 53316291173LL, 86267571272LL, 139583862445LL, 225851433717LL, 365435296162LL, 591286729879LL, 956722026041LL, 1548008755920LL, 2504730781961LL,
        4052739537881LL, 6557470319842LL, 10610209857723LL, 17167680177565LL, 27777890035288LL, 44945570212853LL, 72723460248141LL, 117669030460994LL, 190392490709135LL, 308061521170129LL, 498454011879264LL, 806515533049393LL, 1304969544928657LL, 2111485077978050LL, 3416454622906707LL, 5527939700884757LL, 8944394323791464LL, 14472334024676221LL, 23416728348467685LL, 37889062373143906LL, 61305790721611591LL, 99194853094755497LL, 160500643816367088LL,
        259695496911122585LL, 420196140727489673LL, 679891637638612258LL, 1100087778366101931LL, 1779979416004714189LL, 2880067194370816120LL, 4660046610375530309LL, 7540113804746346429LL};

    if (n < 0 || n >= sizeof(table)/sizeof(table[0])) {
        return -1;
    }

    return table[n];
}

赞(0）回复(0）举报 2023-05-30

t5zmwmid2#

使用Binet's formula。
下面是C++中的一个基本实现：

#include <cmath>
#include <iostream>

const double onesq5 = 0.44721359549995793928183473374626; // 1/sqrt(5)
const double phi1 = 1.6180339887498948482045868343656; // (1 + sqrt(5)) / 2
const double phi2 = -0.61803398874989484820458683436564; // (1 - sqrt(5)) / 2

uint64_t fib(int n)
{
    return onesq5 * (pow(phi1, n) - pow(phi2, n));
}

int main()
{
    for (int i = 1; i < 50; ++i)
       std::cout << fib(i) << "\n";
}

Live Example
1.没有迭代或递归来获得nth Fibonacci数-它是直接计算的。
1.对Binet公式使用memoization是可以的，因为您不会用fib(n)的相同值多次调用pow。

赞(0）回复(0）举报 2023-05-30

o8x7eapl3#

没有一个例子在编译时使用C++的全部功能来创建这样的表（https://godbolt.org/z/nMeqj6xvq）：

#include <array>
#include <cstdint>
#include <iostream>

//construct the table at compile time

template<std::size_t N>
static constexpr auto create_fibonacci_table()
{
    std::array<std::uint64_t, N> table{ 0,1 };

    for (std::size_t n = 2; n < table.size(); ++n)
    {
        table[n] = table[n - 1ul] + table[n - 2ul];
    }

    return table;
}

int main()
{
    static constexpr auto fibonacci_table = create_fibonacci_table<12>();
    std::cout << fibonacci_table[9ul];
    return 0;
}

赞(0）回复(0）举报 2023-05-30

9wbgstp74#

为了好玩，我用下面的代码做了一个快速的比较：

#include <cmath>
#include <iostream>
#include <chrono>
#include <locale>

unsigned long long fib(unsigned input) {
    unsigned long long old1 = 0;
    unsigned long long old2 = 1;

    for (int i = 1; i < input; i++) {
        unsigned long long sum = old1 + old2;
        old1 = old2;
        old2 = sum;
    }
    return old2;
}

unsigned long long fib64(long long n)
{
    const static unsigned long long table[] = { 0ULL, 1ULL, 1ULL, 2ULL, 3ULL, 5ULL, 8ULL, 13ULL, 21ULL, 34ULL, 55ULL, 89ULL, 144ULL, 233ULL, 377ULL, 610ULL, 987ULL, 1597ULL, 2584ULL, 4181ULL, 6765ULL, 10946ULL, 17711ULL, 28657ULL, 46368ULL, 75025ULL, 121393ULL, 196418ULL, 317811ULL, 514229ULL, 832040ULL, 1346269ULL, 2178309ULL,
        3524578ULL, 5702887ULL, 9227465ULL, 14930352ULL, 24157817ULL, 39088169ULL, 63245986ULL, 102334155ULL, 165580141ULL, 267914296ULL, 433494437ULL, 701408733ULL, 1134903170ULL, 1836311903ULL, 2971215073ULL, 4807526976ULL, 7778742049ULL, 12586269025ULL, 20365011074ULL, 32951280099ULL, 53316291173ULL, 86267571272ULL, 139583862445ULL, 225851433717ULL, 365435296162ULL, 591286729879ULL, 956722026041ULL, 1548008755920ULL, 2504730781961ULL,
        4052739537881ULL, 6557470319842ULL, 10610209857723ULL, 17167680177565ULL, 27777890035288ULL, 44945570212853ULL, 72723460248141ULL, 117669030460994ULL, 190392490709135ULL, 308061521170129ULL, 498454011879264ULL, 806515533049393ULL, 1304969544928657ULL, 2111485077978050ULL, 3416454622906707ULL, 5527939700884757ULL, 8944394323791464ULL, 14472334024676221ULL, 23416728348467685ULL, 37889062373143906ULL, 61305790721611591ULL, 99194853094755497ULL, 160500643816367088ULL,
        259695496911122585ULL, 420196140727489673ULL, 679891637638612258ULL, 1100087778366101931ULL, 1779979416004714189ULL, 2880067194370816120ULL, 4660046610375530309ULL, 7540113804746346429ULL, 12200160415121876738ULL };

    if (n < 0 || n >= sizeof(table) / sizeof(table[0])) {
        return -1;
    }

    return table[n];
}

const double onesq5 = 0.44721359549995793928183473374626; // 1/sqrt(5)
const double phi1 = 1.6180339887498948482045868343656; // (1 + sqrt(5)) / 2
const double phi2 = -0.61803398874989484820458683436564; // (1 - sqrt(5)) / 2

uint64_t fib_binet(int n)
{
    return onesq5 * (pow(phi1, n) - pow(phi2, n));
}

int main() {
    using namespace std::chrono;

    auto start = high_resolution_clock::now();
    auto res = fib(93);
    auto stop = high_resolution_clock::now();

    auto start2 = high_resolution_clock::now();
    auto res2 = fib64(92);
    auto stop2 = high_resolution_clock::now();

    auto start3 = high_resolution_clock::now();
    auto res3 = fib_binet(92);
    auto stop3 = high_resolution_clock::now();

    std::cout.imbue(std::locale(""));
    std::cout << res << "\t"<< res2 << "\t" << res3 << "\n";
    std::cout << "iteration time: " << duration_cast<nanoseconds>(stop - start) << "\n";
    std::cout << "Lookup time: " << duration_cast<nanoseconds>(stop2 - start2) << "\n";
    std::cout << "Binet time: " << duration_cast<nanoseconds>(stop3 - start3) << "\n";
}

我得到的结果如下：

12,200,160,415,121,876,738      12,200,160,415,121,876,738      12,200,160,415,121,913,856
iteration time: 0ns
Lookup time: 0ns
Binet time: 10,691ns

观察结果：

虽然理论上是精确的，但当在计算机上使用浮点运算实现时，比奈公式可能产生不精确的结果。
虽然很明显，当数字足够大时，它会赢，但对于适合64位整数的结果，比奈的公式相对较慢。
我使用的实现似乎具有427 ns的最小测量时间，这不足以有意义地测量其他两个。

稍微推测一下，在迭代和表查找之间进行选择可能并不简单。我想这很大程度上取决于通话模式。表查找显然是O（1），但涉及的常数可能变化很大。如果你从该高速缓存中检索数据，它会非常快，但如果你必须从主内存中检索任何数据，那将是 * 相当 * 慢。如果你仔细地反复调用它以获取所有的fib（1）到fib（93），访问模式将是相当可预测的，所以在典型的CPU上，除了第一个缓存行之外的所有缓存行都将被预取该高速缓存中，所以总时间将是1个主内存读取+92个缓存读取。
在最新的CPU上读取主存储器大约需要42个时钟周期+51 ns。后续的缓存读取可能来自L1缓存，每次读取大约需要4个时钟。因此，对于这种在紧密循环中被调用的模式，我们总共得到约92*4个时钟+51ns。在（比如）4 GHz时，这大约是92+51ns或143ns。
但是，如果我们将对它的调用与许多其他代码交织在一起，那么基本上所有的读取都来自主内存而不是缓存，那么计算所有这些最终将达到93 *（42个时钟+51ns）。在这种情况下，在我们假设的4 GHz处理器上，它的最终时间约为5，700 ns。
相比之下，迭代算法每次迭代可能需要大约一个时钟（一次加法，两次移动，其可能被处理为ROB中的寄存器重命名）。为了计算fib（1）到fib（93），平均46.5次迭代，总共大约46.5 * 93 = 4325个时钟。在4 GHz时，这大约是1，100 ns。
因此，为了计算所有这些，迭代解的速度从大约10倍慢到大约5倍快。
旁注：根据您使用的编译器，它可能会或可能不会直接打印出每个算法的最后时间产生的持续时间。在这种情况下，更改：duration_cast<nanoseconds>(stop - start)到类似duration_cast<nanoseconds>(stop - start).count() << "ns"的值。

参考

这里有一页关于内存访问速度的测试结果（需要注意的是，这显然取决于你使用的处理器和内存）。
https://www.7-cpu.com/cpu/Skylake.html

赞(0）回复(0）举报 2023-05-30

我来回答

c++ 用复数算法高效实现N个Fibonacci数

4条答案

参考

相关问题

热门标签

最新问答