3 ms·

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 a

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.

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.