3 ms·

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'

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

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