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.

-QM
--
Quantum Mechanics: The dreams stuff is made of

In reply to Re^2: OT: Finding Factor Closest To Square Root by QM
in thread OT: Finding Factor Closest To Square Root by QM

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.