Billy Mays wrote: > On 08/02/2011 08:45 AM, Alain Ketterlin wrote: >> produce integers. And it will fail with overflow for big values. > > If it would make you feel better I can use decimal. > > Also, perhaps I can name my function billy_fibo(n), which is defined as > billy_fibo(n) +error(n) = fibo(n), where error(n) can be made > arbitrarily small.
So you say, but I don't believe it. Given fibo, the function you provided earlier, the error increases with N: >>> fibo(82) - fib(82) # fib returns the accurate Fibonacci number 160.0 >>> fibo(182) - fib(182) 2.92786721937918e+23 Hardly "arbitrarily small". Your function also overflows for N = 1475: >>> fibo(1475) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 3, in fibo OverflowError: (34, 'Numerical result out of range') The correct value only has 307 digits, so it's not that large a number for integer math. I won't show them all, but it starts and ends like this: 8077637632...87040886025 > This runs in constant time rather than linear > (memoized) A good memoisation scheme will run in constant time (amortised). > or exponential (fully recursive) Good heavens no. Only the most naive recursive algorithm is exponential. Good ones (note plural) are linear. Combine that with memoisation, and you have amortised constant time. > at the cost of a minutia of accuracy. I'm reminded of a time my wife was travelling across the US with her band's roadies. At some point crossing the miles and miles of highway through the desert, she pointed out that they were lost and nowhere even close to the city where they were supposed to be playing. The driver answered, "Who cares, we're making great time!" (True story.) > I find this tradeoff acceptable. Given that Fibonacci numbers are mostly of interest to number theorists, who care about the *actual* Fibonacci numbers and not almost-but-not-quite Fibonacci numbers, I'm having a lot of difficulty imagining what sort of application you have in mind that could legitimately make that trade-off. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
