On Tue, Aug 17, 2010 at 3:53 AM, Richard O'Keefe <o...@cs.otago.ac.nz> wrote: > On Aug 17, 2010, at 12:37 AM, Roel van Dijk wrote: >> >> phi = (1 + sqrt 5) / 2 >> fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 >> >> The use of (**) should make the complexity at least O(n). Please >> correct me if I'm wrong (or sloppy). > > Using the classic > x**0 = 1 > x**1 = x > x**(2k+0) = (x**2)**k k > 0 > x**(2k+1) = (x**2)**k + x k > 1 > powers of smallish numbers or matrices can be computed in logarithmic > time. That is an interesting trick. So there exists an algorithm that calculates Fibonacci numbers in O(log n) time.
> Using x**n = exp(n*log(x)) and floating point arithmetic, > the whole thing can be done in O(1) time, and the price of > some inaccuracy. It will calculate a subset of the Fibonacci numbers in O(1) time. Thinking about it I think you can easily calculate subsets of any function in O(1) time, as long as the function is guaranteed to terminate. Simply precompute the answers and store them in an array. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
