Can you tell us, why you need to find that one? May be we can come up with non-exhaustive alternatives.
OK, but I was so enjoying the direction the discussion was going, and I didn't want the thread to lose the focus on the problem I stated. But here goes...
At various times I've been bitten by the Fibonacci bug, like many others. I've tried my hand at programming F(n), as well as some other interesting things like a prime tester .
Poking around on Mathworld, I read the Fibonacci page. One of the formulas is
F(k*n) = L(k)*F(k*(n-1)) - ((-1)**k)*F(k*(n-2))
where
L(k) = F(n-1) + F(n+1)
and substituting
F(k*n) = (F(n-1)+F(n+1))*F(k*(n-1))
- ((-1)**k)*F(k*(n-2))
For computing F(k*n), this is most efficient when k==n, giving
F(n**2) = (F(n-1)+F(n+1))*F(n*(n-1))
- ((-1)**n)*F(n*(n-2))
If N is prime, use
F(2*k+1) = F(k+1)**2 + F(k)**2
As an exercise in programming and improving my grasp of math and computational complexity, I was going to benchmark several methods of computing F(N). Included in this is the standard recursive solution (which is too slow, but we can estimate it's behavior for large N), the closed form using phi, and various identities.
The identity for F(k*n) seemed to be the most promising in this area, though computing sqrt(N), and/or factoring N, would seem to negate any benefits. Perhaps a quick check to see if N has any small factors, otherwise use the F(2*k+1) identity for odd N, or one of the F(2*k) formulas for even N. (There's a nice identity for N % 3 == 0 too.)
Update: fixed missing parens in formulae.
-QM
--
Quantum Mechanics: The dreams stuff is made of
| [reply]
[d/l]
[select] |
Programming F(n) for benchmarking purposes is interesting.
However, the fastest way of all is probably:
F(n)= integer nearest (1/sqrt 5)[(1+sqrt 5)/2]^n
This isn't perl, but it would only take a line. (If n is extremely large, the exponentiation might become inaccurate,
though...)
chas | [reply]
[d/l] |
Programming F(n) for benchmarking purposes is interesting. However, the fastest way of all is probably:
F(n)= integer nearest (1/sqrt 5)[(1+sqrt 5)/2]^n
Yes, but I'd like to understand for myself why various approaches are slower. Which means I have to find a number of independent approaches.
If n is extremely large, the exponentiation might become inaccurate, though.
That's why you use arbitrary precision, like one of the Math::Big* modules.
-QM
--
Quantum Mechanics: The dreams stuff is made of
| [reply]
[d/l] |
