search

matgrioni / euler-cpp

A solution suite for euler.
0 stars 0 forks source link

Find Constant Time Solution For Problem 2 #4

Open matgrioni opened 1 year ago

matgrioni commented 1 year ago

After some mild poking around to get an idea of any further improvements on the current solution for two, I realized that the Fibonacci sequence has a closed form for the sum of the first N numbers and probably any recurrence relation does. I also saw on the provided overview for problem (2), that the even numbers themselves are a recurrence relation, so it seems that this could be solved very easily in constant time, since it is known how to find the Nth Fibonacci number, (although I would like to prove that once again to myself and relearn how to do this).

matgrioni commented 1 year ago

It seems like there isn't really any constant time solution, because to compute the nth fibonacci number using Binet's Algorithm, actually is not constant time since it required arbitrary precision floating point computations at some point (whereupon arbitrary precision integer arithmetic wins).