Edit: Someone's implementation: http://ideone.com/NWQe38
Edit: constant time -> log time
 Schönhage-Strassen multiplication, one of many bignum multiplication algorithms with sub-quadratic complexity. Other algorithms in common use have worse asymptotic performance.
It's also worth noting that since the Fibonacci sequence grows exponentially, the number of digits is the result will be linear in n. Therefore, the memory requirement is actually O(n), and writing the result to the screen will be O(n).
Right; as you sketch out, there's some constants that disappear into the O() notation.