6
$\begingroup$

I was researching the topic of Fibonacci numbers and asymptotic complexity of generating them. Coming across a seemingly paradoxical conclusion, I've decided to check out if you agree with my explanation.

  1. The naive algorithms runs in $O(n)$, if we ignore the cost of addition.

  2. The Binet's formula or matrix exponentiation method should both theoretically run in $O(\lg(n))$ (since exponentiation of both matrices and real numbers takes $O(\lg(n))$ steps)

The problem arises when you analyze the size of Nth Fibonacci number by assuming that after first few members of the sequence, the ratio between two numbers is at least 1.5 (picked randomly, I assume it can be easily proved by induction).

We can then bound the number to be at least as big as: $c_1*(1.5)^n$. Its logarithm gives us the number of digits the Nth Fibonacci number has ($c_2*n$). Am I right to assume that you can't print out (or calculate) linear number of digits in sublinear time?

My explanation of this "paradox" is that I forgot to add multiplication costs in 2nd algorithm (Binet/matrix), making its complexity $n*\lg(n)$. I've found out that naive algorithm (1st) runs better for very small inputs, and 2nd algorithm runs better for bigger ones (python3).

Is my explanation of complexity correct, and should the naive algorithm get better running time at even larger inputs ($n>10^9$ or such)?

I do not consider this to be a duplicate question, since it adresses the problem of arbitary values and arbitary integer aritmetic.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Welcome to CS.SE! Take a look at en.wikipedia.org/wiki/Model_of_computation#Uses, cs.stackexchange.com/q/1643/755, cs.stackexchange.com/q/32736/755, cs.stackexchange.com/q/33918/755. $\endgroup$
    – D.W. ♦
    Commented Aug 8, 2016 at 16:37
  • 2
    $\begingroup$ The titular question seems to be a duplicate; community votes, please. $\endgroup$
    – Raphael
    Commented Aug 8, 2016 at 18:57
  • 1
    $\begingroup$ @PetarMihalj If you only consider fixed size integers computing any function is O(1) because you have only a finite number of possible inputs. By the way: you mention that you are using python. Well python integers can get unbounded in size and the multiplication uses Karatsuba for big operands. $\endgroup$
    – Bakuriu
    Commented Aug 8, 2016 at 21:05
  • 1
    $\begingroup$ The ratio between successive Fibonacci numbers tends to the golden ratio, which is about $1.618 > 1.5$. $\endgroup$
    – David Richerby
    Commented Aug 8, 2016 at 22:52
  • 2
    $\begingroup$ @PetarMihalj I was confirming that 1.5 is a valid lower bound! $\endgroup$
    – David Richerby
    Commented Aug 8, 2016 at 23:52

2 Answers 2

Reset to default
10
$\begingroup$

Let's assume that you could store such large Fibonacci numbers. In that case, the length of $n^{th}$ Fibonacci number is $\lfloor n \log_{10}\phi+1\rfloor$. That is the length of the $n^{th}$ Fibonacci number is $\Theta(n)$.

If you go by the naive method, then calculating the $n^{th}$ Fibonacci number would cost you $\Theta(n^2)$ time.

In comparison, matrix exponentiation will take $O(n^2\log n)$ time, assuming you use schoolbook long multiplication to multiply numbers. (A slightly more refined analysis shows that it is in fact $\Theta(n^2)$, by summing a geometric series.) But if instead we use Karatsuba multiplication , the running time to compute the $n$th Fibonacci number using matrix exponentiation becomes $O(n^{1.585}\log n)$. (Analogous to before, a slightly more refined analysis shows that the running time is in fact $\Theta(n^{1.585})$.) Thus, if you use sophisticated multiplication algorithms, matrix exponentiation would be better for large $n$ compared to the naive algorithm.

In short: which method is better depends on which multiplication algorithm used.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ And, of course, multiplication can be solved in arbitrary superlinear time, so you can get this down to $\Theta(n^{1 + \varepsilon})$ for any $\varepsilon > 0$ you fancy. $\endgroup$
    – wchargin
    Commented Aug 9, 2016 at 6:47
  • $\begingroup$ @wchargin Do you mind linking some articles about it? $\endgroup$
    – Petar Mihalj
    Commented Aug 9, 2016 at 9:51
  • $\begingroup$ @PetarMihalj Basically, Karatsuba's algorithm breaks its inputs into four chunks, does only three recursive calls instead of four, and thus becomes $n^{\log_2{3}}$. If you chop your inputs into three chunks, and do only five recursive calls instead of nine, you get $n^{\log_3{5}}$. With more and more chunks, you approach unity. For more, see: en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication, or The Nature of Computation section 2.3. $\endgroup$
    – wchargin
    Commented Aug 11, 2016 at 3:07
-1
$\begingroup$

This formula (from wikipedia) may be much faster, depending on how you manage floating point and exponentiate. The first term dominates.

$$ F_n = \frac1{\sqrt{5}}\cdot\left(\frac{1+\sqrt{5}}2\right)^n - \frac1{\sqrt{5}}\cdot\left(\frac{1-\sqrt{5}}2\right)^n\,.$$

(From Wikipedia.)

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ Hint: Don't use floating point, do your calculations in the field $\mathbb{Q}\left[\sqrt{5}\right]$. $\endgroup$
    – Pseudonym ♦
    Commented Aug 9, 2016 at 1:38
  • $\begingroup$ @Pseudonym: Would you mind explaining the notation? I don't know what Q[5] means even though I know what Q, [5], and Field mean separately. $\endgroup$
    – user541686
    Commented Aug 9, 2016 at 4:51
  • $\begingroup$ @Mehrdad $\mathbb{Q}[X]$ is the ring of polynomials in terms of $X$ with coefficients in $\mathbb{Q}$. $\mathbb{Q}[\sqrt{5}]$ is the set of numbers that are a result of these polynomials evaluated at $X=\sqrt{5}$. You essentially end up with $\mathbb{Q}[\sqrt{5}] = \{a+b\sqrt{5}\ |\ a,b \in \mathbb{Q} \}$. Instead of converting to floating point and losing precision, it suffices to store the values $a$ and $b$. $\endgroup$
    – mdxn
    Commented Aug 9, 2016 at 5:12
  • 2
    $\begingroup$ This answer is not a good idea. If you use regular floating point arithmetic for this, you will get incorrect answers when $n$ is large, because regular floating point arithmetic doesn't have enough precision. If you use fixed-point arithmetic with just the right precision, then (contrary to what you claim) the running time will be no faster than the matrix-based methods... plus you have extra headaches to deal with, to try to figure out how many digits of precision are needed for all intermediate results. Not a good approach. $\endgroup$
    – D.W. ♦
    Commented Aug 9, 2016 at 6:55
  • 2
    $\begingroup$ Well, you can't get the exact number in time better than O (n) because the result is O (n) digits. This formula gives you a very fast approximation. It's an excellent idea if you want an approximation. $\endgroup$
    – gnasher729
    Commented Aug 9, 2016 at 10:56

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.