3 ms·

Good example of this: What is the complexity of the fastest algorithm that prints the nth Fibonacci number? Novice: "O(n), because you have to iterate from 0..

Good example of this: What is the complexity of the fastest algorithm that prints the nth Fibonacci number? Novice: "O(n), because you have to iterate from 0..n." Expert: "O(log n), because we can use matrix exponentiation." Master: "O(n), because F(n) has O(n) digits to print!"

thomasahle 5y ago
The Master's argument would imply Ω(n) time, The matrix exponentiation algorithm would take O(nlogn) time, since you have to multiply large numbers, and this takes nlogn with the best known algorithms (FFT). I don't think there are any O(n) algorithms.
- ChrisLomont 5y ago
  There are closed forms for F(n), and even faster ways to get it without needing to compute the sequence. You're conflating n power with requiring n digit multiplications. This isn't true. The size of needed numbers is smaller for most problems of this type. And special structure is likely exploitable. A simple proof is to write the recurrence as a matrix, take powers, diagonalize and read off the result. If I recall, the answer is something like F(n) is ((1+sqrt5)/2)^n + ((1-sqrt5)/2)^n. Then you can only compute part of the first term, the second is small. Then use the bits of n similar to power mod to compute powers in log n steps. You only need something like log n precision along the way. This should reach O(n) easily, perhaps below. Quick check shows O(log n) steps in standard constant time ops.
  - jepler 5y ago
    gmp uses a particular recurrence relation to exactly compute fib(x) in about log(x) steps[0]. Of course, the digits of the numbers it has to multiply also increase. It's fast-ish up to fib(128 million) or so but soon after that you run into the limit of the size of numbers in gmp, which are limited to being less than 2^31 * 32 bits long or something. [0]: https://gmplib.org/manual/Fibonacci-Numbers-Algorithm https://gmplib.org/manual/Fibonacci-Numbers-Algorithm
  - thomasahle 5y ago
    You seem to be saying that if we don't want to compute F(n), but just some numbers a, e such that F(n) ~ a*10^e, then we can do it faster than nlogn time. That's of course true. However, that's a different problem than actually computing the n digits of F(n). Even computing the first n digits of ((1+sqrt5)/2)^n probably takes nlogn time. You say "use the bits of n similar to power mod". I suppose you mean repeated squaring. But what happens in the last of the logn steps of that procedure?: You multiply two n/2 bit numbers.
    - ChrisLomont 5y ago
      No, I am not saying that. I am saying we can compute F(n) exactly in O(log n) time. All the digits. That Fibonacci identity I posted allows computing exactly every single integer digit by rounding at the end, because the other term goes to zero as n goes to infinity, and that other term is always less than 1. There are papers showing the complexity I claimed is true. For example, [1]. Algorithm 3.7, on page 15, and I quote: "Hence, with constant time arithmetic, the time complexity is O(lg n). The space complexity is also logarithmic in n." It uses the same ideas as the algorithm I suggested. Also the two algorithms in section 3.8 achieve the same. The algorithm in section 11 achieves the same. These use, as I used above, as is common for algorithms, what is called constant time arithmetic. This is how pretty much every textbook you will find uses these terms. Otherwise, even simple things like Quick Sort are no longer O(n log n) in the number of items, because as those items grow without bound, if the arithmetic does also, you end up with (often) more factors of n or log n in your final complexity. For example, here is the bit complexity of quicksort [2], which is O(n log n log n) instead of the usual O(n log n). This concept is used so rarely that I don't think I've ever heard another person state it. People state the O(n log n) complexity, which is the standard for constant time arithmetic. >You multiply two n/2 bit numbers. You keep mixing your ideas for complexity. To specify the problem for computing F(n) you need not n bits - you need log n bits. So the input for this problem is not n, it is log n. Thus if you take your claim, and at the end multiply two (log n)/2 sized numbers, what do you get? For example, if I tell you that you should compute F(1024), you do not need 1024 bits to tell you that. You need 10 = log 1024 bits to specify the problem. To describe the input to compute F(1,000,000) you do not need 1 million bits. You need 20. Thus you do not multiply out n/2 bit numbers at the last step. [1] https://arxiv.org/pdf/1803.07199.pdf https://arxiv.org/pdf/1803.07199.pdf [2] https://www.ams.jhu.edu/~fill/papers/BitsQuickxabs.pdf https://www.ams.jhu.edu/~fill/papers/BitsQuickxabs.pdf

thomasahle 5y ago

The Master's argument would imply Ω(n) time, The matrix exponentiation algorithm would take O(nlogn) time, since you have to multiply large numbers, and this takes nlogn with the best known algorithms (FFT). I don't think there are any O(n) algorithms.

ChrisLomont 5y ago
There are closed forms for F(n), and even faster ways to get it without needing to compute the sequence. You're conflating n power with requiring n digit multiplications. This isn't true. The size of needed numbers is smaller for most problems of this type. And special structure is likely exploitable. A simple proof is to write the recurrence as a matrix, take powers, diagonalize and read off the result. If I recall, the answer is something like F(n) is ((1+sqrt5)/2)^n + ((1-sqrt5)/2)^n. Then you can only compute part of the first term, the second is small. Then use the bits of n similar to power mod to compute powers in log n steps. You only need something like log n precision along the way. This should reach O(n) easily, perhaps below. Quick check shows O(log n) steps in standard constant time ops.
- jepler 5y ago
  gmp uses a particular recurrence relation to exactly compute fib(x) in about log(x) steps[0]. Of course, the digits of the numbers it has to multiply also increase. It's fast-ish up to fib(128 million) or so but soon after that you run into the limit of the size of numbers in gmp, which are limited to being less than 2^31 * 32 bits long or something. [0]: https://gmplib.org/manual/Fibonacci-Numbers-Algorithm https://gmplib.org/manual/Fibonacci-Numbers-Algorithm
- thomasahle 5y ago
  You seem to be saying that if we don't want to compute F(n), but just some numbers a, e such that F(n) ~ a*10^e, then we can do it faster than nlogn time. That's of course true. However, that's a different problem than actually computing the n digits of F(n). Even computing the first n digits of ((1+sqrt5)/2)^n probably takes nlogn time. You say "use the bits of n similar to power mod". I suppose you mean repeated squaring. But what happens in the last of the logn steps of that procedure?: You multiply two n/2 bit numbers.
  - ChrisLomont 5y ago
    No, I am not saying that. I am saying we can compute F(n) exactly in O(log n) time. All the digits. That Fibonacci identity I posted allows computing exactly every single integer digit by rounding at the end, because the other term goes to zero as n goes to infinity, and that other term is always less than 1. There are papers showing the complexity I claimed is true. For example, [1]. Algorithm 3.7, on page 15, and I quote: "Hence, with constant time arithmetic, the time complexity is O(lg n). The space complexity is also logarithmic in n." It uses the same ideas as the algorithm I suggested. Also the two algorithms in section 3.8 achieve the same. The algorithm in section 11 achieves the same. These use, as I used above, as is common for algorithms, what is called constant time arithmetic. This is how pretty much every textbook you will find uses these terms. Otherwise, even simple things like Quick Sort are no longer O(n log n) in the number of items, because as those items grow without bound, if the arithmetic does also, you end up with (often) more factors of n or log n in your final complexity. For example, here is the bit complexity of quicksort [2], which is O(n log n log n) instead of the usual O(n log n). This concept is used so rarely that I don't think I've ever heard another person state it. People state the O(n log n) complexity, which is the standard for constant time arithmetic. >You multiply two n/2 bit numbers. You keep mixing your ideas for complexity. To specify the problem for computing F(n) you need not n bits - you need log n bits. So the input for this problem is not n, it is log n. Thus if you take your claim, and at the end multiply two (log n)/2 sized numbers, what do you get? For example, if I tell you that you should compute F(1024), you do not need 1024 bits to tell you that. You need 10 = log 1024 bits to specify the problem. To describe the input to compute F(1,000,000) you do not need 1 million bits. You need 20. Thus you do not multiply out n/2 bit numbers at the last step. [1] https://arxiv.org/pdf/1803.07199.pdf https://arxiv.org/pdf/1803.07199.pdf [2] https://www.ams.jhu.edu/~fill/papers/BitsQuickxabs.pdf https://www.ams.jhu.edu/~fill/papers/BitsQuickxabs.pdf