1
$\begingroup$

With efficient I mean of a big O of polynomial time in the number of digits each number has.

$\endgroup$
5
  • 1
    $\begingroup$ Any general number or a prime? Have you seen this? What have you tried so far? $\endgroup$
    – Evil
    Commented Mar 5, 2017 at 22:50
  • $\begingroup$ If you want to find the $n$th fibonacci number, doesn't your time complexity have to depend on $n$ as well? $\endgroup$
    – Riley
    Commented Mar 5, 2017 at 23:22
  • $\begingroup$ If you mean literally what you wrote, then fixing the modulus would mean you'd have to be able to calculate arbitrary Fibonacci numbers in constant time. That can't be possible, since the Fibonacci sequence, even modulo something, isn't eventually constant. $\endgroup$ Commented Mar 5, 2017 at 23:46
  • $\begingroup$ cs.stackexchange.com/q/37571/755, cs.stackexchange.com/q/62401/755 - you can adapt the techniques there to your problem, by just doing all calculatiosn modulo the modulus. $\endgroup$
    – D.W.
    Commented Mar 6, 2017 at 3:45
  • $\begingroup$ It appears you may have created multiple accounts. If so, I encourage you to merge them. This will help you retain the ability to edit your question and comment on answers. $\endgroup$
    – D.W.
    Commented Mar 6, 2017 at 3:46

1 Answer 1

2
$\begingroup$

Here are two suggestions:

The linear algebra approach. It is known that $$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n &F_{n-1} \end{bmatrix}. $$ You can compute the matrix power using repeated squaring, doing all the calculations modulo your modulus.

Closed form. If your modulus is odd and 5 is a quadratic residue (i.e., 5 has a modular square root) then you can use the explicit formula $$ F_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}. $$ You can then use Carmichael's function to reduce $n$, and then repeated squaring. Care must be taken when the modulus isn't a prime power.

It is possible that a similar approach works more generally.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.