更快地生成递归序列（类似于 Fibonacci）

Question

你好必须计算一个级数的 n 项，n 真的很大，而且必须尽可能快地完成。

该系列由以下函数定义：

f(0) = 1
f(1) = 1
f(2n) = f(n)
f(2n+1) = f(n) + f(n-1)

我知道我必须使用记忆。我做了这段代码，但问题是大 n 值会导致分段错误。我想尝试做一个 2 值数组版本（就像其中一个响应 here 中描述的那样），但我没有找到正确的解决方案。

uint64_t f(uint64_t n)
{
    uint64_t a[n+2];
    uint64_t i;

    a[0] = 1;
    a[1] = 1;
 
    for(i = 2; i <= n; i++)
    {
        if (i % 2 == 0)
        { 
            a[i] =  a[i / 2];
        }
        else
        {
            a[i] =  a[i / 2] + a[(i / 2) - 1];
        }
    }
    return a[n];
};

Answer 1

我认为递归在这里是正确的想法，因为您只需要最后一个值，而它实际上并不依赖于那么多先前值。最好的情况是，如果您的输入是 2 的幂，比如 2^n。那么你只需要 n 个输入的值。虽然在其他情况下性能更差，但它仍然比实际计算所有前面的值要好得多。

编辑：使用评论中要求的具体数量和一个计数器变量来显示所需的评估数量：

编辑2：当然，将递归与缓存中间结果结合起来是可能的（并且是真正的性能提升！），正如@Bob__ 在他下面的评论中所展示的那样，谢谢！对于未来的读者，这里是带有递归+缓存的完整版本。对于给定的输入，缓存将 g 所需的评估次数从无缓存的 12875760616 显着减少到有缓存的 164。

#include <iostream>
#include <map>
#include <stdexcept>

static unsigned long count = 0;
static std::map<unsigned long, unsigned long> cache;

static unsigned long g(unsigned long n) {
  auto it = cache.find(n);
  if (it != cache.end()) {
    return it->second;
  }

  ++count;
  if (count == 0) {
    std::cout << "Integer overflow! Aborting!";
    throw std::overflow_error("overflow error!");
  }

  if (n == 0 or n == 1) {
    return 1;
  } else if (n % 2 == 0) {
    auto a = g(n / 2);
    cache.insert({n, a});
    return a;
  } else {
    auto a = g((n - 1) / 2) + g((n - 3) / 2);
    cache.insert({n, a});
    return a;
  }
}

int main() {
  try {
    std::cout << "result: " << g(123456789012345678) << std::endl;
    std::cout << "number of used values: " << count << std::endl;
  } catch (std::exception &e) {
    std::cout << "An error occured:\n" << e.what() << std::endl;
  }
}

Answer 2

我们可以一次考虑两组四个值来扩展发布的递归关系。

$\colorbox{white}{\begin{bmatrix}F_{2n}\F_{2n+1}\F_{2n+2}\F_{2n+3}\end{bmatrix} = \begin{bmatrix}F_{n}\F_{n-1} + F_n\F_{n+1}\F_n+F_{n+1}\end{bmatrix} = \begin{cases}\begin{bmatrix}0 & 1 & 0 & 0\ 1 & 1 & 0 & 0\ 0 & 0 & 1 & 0\ 0 & 1 & 1 & 0\end{bmatrix}\begin{bmatrix}F_{n-1}\F_{n}\F_{n+1}\ {\textcolor{gray}{F_{n+2}}}\end{bmatrix} & n = 2k + 1\&\begin{bmatrix}0 & 0 & 1 & 0\ 0 & 1 & 1 & 0\ 0 & 0 & 0 & 1\ 0 & 0 & 1 & 1\end{bmatrix}\begin{bmatrix}{\textcolor{gray}{F_{n-2}}}\F_{n-1}\F_{n}\F_{n+1}\end{bmatrix} & n = 2k\end{cases}}$

请注意，这些集合的第一个元素始终处于偶数位置（2n，当 n = 2k+1 时为 n-1 或当 n = 2k 时为 n-2）并且每个集合中只有三个元素低位实际参与计算

从给定的 N 开始，我们要为其计算 F_N，我们可以找到一个递减值序列 n_i表示这些位置，p_i 表示要使用的变换。

n₀ = N - N mod 4

h_i = n_i / 2
p_i = h_i mod 2
n_i+1 = h_i + p_i - 2

然后我们只需要将前面的变换连续应用到向量{F₀, F₁, F₂, F₃} = {1, 1, 1, 2} 我们可以在 O( logN).

以下是一种可能的实现方式

unsigned long long f(unsigned long long n)
{
    unsigned long long F[] = {
        1, 1, 1, 2
    };
    auto idx = n % 4;
    auto pos = n - idx;
    unsigned long long journal{};
    int count{};
    while ( pos )
    {
        auto n = pos / 2;
        journal <<= 1;
        journal |= n % 2;
        pos = n + n % 2 - 2;
        ++count;
    }
    while ( count-- )
    {
        if ( journal & 1u )
        {
            unsigned long long tmp = F[1];
            F[1] += F[0];
            F[0] = tmp;
            F[3] = F[2] + tmp;
        }
        else
        {
            unsigned long long tmp = F[2];
            F[0] = tmp;
            F[1] += tmp;
            F[2] = F[3];
            F[3] += tmp;
        }
        journal >>= 1;
    }
    return F[idx];
}

可测试here。

更快地生成递归序列（类似于 Fibonacci）

Generate a recursive series faster (similar to Fibonacci)

c++

series

fibonacci