8001. Fibonacci sum [FIBOSUM] - NZEC

[kokosek]

Hi.
I am not good at Python and I use it only when I have to deal with bignums and PHP get TLE.
This is one of such tasks. I wrote a program in PHP and got TLE. Then I tried in Python and received NZEC.
That's my code:
[bbone=PYTHON,81]exec"
a,b=map(int,raw_input().split());
x=1.61803398875**(b+2.0)/2.2360679775+1;
y=1.61803398875**(a+1.0)/2.2360679775+1;
print int(round((x-y)%1000000007));
"*input()[/bbone]
// Code submitted without endln's.
I would be grateful for any help.
// On ideone of course all correct.

[hendrik]

If you are not good in Python choose a different language. I believe this can be solved with almost all languages. The way you have chosen is possibly the worst you could do and will never be successfull. Sorry, but you should avoid looking too often at the SHORTEN solutions.

[numerix]

On ideone of course all correct.

Look at the constraints! Your "solution" doesn't even work for any a,b > 1473.

[bbone=Python,82]>>> 1.61803398875**1475
Traceback (most recent call last):
File "", line 1, in
OverflowError: (34, 'Numerical result out of range')[/bbone]

As hendrik said: You need another approach. And: Try to write "readable Python", not "short Python".

[kokosek]

I didn't realised that that code is so unreadable. Sorry.
So what's the limit of Python's big numbers?
I thought that 2**1500 is nothing for Python as I solved task POTEGA on pl.spoj.pl where I should print a**b where a,b<1001.
Why in that case I can't power these numbers?

[numerix]

Python's "bignum" in fact is "bigint" and there is indeed no limit except runtime and memory. As the base of your power is a float, the result is calculated using floats with the usual limitations. Python has a builtin module called "decimal" that allows calculations with arbitrary exactness, but according to SPOJ problems it is in nearly all cases unusable because of its slowness. (If I remember right, there is only one of the SPOJ problems that I solved so far, where I really needed that module)

But even if the base were an integer. Just execute the following on your local machine to get an idea of the runtime ...
[bbone=Python,83]for k in range(10**9-1000, 10**9): 3**k[/bbone]

[kokosek]

And I naively thought that I have fast O(t) algorithm...