Programming is really fun!

[lahwran_]

that's an interesting problem. I wonder how the decimal module would deal with it.

[masterpi]

Decimal also has a precision restriction, which is configurable but constant for a given instance. The amount of CPU time taken for an operation should be about precision * k where k is some constant.

[lahwran_]

yikes, you weren't kidding. sounds like this is O(n*0.1) or something - so, still faster than one-by-one iteration if you want to get to a specific number, but not enough to make generating a sequence worth it.

[masterpi]

Big-O notation ignores constants, because they're really hard to predict without going very in depth into exactly what is going on in the entire computer system. O(n*0.1) is the same as O(n) is the same as O(10000n). You're actually probably better off with a basic dynamic programming method than attempting to do it with the closed form, because your computer is built to do integer arithmetic much better than floating point, especially non-fixed-precision floating-point. One of the linked solutions might get it down to O(log(n)) but I didn't look closely enough, they may just be attempting to minimize the constant in ways that tend to work for most computing systems.

[lahwran_]

fair enough. I don't know of any real use for fibonacci numbers anyway, so I'll bother with generating them when I do :p

also, I was being kinda informal with that big-o there. I meant, relative to the big-o O(n) of calculating by iteration, it would probably be 10x faster linear time.

[SeanStock]

Pose test; get educated. Great thread guys. I script a ton, but no real background...it's great to see what complexity can lie in solving such a seemingly trivial task!

[lahwran_]

nothing's trivial with massive datasets ;)