Here's my translation of a version I saw in Haskell:
fnd=: 3 : 0
xs=. 2}.y
ys=. 2{.y
for_i. i.#xs do.
ys=.ys,+/(1,i{xs)*_2{.ys
end.
)
ev3=: 2 }. ([: fnd 0 1,]) % [: fnd 1 0,]
ev3 q
4 9r2 13r3 48r11 61r14 170r39
It's faster for longer cf's
q3=:1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
2 1 2 1 2 1x
10 ts 'ev\ q3'
0.0259532 11328
10 ts '{:@:ev2\ q3'
0.0143576 15104
10 ts 'ev3 q3'
0.0027628 14976
(ev3-:ev\)q3
1
=@@i
John Randall schreef:
Suppose q is a truncated continued fraction, say
q=:4 2 1 3 1 2x
J can evaluate these very niftily using (+%)/ :
ev=:(+%)/
ev q
170r39
ev\ q
4 9r2 13r3 48r11 61r14 170r39
What is more difficult is taking as many terms as are needed until
some condition is satisfied: because of J's right to left evaluation,
you cannot just add another term.
One solution is to evaluate the continued fraction backwards and use
various identitites. Another is to use a matrix formulation as in the
Fibonacci sequence (which corresponds to the continued fraction
1 1 1 1....).
In this, the numerator and denominator appear as the bottom row of a
2x2 matrix, and we get the next term by multiplying by the matrix
2 2 $ 0 1 1, an , where an is the next term of the continued fraction.
mp=:+/ .*
init=:2 2 $ 0 1 1 0
ev2=:mp/ @: |. @: (init , 2 2 ($"1) 0 1 1 ,"1 0 ])
ev2 q
61 14
170 39
{: @: ev2\ q
4 1
9 2
13 3
48 11
61 14
170 39
Does anyone have suggestions as to how to improve this code?
Best wishes,
John
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
