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