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.

$\endgroup$
  • 1
  • 2
    $\begingroup$ The titular question seems to be a duplicate; community votes, please. $\endgroup$ – Raphael Aug 8 '16 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 Aug 8 '16 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 Aug 8 '16 at 22:52
  • 2
    $\begingroup$ @PetarMihalj I was confirming that 1.5 is a valid lower bound! $\endgroup$ – David Richerby Aug 8 '16 at 23:52
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.

$\endgroup$
  • 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 Aug 9 '16 at 6:47
  • $\begingroup$ @wchargin Do you mind linking some articles about it? $\endgroup$ – Petar Mihalj Aug 9 '16 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 Aug 11 '16 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.)

$\endgroup$
  • 2
    $\begingroup$ Hint: Don't use floating point, do your calculations in the field $\mathbb{Q}\left[\sqrt{5}\right]$. $\endgroup$ – Pseudonym Aug 9 '16 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$ – Mehrdad Aug 9 '16 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 Aug 9 '16 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. Aug 9 '16 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 Aug 9 '16 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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