Text only | Text with Images

newLISP Fan Club

Forum => newLISP in the real world => Topic started by: eddier on October 31, 2005, 12:41:25 PM

Title: roman numerals revisited
Post by: eddier on October 31, 2005, 12:41:25 PM
Lutz,



I've been trying to recode some of my recursive routines to iterative ones. The iterative versions aren't nearly as elegant. For example, recoding a recursive roman numeral conversion to an iterative version looks horrible (below). Looks even worse to maintain, but you're right, it runs significantly faster.


Code Select

(define (->roman n)
    (let (s "" v '(100 50 40 10 9 5 4 1))
      (dotimes (i (length v))
        (while (>= n (v i))
          (setq s (append s ('("C" "L" "XL" "X" "IX" "V" "IV" "I") i))
                n (- n (v i)))))
      s))


Am I doning the right thing here? Or, should I be coding in a different way I'm not familiar with? (dotimes (while ick!



Eddie
Title:
Post by: Lutz on October 31, 2005, 03:09:12 PM
I don't see any improvement except for replacing the repeated append with write-buffer which will be faster for longer bigger n:


Code Select

(define (->roman n)
    (let (s "" v '(100 50 40 10 9 5 4 1))
      (dotimes (i (length v))
        (while (>= n (v i))
          (write-buffer s  ('("C" "L" "XL" "X" "IX" "V" "IV" "I") i))
          (setq n (- n (v i))) ))
      s))


I would be interested to see the recursive function too,



Lutz
Title:
Post by: eddier on November 01, 2005, 06:44:56 AM
Look at Sam Cox's version.



Here is his algorithm with a few minor changes. Note everything is a pure function with no side effects!


Code Select

(define (->roman n)
    (let (roman-a '((100  "C") (99 "IC") (90 "XC") (50  "L") (49 "IL")
                    (40 "XL")  (10  "X") (9 "IX") (5  "V") (4 "IV") (1  "I")))
     
      (define (roman-aux result n pair remaining)
          (roman-aux-2 result n (pair 0) (pair 1) remaining))
     
      (define (roman-aux-2 result n val rep remaining)
          (if (= n 0)  result
              (< n val) (roman-aux result n (remaining 0) (1 remaining))
              (roman-aux-2 (append result rep) (- n val) val rep remaining)))
     
      (roman-aux "" n (roman-a 0) (1 roman-a))))


ps -- My original does not handle 99 and 49 correctly. 99:"IC"  and 49:"IL" need to be added to the appropriate lists.





Eddie
Title:
Post by: newdep on November 02, 2005, 12:54:37 PM
Ha! never thought about this actualy. Thats not even as simple as we all

"think" it is ;-) I like this..!



Norman.
Title:
Post by: qdn5609 on April 21, 2006, 05:09:49 PM
Could anyone please help me how to write (roman 2000) in clisp (common lisp). Please Please I got stuck.
Title:
Post by: cormullion on April 22, 2006, 05:17:34 AM
Quote from: "qdn5609"Could anyone please help me how to write (roman 2000) in clisp (common lisp). Please Please I got stuck.


//http://forums.devshed.com/other-programming-languages-139/lisp-roman-numerals-320899.html



//http://paste.lisp.org/display/13733



//http://web.cecs.pdx.edu/~mperkows/CLASS_ROBOTICS/LISP/tanimoto/ROMAN1.CL



But isn't it built-in to CL's (format) function?
Title:
Post by: Lutz on April 22, 2006, 05:28:48 AM
There is one on here: http://newlisp.org/index.cgi?roman_numbers_generator



Also accessible from this page: http://newlisp.org/index.cgi?Code_Contributions



This nicely written piece by Sam Cox is easy to understand and translate into any other programming language.



Lutz



Ps: and qdn5609's teacher will be delighted because it is recursive :)
Text only | Text with Images