An issue here is that the the nth Fibonacci number has O(N) bits, so once you move into arbitrary arithmetic calculations your +'s and *'s will become O(N) and

An issue here is that the the nth Fibonacci number has O(N) bits, so once you move into arbitrary arithmetic calculations your +'s and *'s will become O(N) and O(N logN) respectively.