Subject is (fast) calculation of the n-th fibonacci number (emphasis on
large values of n). And ffib is my translation of the idea used in the
Haskell wiki article (3.3 Fastest Fib in the West ). I'm not saying it
is a simple or beautiful one. It's just a fast one.
ts '{. (0 1x ,: 1 1)&(+/ . *) ^:(10001) 0 1' NB. use ext. prec.
0.270889 45312
http://www.jsoftware.com/jwiki/Essays/Fibonacci_Sequence#Matrixpower
ts 'f7 10001'
0.023858 104832
ts '{: ffib 10001'
0.007863 35968
time space
ffib 1.00 1.00
Shimura 34.45 1.26
f7 3.03 2.91
first 11 digits:
11{.": {. (0 1x ,: 1 1)&(+/ . *) ^:(10001) 0 1
54438373113
11{. ": f7 10001
54438373113
11{. ": {: ffib 10001
54438373113
=@@i
M.Shimura schreef:
> this is very simple and maybe fast
>
> (0 1 ,: 1 1)&(+/ . *) ^:(i.12) 0 1
> 0 1
> 1 1
> 1 2
> 2 3
> 3 5
> 5 8
> 8 13
> 13 21
> 21 34
> 34 55
> 55 89
> 89 144
>
> [email protected]
> M.Shimura
>
>
>> Inspired by Haskells: http://tinyurl.com/3c3yor
>>
>>
>> ffib=:(+&*:,]*]-~+:@[)/@]`((+&*:,~[*[++:@])/@])@.({...@[)/@(1x
>> 0,~,.@|....@#:)
>>
>> ffib"0 i.8
>> 1 0
>> 1 1
>> 2 1
>> 3 2
>> 5 3
>> 8 5
>> 13 8
>> 21 13
>>
>> ts '{: ffib 100001'
>> 0.748854 265536
>>
>> 11{. ": {: ffib 100001
>> 42026927029
>>
>>
>> (slower) variants:
>>
>> ffib2=: (+&*:,+:@*-*:@])/@]`((+&*:,~*:@[++:@*)/@])@.({...@[)/@(1x
>> 0,~,.@|....@#:)
>>
>> ffib3=: (,+/ .*~,,:],-)/@]`(((,~,:~[,+)+/ .*,~)/@])@.({...@[)/@(1x
>> 0,~,.@|....@#:)
>>
>>
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
