Adam Majewski a ?crit :
> Richard Fateman pisze:
>> 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
>
> Thx.
>
> I have found also :
>
> (defun farey-cauchy (n)
> (let ((a 0) (b 1) (c 1) (d n) k f e)
> (format t "~a/~a " a b)
> (loop while (< c n) do
> (setq k (floor (/ (+ n b) d))
> e (- (* k c) a)
> f (- (* k d) b)
> a c
> b d
> c e
> d f)
> (format t "~a/~a " a b))))
>
>
> from http://www.ymeme.com/farey-cauchy-sequence-lisp-101.html
>
> but I can't find its time of execution to compare with maxima results
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));
This implementation where the elements of the list are computed but not
stored looks about the same speed as in method 3 after the improvement
by 25% I mentioned this morning. I don't know the fastest way to store
the elements in a list.
Eric
>
> Adam
>
>
>
>
>>
>>
>>
>> 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
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>