Stavros Macrakis a ?crit :
> How about using Maxima representation for the rationals? Then the
> symmetric part becomes very easy:
>
> fc3(n):=block(L:[0],a:0,b:1,c:1,d:n,
> while 2*c < d do
> (k:floor((b+n)/d),e:k*c-a,f:k*d-b,a:c,b:d,c:e,d:f,L:cons(a/b,L)),
> append(reverse(L),[1/2],1-L))$
Much nicer, but seems very slightly slower. Does a/b try to reduce it to
irreducible form (which is already the case) ?
Eric
>
>
> On Mon, Jun 14, 2010 at 17:06, reyssat <eric.reyssat at math.unicaen.fr
> <mailto:eric.reyssat at math.unicaen.fr>> wrote:
>
> Stavros Macrakis a ?crit :
>
> Appending to the *end* of a list is expensive. Cons'ing on to
> the beginning then reversing is much faster:
>
> (%i1) showtime:all;
> Evaluation took 0.0000 seconds (0.0000 elapsed)
> (%o1) all
> (%i2) (l:[],for i thru 20000 do l:cons(i,l),reverse(l))$
> Evaluation took 0.1000 seconds (0.1000 elapsed)
> (%i3) (l:[],for i thru 20000 do l:append(l,[i]))$
> Evaluation took 4.6300 seconds (4.6300 elapsed)
>
>
> Thank you, I forgot this big difference. Too bad that the word
> "append" is easier to remember for me !
>
> with this improvement, fc computes the list faster than ff2. And
> two cents more, notice that the Farey sequence is symmetric around
> 1/2, hence it suffices to compute one half of it (only for 2*c<d),
> then transform the result by symmetry (faster than computing the
> other half) :
> fc2(n):=block(L:[[0,1]],a:0,b:1,c:1,d:n,
> while 2*c<d do
> (k:floor ((b+n)/d), e:k*c-a,f:k*d-b, a:c,b:d,c:e,d:f,
> L:cons([a,b],L)),
> append(reverse(L) , [[1,2]] , map(lambda([x],[x[2]-x[1],x[2]]),L)));
>
> Eric
>
>
> On Mon, Jun 14, 2010 at 15:55, reyssat
> <eric.reyssat at math.unicaen.fr
> <mailto:eric.reyssat at math.unicaen.fr>
> <mailto:eric.reyssat at math.unicaen.fr
> <mailto:eric.reyssat at math.unicaen.fr>>> wrote:
>
> Adam Majewski a ?crit :
>
> ......reyssat pisze:
>
> This is the first method of
>
> http://magma.maths.usyd.edu.au/magma/Examples/node6.html
> a maxima implementation is :
> fc(n):=block(a:0,b:1,c:1,d:n,
> while c<n do
> (k:floor ((b+n)/d), e:k*c-a,f:k*d-b, a:c,b:d,c:e,d:f));
>
>
> Thx but fc gives no result. (:-))
>
> Yes, this is why I said the elements are computed but not
> stored.
>
> One way to get a result is to add a print instruction
> inside the
> loop :
> (k:floor ((b+n)/d), e:k*c-a,f:k*d-b, a:c,b:d,c:e,d:f,
> print([a,b])));
> Of course, printing takes time.
>
> An other way is to store the result, maybe by appending the new
> element :
>
> fc(n):=block(L:[],a:0,b:1,c:1,d:n,
> while c<n do
> (k:floor ((b+n)/d), e:k*c-a,f:k*d-b, a:c,b:d,c:e,d:f,
> L:append(L,[[a,b]])),L);
>
> but I don't know if appending one element each time is
> efficient
> or not.
>
> Eric
>
>
> Adam
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu <mailto:Maxima at math.utexas.edu>
> <mailto:Maxima at math.utexas.edu <mailto:Maxima at math.utexas.edu>>
>
> http://www.math.utexas.edu/mailman/listinfo/maxima
>
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu <mailto:Maxima at math.utexas.edu>
> <mailto:Maxima at math.utexas.edu <mailto:Maxima at math.utexas.edu>>
>
> http://www.math.utexas.edu/mailman/listinfo/maxima
>
>
>
>