Bigger Fib

dotme · Post by **dotme** » Sun Dec 07, 2008 7:56 pm

That was fun.

While solving "Big Fib" with bc driven by a perl-script and using the dijkstra-simplification, I realized that getting the solution for this challenge would take more time and cycles than I want to spent on it.

So, I changed to C with GMP and was really thrilled by the speed of GMP in computing fib members (damn, should have known that before

) . But GMP lacks ln() so I spent some extra time to bring in MPFR.

.done! (phewww)

brazzy · Post by **brazzy** » Mon Dec 08, 2008 9:48 pm

You know, a little bit of pretty basic applied math knowledge makes this (and BiggestFib as well) solvable without any fancy libraries in 2 or 3 lines of code and a very small fraction of a second.

homeas · Post by **homeas** » Sun Dec 28, 2008 9:44 pm

with a little bit knowledge of "sectio aurea" you don't need any coding at all, just the Windows calculator and you'll find the solution manually in only some seconds ...

rmplpmpl · Post by **rmplpmpl** » Thu Jan 01, 2009 10:56 pm

Phew, finally solved that one... after I got the BigFib I really was shocked by the BiggerFib challenge, a short attempt to calculate this number (w/o thinking about the ln-part too much) led me to the point that this is simply senseless...

It was not until half an hour ago that I read about ways to calculate big f(n) and to recap the laws of logarithmics.

Now on to the biggest fib

EDIT: OK, biggest is not really harder than bigger...

gfoot · Post by **gfoot** » Fri Jan 02, 2009 2:18 am

rmplpmpl wrote:EDIT: OK, biggest is not really harder than bigger...

Except in the sense that "bigger" is fully calculable in a vaguely reasonable time period (a few days, for me) - it wasn't until "biggest" that I took the more efficient approach.

blablaSTX · Post by **blablaSTX** » Tue Aug 25, 2009 1:29 pm

sometimes it helps to "think" before starting to hack in some code !
compuation is done in a few milliseconds if done right.

quangntenemy · Post by **quangntenemy** » Sun Aug 30, 2009 5:33 am

Well the ln part makes it easier than expected

Millennium · Post by **Millennium** » Wed May 18, 2011 11:29 am

XD I did it in one line

print(150000000*log(1.61803398874989484820458683436563811772030917980576286213544862270526046281890244970720720418939113748475408807538689175212663386222353693179318006076672635443)-.5*log(5))

Which is a way of writing

x*log(phi)-.5*log(5)

moose · Post by **moose** » Wed Jul 27, 2011 11:23 am

Wolfram|Alpha did it.

Has anyone solved it with Python? Could you please post your solution? Or any C++ approach? (I would like to learn C++ and I appreciate reading examples)

laz0r · Post by **laz0r** » Wed Jul 27, 2011 2:04 pm

moose wrote:Wolfram|Alpha did it.

Has anyone solved it with Python? Could you please post your solution? Or any C++ approach? (I would like to learn C++ and I appreciate reading examples)

I think most of us probably used the formula for the nth Fibonacci number, ending up with:
-(Log[5]/2) + Log[-(2/(1 + Sqrt[5]))^n + (1/2 (1 + Sqrt[5]))^n]
(WolframAlpha will show this in a nice format).
Then noting that the -(2/(1+Sqrt[5]))^n term will become very close to 0 as n increases, so we end up with:
-(Log[5]/2) + n Log[(1/2 (1 + Sqrt[5]))]
which is very easy to find.

Hippo · Post by **Hippo** » Tue Apr 01, 2014 8:08 pm

If I remember well, I had opened excell when I came to these 2 challenges. So I have multiplyed and subtracted the logarithms there...