Here's an idea.
:lisp (defun $fa(n)(cons '(mlist)(loop for i from 0 to n collect (/ i n))))
this gives you 0, 1/100, 2/100 ..... in lowest terms. of course 2/100
is also 1/50...
Anyway, compute all fa(1) ... fa(100) and merge them, eliminating
duplicates.
:lisp (defun $merge(n m) (cons '(mlist) (merge 'list (cdr n)(cdr m) #'<)))
:lisp (defun $nodups(n) ;; exercise for the reader.
;; actually, eliminating duplicates during the merge is going to be
faster.
RJF
Adam Majewski wrote:
> Hi Barton,
>
> Thx for an answer,
>> Suggestions:
>>
>> (0) Read about the Maxima function "adjoin" and try converting your
>> function to use sets
>> instead of lists--for an n element set S, the time complexity of
>> adjoin(x,S) is log_2(n),
>> I think. For an n element list l, the time complexity for
>> member(x,l) is n.
> I will try it.
>
>> (1) Try bounding the time complexity of your code.
> Do you think about some tool or analysis ? ( I'm not an expert ).
>
>>
>> (2) Do a web search on "Farey" and try bounding the time complexity
>> of each algorithm you find.
> I have found :
> http://magma.maths.usyd.edu.au/magma/Examples/node6.html
>
> On my computer Evaluation of Farey(100) took 2.6800 seconds (2.6800
> elapsed)
>
> So changing to set should make it faster.
>>
>> (3) Using "denom" or "num" as identifiers can cause trouble because
>> there are Maxima functions
>> with these names.
>
> OK. I have change it.
>
>
> Regards
>
> Adam
>>
>> --Barton
>>
>> -----maxima-bounces at math.utexas.edu wrote: -----
>>
>>
>>> I try to compute Farey sequences.
>>> I have made function :
>>>
>>> Farey(n):=
>>> block(
>>> [a],
>>> a:[0/1,1/1],
>>> if n>=2 then
>>> for denom:2 thru n step 1 do
>>> for num:1 thru (denom-1) step 1 do
>>> if (not member(num/denom,a)) then a:cons(num/denom,a),
>>> return(a)
>>> );
>>>
>>> It seems to work.
>>> Is it true or can it be done better ?
>>>
>>>
>>> Adam
>>>
>>> _______________________________________________
>>> Maxima mailing list
>>> 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