3 ms·

> Technically not correct, because when you get to large numbers you have to take into account that multiplication of those numbers takes O(nlogn) at best. Thi

> Technically not correct, because when you get to large numbers you have to take into account that multiplication of those numbers takes O(nlogn) at best. This seems disingenuous. You could make the same claim about any algorithm that involves multiplication.

hansvm 5y ago
Yes you could. For a fixed-width register machine you can go even further and say that there don't exist non-trivial constant time algorithms (it takes at least logarithmic time to read the entire input). This includes bread-and-butter classics like hashtables. In practice we usually hand-waive those details away because they don't apply on the domain of interest; rarely is somebody meaningfully exceeding a 64-bit space for their hashtables. You can formalize that a bit with something like the "Word RAM" model of computation -- assume that you have fixed width registers as wide as your inputs. For the Fibonacci sequence those details are a little harder to hand-waive away because of how quickly the output grows. As soon as the input is bigger than ~64 on a modern computer you'll start to see the effects of that linear runtime. On most clusters you'd have to stream Fib(1<<64) just to see all the bits, and it'd take ages. The reason that idea doesn't (usually) get applied to algorithms involving multiplication is because usually we're operating implicitly in a model that includes constant-time multiplication of "big enough" numbers. In cryptography and other fields operating on large integers though that analysis absolutely does come into play. The overarching theme is that reality is hard to capture both succinctly and accurately, and you want as simple of a model as possible that adequately describes the behavior you're curious about. Often that includes constant-time multiplication, but that'd seriously deceive you in an analysis of Fibonacci runtime.
tylerhou 5y ago
No. Specifically, in this case we are multiplying exponentially large numbers meaning that they have linearly many bits with respect to the input, so you must account for the multiplication costs as they are not insignificant (e.g. O(n^1.59)). For normal computations, you usually deal with numbers that have logarithmically many bits wrt. the input, so the runtime is negligible (something like O(log^1.59(n)), so we can treat it as a constant. It's technically not a constant, but it's so close to the time to actually read the input (log(n) or n) that we can treat it as one.
- patrick451 5y ago
  That's unconvincing. You could say the same thing about matrix multiplication with huge elements.
  - tylerhou 5y ago
    Yes, you could. But normally when people analyze the runtime of matrix multiplication, they assume that the elements have constant size (hence constant runtime arithmetic) and the matrix size scales. But you could also write a runtime that scales with respect to the size of the elements as well; assuming that we are using integer elements that have size at most M your runtime would be something like O(n^3log^2(M)M) in the naive case. In Fibonacci it is not valid to assume that your arithmetic is constant time because you are doing arithmetic on integers that grow exponentially. In general, it is not valid to assume that you can do constant-time arithmetic on all numbers because then you could solve many many problems much faster than possible on a word-RAM machine by encoding your problem as a real number, and multiplying/adding.
    - a-dub 5y ago
      > In general, it is not valid to assume that you can do constant-time arithmetic on all numbers because then you could solve many many problems much faster than possible on a word-RAM machine by encoding your problem as a real number, and multiplying/adding. i miss theory of computation. the reasoning was so simple and the proofs were so fun.

hansvm 5y ago

Yes you could. For a fixed-width register machine you can go even further and say that there don't exist non-trivial constant time algorithms (it takes at least logarithmic time to read the entire input). This includes bread-and-butter classics like hashtables. In practice we usually hand-waive those details away because they don't apply on the domain of interest; rarely is somebody meaningfully exceeding a 64-bit space for their hashtables. You can formalize that a bit with something like the "Word RAM" model of computation -- assume that you have fixed width registers as wide as your inputs. For the Fibonacci sequence those details are a little harder to hand-waive away because of how quickly the output grows. As soon as the input is bigger than ~64 on a modern computer you'll start to see the effects of that linear runtime. On most clusters you'd have to stream Fib(1<<64) just to see all the bits, and it'd take ages. The reason that idea doesn't (usually) get applied to algorithms involving multiplication is because usually we're operating implicitly in a model that includes constant-time multiplication of "big enough" numbers. In cryptography and other fields operating on large integers though that analysis absolutely does come into play. The overarching theme is that reality is hard to capture both succinctly and accurately, and you want as simple of a model as possible that adequately describes the behavior you're curious about. Often that includes constant-time multiplication, but that'd seriously deceive you in an analysis of Fibonacci runtime.

tylerhou 5y ago

No. Specifically, in this case we are multiplying exponentially large numbers meaning that they have linearly many bits with respect to the input, so you must account for the multiplication costs as they are not insignificant (e.g. O(n^1.59)). For normal computations, you usually deal with numbers that have logarithmically many bits wrt. the input, so the runtime is negligible (something like O(log^1.59(n)), so we can treat it as a constant. It's technically not a constant, but it's so close to the time to actually read the input (log(n) or n) that we can treat it as one.

patrick451 5y ago
That's unconvincing. You could say the same thing about matrix multiplication with huge elements.
- tylerhou 5y ago
  Yes, you could. But normally when people analyze the runtime of matrix multiplication, they assume that the elements have constant size (hence constant runtime arithmetic) and the matrix size scales. But you could also write a runtime that scales with respect to the size of the elements as well; assuming that we are using integer elements that have size at most M your runtime would be something like O(n^3log^2(M)M) in the naive case. In Fibonacci it is not valid to assume that your arithmetic is constant time because you are doing arithmetic on integers that grow exponentially. In general, it is not valid to assume that you can do constant-time arithmetic on all numbers because then you could solve many many problems much faster than possible on a word-RAM machine by encoding your problem as a real number, and multiplying/adding.
  - a-dub 5y ago
    > In general, it is not valid to assume that you can do constant-time arithmetic on all numbers because then you could solve many many problems much faster than possible on a word-RAM machine by encoding your problem as a real number, and multiplying/adding. i miss theory of computation. the reasoning was so simple and the proofs were so fun.