What can I do to improve my Fibonacci number gener

问题:

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.

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).

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?

回答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.

(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.

For more info read Generating Functions (pdf)

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

回答2:

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

therefore

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)

= 5f(n-4) + 9f(n-8) + 18f(n-12) + 36f(n-16) + 24f(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.

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

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.

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.

回答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.

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.

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:

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)

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

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)

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