Farey sequence

My best effort:

h(n) := block([d,j,l : [[0],[1]]],
  d : setify(makelist(i,i,floor(n/2),n)),
  while not emptyp(d) do (
    j : last(d),
    d : setdifference(d, divisors(j)),   
    l : cons(makelist(i/j,i,1,j-1),l)),
  setify(xreduce('append,l)));

(%i62) compile(h,fc3)$

(%i77) h(500)$
Evaluation took 1.8300 seconds (1.8300 elapsed)

(%i79) fc3(500)$
Evaluation took 1.8900 seconds (1.8900 elapsed)

(%i80) h(500)$
Evaluation took 2.5200 seconds (2.5200 elapsed)

(%i81) fc3(500)$
Evaluation took 1.9900 seconds (1.9900 elapsed)

--Barton

-----maxima-bounces at math.utexas.edu wrote: -----

>To:?Stavros?Macrakis?<macrakis at alum.mit.edu>
>From:?reyssat?<eric.reyssat at math.unicaen.fr>
>Sent?by:?maxima-bounces at math.utexas.edu
>Date:?06/14/2010?06:04PM
>cc:?maxima at math.utexas.edu,?reyssat at math.unicaen.fr
>Subject:?Re:?[Maxima]?Farey?sequence
>
>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
>>
>>
>>
>>
>
>_______________________________________________
>Maxima?mailing?list
>Maxima at math.utexas.edu
>http://www.math.utexas.edu/mailman/listinfo/maxima