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
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