Topic: { Challenge } Convert a Continued fraction to a simple fraction

[qjchen]

{ Challenge } Convert a Continued fraction to a simple fraction



Continued fraction definition can be found from the wiki page:
http://en.wikipedia.org/wiki/Continued_fraction

And the form of it is as following picture.


Now, question is: if we know a continued fraction which is expressed by (list a0 a1 a2 a3.... an)

How to simplify it to a simple fraction (only one numerator and one denominator) list (a b)

Code: [Select]

(defun convert(lst) .............)

(convert '(0 1 3 4 6))  -> '(81 106)

From my attached picture, you may know what I means.


BTW, this question comes from my study on "Using Continued Fractions to Convert Decimals to Fractions" "http://www.willamette.edu/~mjaneba/help/frac.html"

And I find it is a funny recursion question, I hope you enjoy it

[VovKa]

Code: [Select]

(defun test (lst / rslt)
  (if (cdr lst)
    (progn (setq rslt (test (cdr lst)))
   (list (+ (* (car lst) (car rslt)) (cadr rslt)) (car rslt))
    )
    (list (car lst) 1)
  )
)


[qjchen]

oh~~, VoVka， you beat me 

My codes is similar to yours, but more longer.....

Thanks for sharing

[Lee Mac]

My attempt at a non-recursive solution:

Code: [Select]

(defun con->sim ( a / b x ) (setq a (reverse a) b 1)
 
  (while (cdr a) (setq x (car a) a (cons (+ (* x (cadr a)) b) (cddr a)) b x))
 
  (list (car a) b)
)


[Lee Mac]

How about the reverse 

Code: [Select]

(defun sim->con ( a b )
  (if (zerop b) nil
    (cons (fix (/ a b)) (sim->con b (rem a b)))
  )
)


Code: [Select]

(sim->con 81 106)
==> (0 1 3 4 6)


[ElpanovEvgeniy]

Code: [Select]

(defun s>c (a b)
;;My version is similar to Lee Mac
  (if (> b 0)
  (cons (fix (/ a b)) (s>c b (rem a b)))
 )
)
(defun c>s (l)
 (defun f (l)
  (if (cddr l)
   (f (cons (cadr l) (cons (+ (car l) (* (cadr l) (caddr l))) (cdddr l))))
   (reverse l)
  )
 )
 (f (cons 1 (reverse l)))
)
test:

Code: [Select]

(fix (* pi 1e+8))  ;; >> 314159265
(s>c (fix (* pi 1e+8)) 1e+8) ;; >> (3 7 15 1 288 1 2 1 3 1 7 4)
(c>s '(3 7 15 1 288 1 2 1 3 1 7 4)) ;; >> (62831853 20000000)
(rtos(/ 62831853 20000000.)2 8) ;; >> "3.14159265"

[highflyingbird]

Code: [Select]

(defun f (L / k)
  (if L
    (setq k (f (cdr L))
  k (cons (+ (* (car L) (car k)) (cdr k)) (car k))
    )
    '(1 . 0)
  )
)Mine is the same as VoVka's,just a little different.

[ElpanovEvgeniy]

last variant:

Code: [Select]

(defun c>s (l)
 (defun f (a c) (list (+ (* (car a) c) (cadr a)) (car a)))
 (if (cdr l)
  (f (c>s (cdr l)) (car l))
  (list (car l) 1)
 )
)

[qjchen]

Thank you all , I learn a lot from yours code..
My code like VoVka and highflybird ...

Code: [Select]

(defun cf1(lst)
  (cond ((= (length lst) 1) (list (car lst) 1))
        (T (list (+ (* (car lst) (car (cf1 (cdr lst)))) (cadr (cf1 (cdr lst)))) (car (cf1 (cdr lst)))))
  )
)

and let me try to write some S to C code...

[Lee Mac]

Quick test:

Code: [Select]

(setq l '(0 1 3 4 6))

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (CON->SIM_MAC L).....1045 / 7.72 <fastest>
    (TEST_VOV L).........1060 / 7.61
    (F_HIGH L)...........1092 / 7.39
    (C>S_EV L)...........1186 / 6.80
    (C>S2_EV L)..........1248 / 6.46
    (CF1_CHEN L).........8065 / 1.00 <slowest>


Code: [Select]

(setq n 81 d 106)

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (SIM->CON_MAC N D).....1077 / 1.01 <fastest>
    (S>C_EV N D)...........1092 / 1.00 <slowest>

 

[qjchen]

Thanks Lee~.
In my code I used (cdr lst) for three times but not as VoVka and Highflybird's.
It seems this was a bad choice, maybe sometimes I should add one local variable rather than reduce it.

And in your test, maybe non-recursion  algorithm will be quick than recursion one.

[Lee Mac]

Thanks Lee~.
In my code I used (cdr lst) for three times but not as VoVka and Highflybird's.
It seems this was a bad choice, maybe sometimes I should add one local variable rather than reduce it.

And in your test, maybe non-recursion  algorithm will be quick than recursion one.

In most cases, non-recursive solutions are quicker (but less elegant) than their recursive alternatives due to the recursive function's use of a stack of previous unreturned expressions (Activation Records: memory space for parameters, variables and the return address), which build up when re-evaluating the function. This makes it slower and more memory consuming due to maintaining the stack.

Also, you make the recursive call three times as you say, meaning the program has to do the work three times over 

Lee