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))$
On Mon, Jun 14, 2010 at 17:06, reyssat <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>> 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>
>>
>> http://www.math.utexas.edu/mailman/listinfo/maxima
>>
>>
>> _______________________________________________
>> Maxima mailing list
>> Maxima at math.utexas.edu <mailto:Maxima at math.utexas.edu>
>>
>> http://www.math.utexas.edu/mailman/listinfo/maxima
>>
>>
>>
>