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))
[download]

where

L(k) = F(n-1) + F(n+1)
[download]

and substituting

F(k*n) = (F(n-1)+F(n+1))*F(k*(n-1)) 
          - ((-1)**k)*F(k*(n-2))
[download]

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))
[download]

If N is prime, use

F(2*k+1) = F(k+1)**2 + F(k)**2
[download]

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.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.