bigger fib

aurora · Post by **aurora** » Tue Feb 10, 2009 10:26 pm

hello,

would just like to ask, if actually someone calculated the bigger fib -- the 150000000th member of the fibonacci sequence? gnu bc is running 30 hours now. would like to know, if it's better to stop or if i have to wait some more days to get a result from it

thanks,

MagneticMonopole · Post by **MagneticMonopole** » Tue Feb 10, 2009 10:43 pm

Suggest you stop it.
Read the challenge again. It does not ask for the fibonacci number itself.

megabreit · Post by **megabreit** » Wed Feb 11, 2009 12:31 am

Hm... I thought there has to be some math trick. But I was to lazy to search.

I found a quite fast algorithm that calculated the number in about a week... bc is substantially slower in comarision!
Now I'm waiting for the calculation of the logarithm. Hopefully it does not take longer than the fib calculation.

If I had known that it takes that long, I'd searched longer for an alternate algorithm...
On the other hand: The server is there and has (mostly) nothing else to do so why don't let it calculate things...

teebee · Post by **teebee** » Wed Feb 11, 2009 1:46 am

Hm... I computed the fibonacci number within 9 minutes on a 600MHz CPU. The logarithm was computed within 1.5 seconds. Obviously, I had the right touch with the choice of my tools.

aurora · Post by **aurora** » Wed Feb 11, 2009 2:07 pm

thanks for the hints. i searched a little longer and found a better tool for calculating the fib. it took a very short time now. but now the problem is the log. there must really be some math trick, to solve it -- but i could not figure out how it works, yet

...

cyberwoozle · Post by **cyberwoozle** » Wed Feb 11, 2009 3:36 pm

It's only math - you don't need any other tool than the Windows calculator.

megabreit · Post by **megabreit** » Fri Feb 20, 2009 7:08 pm

I'm sorry if I motivated somebody to calculate fib and the logarithm manually... at least if you don't have teebee's tools. I did not have them, and stopped calculations after 2 weeks on a dedicated server. Being lazy is not very efficient with this challenge.
After 20 min Google and remembering some school math it was no problem calculating the result.

There is a second motivation: You surely won't brute-force the following challenge "Biggest Fib"

teebee · Post by **teebee** » Sat Feb 21, 2009 12:13 am

megabreit wrote:There is a second motivation: You surely won't brute-force the following challenge "Biggest Fib"

You are definitely right. There my tools would fail too - I did not even try to solve "Biggest Fib" using them.

m!nus · Post by **m!nus** » Sun Feb 22, 2009 4:46 am

*snip* seems to be a bad habit of mine to post solutions...

cyberwoozle · Post by **cyberwoozle** » Sun Feb 22, 2009 10:52 am

Ehemmm......., i would delete the last one from the forum, 'cuz this is the solution - with a slight modification it prints the solution. If it doesn't work on your PC, it's only possible, that you made a mistake in copying and pasting it to the answer field.

I had to modify your solution for python, not becasue there's a mistake in it .

DaymItzJack · Post by **DaymItzJack** » Thu Nov 19, 2009 9:32 pm

Can someone who has completely this message me? I think my method should be correct but I am getting the wrong answers and it's driving me crazy.

crstnbr · Post by **crstnbr** » Wed Dec 23, 2009 2:06 am

Can anybody give me a hint for the "Biggest Fib" Challenge. I could calculate the Bigger Fib but, 150000000000000 is too huge

i googled for something like a exponential approximation of the fibbonacci numbers. i hoped to find a way to use some log and exp transformation rules to make the challenge easier to solve, but i had no success so far. So a hint would be nice. Maybe someone could tell me if i'm on the right track with the mathematic research.

thanks
crstnbr

CodeX · Post by **CodeX** » Wed Dec 23, 2009 2:28 am

It sounds like your looking for a closed expression way of calculating numbers in the Fibonacci sequence... maybe looking at the Wikipedia article would help

tripleedged · Post by **tripleedged** » Wed Nov 10, 2010 3:13 pm

I got stuck on this, too... (Bigger Fib)

I think I have done the right calculation, but it tell me I'm false.

Does the correct number have the same two digits at the beginning and right before the decimal point?
(like 72xxxxxxxx72.xxxxx)

Don't want to spoil something, but I may have a problem with rounded numbers. The error might get quite large...

Mon Jun 20, 2011 2:55 pm

CodeX wrote:It sounds like your looking for a closed expression way of calculating numbers in the Fibonacci sequence...

Sounds like a good idea. So the formula is:

Fn = (phi ^ n - psi ^ n )/ sqrt(5), where phi = (1+sqrt(5))/2 and psi = (1-sqrt(5))/2

Now to rewrite the equation:

Fn * sqrt(5) = phi ^ n - psi ^ n

log (Fn * sqrt(5)) = log(phi ^ n - psi ^ n)

log Fn + 1/2 log 5 = log(phi ^ n - psi ^ n)

My problem here is that there is no algebraic formula for the logarithm of a difference

I seem to be unable to get the pesky n away from the exponent, and that is exactly what you want to do if you don't want to multiply 150000000 times, is it not? Or am I missing something here? Any hint would be appreciated.