| 123456789101112131415161718192021222324 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 19 June 2018
- # https://github.com/trizen
- # A very efficient algorithm for computing the nth-Fibonacci number.
- func fibonacci_number(n) {
- var (f, g) = (0, 1)
- var (a, b) = (0, 1)
- for k in (0 .. n.ilog2) {
- (f, g) = (f*a + g*b, f*b + g*(a+b)) if n.getbit(k)
- (a, b) = (a*a + b*b, a*b + b*(a+b))
- }
- return f
- }
- say fibonacci_number(100) #=> 354224848179261915075
- say 15.of(fibonacci_number) #=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
|
