23 feb 2009
- Generating Fibonacci's sequence
Contrary to Essays/Fibonacci Sequence where only a single Fibonacci number is produced, I want to generate (the start of) the sequence as efficient as possible. This was done with F1 before in 0805 Boss, and extended in 0805 Hui.
Recently, in private communication, Groeneveld came with
fib17D=: [: {."1 (,~@{.+0,~{:)^: (<@]`(1x 0"_))which he pointed out to be equivalent with the one in 0108 Cerovski
3 :'(,{:+{:@}:)^: y (0 1)'All I could do was producing a more elegant version of F1, the Repeated doubling solution, by
(,}. +&(*{:) }:)^:(]`(1x 1"_))although the performance still was poor.
(fib17D 4097)-:(,}. +&(*{:) }:)^:(]`(1x 1"_))12
1
10 ts'fib17D 4097'
0.028488048 5931840
10 ts'(,}. +&(*{:) }:)^:(]`(1x 1"_))12'
0.2210053 6841472
(,*/) 0.2210053 6841472 % 0.028488048 5931840
7.76 1.15 8.95Groeneveld's code could be improved a bit by an alternative which essentially was presented in 1006 Jamin. There however it was applied to floating points numbers, not to extended integers.
F2=:[:{."1 (+/,{.)^:(<@]`(1 0x"_))
(fib17D -: F2)10000
1
5 ts'fib17D 10000'
0.1449003 31101696
5 ts'F2 10000'
0.102745 16135360
(,*/)0.1449003 31101696 % 0.102745 16135360
1.41 1.93 2.72