Re: Code from a Rosetta Code Task

[Jos van Uden]

On 30-8-2013 0:40, H. S. Teoh wrote:
(...)

A far better implementation is to use std.range.recurrence:

        uint fib(in uint n) pure nothrow {
                return recurrence!((a,n) => a[n-2] + a[n-1])(1, 1)
                        .drop(n-1)
                        .front;
        }

This implementation has linear time complexity and constant space
complexity (vs. exponential time complexity vs. linear space complexity
in the original).

To illustrate how bad it is, I wrote a program that calls fib(50) for
each of the above implementations, and observed how long it takes each
one to return an answer. The version using recurrence completes in a
fraction of a second, the second takes two *minutes*. I bumped it up to
fib(100), and the recurrence version still runs under a fraction of a
second, but I ran out of patience waiting for the second one.

(...)

http://www.wolframalpha.com/input/?i=fib(100)


void main() {
    import std.bigint, std.range;
    BigInt fib(in uint fibN) pure {
        return recurrence!((a,n) => a[n-2] + a[n-1])(BigInt(1), BigInt(1))
            .drop(fibN-1)
            .front;
    }
    assert(fib(100) == BigInt("354_224_848_179_261_915_075"));
}


nice