我能做些什么来改进我的斐波那契数生成器?

I'm solving this problem:

我解决这个问题:

G(n) is defined as

G(n) = G(n-1) + f(4n-1) , for n > 0

and G(0) = 0

f(i) is ith Fibonacci number. Given n you need to evaluate G(n)

modulo 1000000007.

模1000000007。

Input

First line contains number of test cases t (t<40000). Each of the next t

lines contain an integer n ( 0 <= n < 2^51).

行包含一个整数n(0 < = n < 2 ^ 51)。

Output

For each test case print G(n) modulo 1000000007.

Example

Input:
2
2
4



Output:


15
714

This is the code I've written:

这是我写的代码:

typedef long long type;
#define check 1000000007
type x;
type y;

type f(type n)
{
    return(ceil((pow(1.618,n) - pow(-0.618,n))/((sqrt(5)*1.0))));
}
type val(type n)
{
    if(n==0)
    return 0;
    else 
    return (val(n-1)+f(4*n-1));
}
int main()
{
    cin>>x;
    while(x--)
    {
       cin>>y;
       cout<<val(y)%check<<endl;
       }
    //getch();
    return 0;
}

Can you suggest any improvements?

你能提出一些改进建议吗?

4 个解决方案

#1

Sometimes such problems can be tackled with mathematical tricks,
instead of brute force solutions.

有时，这些问题可以用数学技巧来解决，而不是用蛮力解决方法。

The large value of n and modulo, in my opinion, are indications that
a clever solution exists. Of course figuring out the solution is the hard part.

在我看来，n和modulo的巨大值表明存在一个聪明的解决方案。当然，找出解决方案是最困难的。

(I'm not sure if this is ideal in your case, I'm only pointing you an alternative way)

(我不确定这是否适合你，我只是用另一种方式给你指出)

For example, in the Art of Computer Programming, Volume 1: Fundamental Algorithms
Knuth uses "generating functions", a clever way for constructing a closed form
for the Fn fibonacci number.

例如，在计算机编程的艺术中，第1卷:基本算法Knuth使用“生成函数”，这是为Fn斐波那契数构造一个闭合形式的一种聪明的方法。

For more info read Generating Functions (pdf)

有关更多信息读取生成功能(pdf)

Why should one care about the generating function for a sequence? There are several answers, but here is one: if we can ﬁnd a generating function for a sequence, then we can often ﬁnd a closed form for the nth coefﬁcient— which can be pretty useful! For example, a closed form for the coefﬁcient of xⁿ in the power series for x/(1−x−x²) would be an explicit formula for the nth Fibonacci number. [...]

为什么要关心序列的生成函数?有几个答案，但这里有一个:如果我们能找到一个序列的生成函数，那么我们通常可以找到一个闭合形式的第n个系数，这是非常有用的!例如,一个封闭的形式幂级数的系数xn x / x(1−−x2)将是一个明确的第n个斐波纳契数的公式。[…]

#2

G(n) = G(n-1) + f(4n-1) = G(n-2) + f(4n-1) + f(4n-5) etc.

G(n)= G(n - 1)+ f(n - 1)= G(n - 2)+(4 n - 1)+ f(4存在)等。

therefore

因此

G(n) = f(4n-1) + f(4n-5) + f(4n-9) ... f(3)

G(n) = f(4n-1) + f(4n-5) + f(4n-9)…f(3)

f(n) = f(n-1) + f(n-2) = 2f(n-2) + f(n-3) = 3f(n-3) + 2f(n-4) = 5f(n-4) + 3f(n-5) f(n-5) = 3f(n-8) + 2f(n-9) thus f(n) = 5f(n-4) + 9f(n-8) + 6f(n-9) = 5f(n-4) + 9f(n-8) + 18f(n-12) + 12f(n-13)

f(n)= f(n - 1)+ f(n - 2)= 2(n - 2)+ f(n)= 3 f(n)+ 2(4)= 5 f(4)+ 3(存在)f(存在)= 3 f(n-8)+ 2 f(n - 9)因此f(n)= 5(4)+ 9 f(n-8)+ 6 f(n - 9)= 5 f(4)+ 9(n-8)+ 18 f(n-12)+ 12 f(n-13)

= 5f(n-4) + 9f(n-8) + 18f(n-12) + 36f(n-16) + 24f(n-17)

= 5 f(4)+ 9(n-8)+ 18 f(n-12)+ 36 f(n-16)+ 24 f(n-17)

in any case it is clear the coefficients will double each time. Of course from the above we can define f(n-4) in terms of f(n-8) etc. Not sure where this will lead.

在任何情况下，每个时间的系数都将加倍。当然，从上面我们可以定义f(n-4)的f(n-8)等，不确定这将会导致什么。

There is a series here and f(3)=2 and f(2) = 1 so at the end you will add the constant.

这里有一个级数，f(3)=2和f(2) = 1所以最后你要加上这个常数。

Practically though for your purpose you can calculate f(n) in a single pass without having to store more than 2 of them at this point and as you know the formula for G above, as you pass through calculating f(n) you can update G as appropriate summing the fibonnaci numbers when n is congruent to 3 mod 4 at each point.

实际上尽管你的目的你可以计算f(n)在一个通过无需存储超过2人在这一点上你知道G以上的公式,通过计算f(n)你可以适当更新G求和fibonnaci数字当n是相等的3国防部4每一点。

You will not find the space to save a table with such a huge number (2 to the power of 51) not even to disk, though it is really the sums you need to store in a table (f(3), f(3)+f(7), f(3)+f(7)+f(11) etc.) if you were going to save anything.

如果你想要保存任何东西，你将不会找到一个空间来保存一个如此巨大的数字(2的51次方)甚至磁盘的空间，尽管它实际上是你需要存储在一个表中的金额(f(3)， f(3)+f(7)， f(3)+f(7)+f(11)等等)。

#3

So f() is the fibonacci function? I would suggest that you use the regular recursive algorithm. But you can improve performance significantly by adding a cache, as calls to f(i) for smaller values of i will be repeated very often.

f()是斐波那契函数?我建议你使用规则递归算法。但是您可以通过添加缓存来显著提高性能，因为对于较小值的调用(i)会经常重复。

You can do that by using a static local array of integers. If the element is 0 it's a miss so you calculate the value and store it in the array.

您可以通过使用一个静态的本地整数数组来实现这一点。如果元素为0，那么它就是一个miss，所以您计算值并将其存储在数组中。

That way you avoid using floating point operations and you won't fill up the stack.

这样可以避免使用浮点运算，也不会填充堆栈。

#4

I think the better way to get value of G(n) is to compute it like this:

我认为得到G(n)的更好的方法是像这样计算

type val(type n, std::vector<type> &fib)
{
  type ret = 0, s = min(type(fib.size()), n);
  for(type i=0; i < s; ++i)
      ret += fib[i];

  if(n > fib.size()){    
    fib.reserve(n);
    int tmp;
    for(type i = fib.size(); i < n; ++i){
      tmp = f(4*i+3);
      fib.push_back(tmp);
      ret += tmp;
    }

  }
  return ret;
}

(For whole code check http://www.ideone.com/jorMy)

(用于整个代码检查http://www.ideone.com/jorMy)

Avoid recursion everywhere it's possible and this way it won't compute everytime Fibonacci function.

避免在任何可能的地方递归，这样它就不会计算每一个Fibonacci函数。

Edit: I've spent much time to find that (my math is little rusty), but you can also write val like this:

编辑:我花了很多时间来发现(我的数学有点荒废)，但你也可以这样写:

numtype val(numtype n) {
  return ceil(2.218*pow(6.8541,n-1) - 0.018*pow(0.145898,n-1) - 0.2);
}

(code on http://www.ideone.com/H1SYz)

(代码在http://www.ideone.com/H1SYz上)

This is closed form of your sum. If you want to find it by yourself (it's homework after all) follow Nick D answer.

这是你的和的闭合形式。如果你想自己找到它(毕竟是家庭作业)，请跟随尼克·D的回答。

#1