hacker.org

you're nearly there tripleedge and you may not need any rearranging to get the answer

CodeX wrote:and you may not need any rearranging to get the answer

(Note: post edited)

Well, I have solved it now, but I very much had to rearrange the equation of the closed-form expression to get there.

The method without rearranging has quite arbitrary steps, and the precision is very good

But who wants a solution that takes a long time to compute

it took a fraction of a second for me, could even do it online

Well, Wolfram Alpha says "Computation timed out" when entering log(Fibonacci(150000000)) ...

I managed to do it with Wolfram Alpha using using only 3 more characters than that, I guess it takes up a load of time trying to do fancy stuff to the value instead of spitting out a plain old number and so times out before getting there unless it's prompted to do so first. Putting that into Mathematica does take a long time though (aborted after a few seconds) but it works nearly instantly when given the closed form so I guess it uses a series function

I'm trying to solve this with Python.

Could you please tell me if natLog( Fib(1,500,000) ) = 721816.933? (the sequence has 313,482 digits!)
(I know that the challenge asks for 150,000,000, but I want to take a "small" example to test my programms.)

I used psyco to speed python up. It got about two times faster.

Algorithm #1:

• time for natLog( Fib(1,500,000) ): 1min 19s
• time for natLog( Fib(15,000,000) ): 2h 54 min =>

Algorithm #2:

• time for natLog( Fib(1,500,000) ): 1min 53s
• time for natLog( Fib(15,000,000) ):=>as it seems to be slower than#2, I won't try this

Algorithm #3:

• time for natLog( Fib(1,500,000) ): 2min 12s
• time for natLog( Fib(15,000,000) ):=>also too slow

Hmm ... I guess I can't improve the algorithm that much ...

Ln(Fib(1500000)) = 721816.93287044895420, so you're nearly right...

Actually, he is not nearly right, but completely right, since the answer should be rounded to 3 decimals.

In the meantime I have solved this too... Found quite an easy way to conquer it. Was even solving biggest fib in less than 5 minutes, following the same plan...

Nice challenge. My first program couldn't handle the massive number, so after searching for a long time I found something amazing that can find fib in 8 seconds! Calculating the log took just as long because I just didn't know how for such a big number until I found a nice article that explained how to calculate an approximate value of huge numbers.

It would be interesting to see how to solve this using wolfram alpha too!

Yes, it helps to know something from linear algebra.
Matrix multiplication is good close form.
Associativity says you can replace multiplication by exponentation, which can be speeded up by associativity again reusing the same subresults (powers of 2...).
Eigen values gave nice base for another close form, but as they contain square roots, this close form is impractical for exact computation, but is very good for approximations, especially when only logarithm of the result is needed.

[edit]
After reading other posts, I think this could stay here as a hint ... .
And one more hint ... of course when computing approximations, one should do some "roundings" to simplify. It helps to keep in mind which order of magnitude the "rounding" affects.
[/edit]

I spend hours to check my solution until I saw, my program printed a 'comma' instead of a decimal point. (OK, I am a german)
This was not accepted as solution. After changing this, I recognized, my result was right.