roman numerals revisited

[eddier]

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 Expand


(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

[Lutz]

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 Expand


(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

[eddier]

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 Expand


(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

[newdep]

Ha! never thought about this actualy. Thats not even as simple as we all

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



Norman.

[qdn5609]

Could anyone please help me how to write (roman 2000) in clisp (common lisp). Please Please I got stuck.

[cormullion]

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://forums.devshed.com/other-programming-languages-139/lisp-roman-numerals-320899.html



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



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



But isn't it built-in to CL's (format) function?

[Lutz]

There is one on here: http://newlisp.org/index.cgi?roman_numbers_generator">http://newlisp.org/index.cgi?roman_numbers_generator



Also accessible from this page: http://newlisp.org/index.cgi?Code_Contributions">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 :)