newlispfanclub.alh.net

Posted: **Mon Oct 31, 2005 8:41 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 all

(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

Posted: **Mon Oct 31, 2005 11:09 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 all

(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

Posted: **Tue Nov 01, 2005 2:44 pm**

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 all

(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

Posted: **Wed Nov 02, 2005 8:54 pm**

Ha! never thought about this actualy. Thats not even as simple as we all
"think" it is ;-) I like this..!

Norman.

Posted: **Sat Apr 22, 2006 12:09 am**

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

Posted: **Sat Apr 22, 2006 12:17 pm**

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

http://forums.devshed.com/other-program ... 20899.html

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

http://web.cecs.pdx.edu/~mperkows/CLASS ... /ROMAN1.CL

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

Posted: **Sat Apr 22, 2006 12:28 pm**

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

newlispfanclub.alh.net

roman numerals revisited

roman numerals revisited