Radix conversion
Xcriber51
I wrote this function for converting numbers in base-N to decimal.
(defun in-decimal-base (n base)
(let ((tmp 0) (digit 0) (result 0))
(do ((i 0 (1+ i)))
((<= n 0))
(setf tmp (mod n (expt 10 (1+ i))))
(setf digit (/ tmp (expt 10 i)))
(setf result (+ result (* digit (expt base i))))
(setf n (- n tmp)))
result))
And you use it as:
> (in-decimal-base 1020 7)
357
> (in-decimal-base 10110 2)
22
etc.
Not being a LISP guru, can't think of a "tail recursive" version
immediately--assuming it'd be any better in this case. Still, it feels
so... imperative and inelegant -- those stacked "setfs" look awful.
(Please, no wisecracks like "what makes you think 'imperative =>
inelegant'?" etc.)
Any suggestions for improvement?
-- Ken
Alexander Schmolck
> Hi --
>
> I wrote this function for converting numbers in base-N to decimal.
>
> (defun in-decimal-base (n base)
> (let ((tmp 0) (digit 0) (result 0))
> (do ((i 0 (1+ i)))
> ((<= n 0))
> (setf tmp (mod n (expt 10 (1+ i))))
> (setf digit (/ tmp (expt 10 i)))
Aside: if you write low-level code you might as well get rid of the
exponentiation, since it's unnecessarily expensive (hint: (expt 10 i) at loop
iteration i = (* 10 the-same-expression-one-iteration-before)).
> (setf result (+ result (* digit (expt base i))))
> (setf n (- n tmp)))
> result))
>
> And you use it as:
>
> > (in-decimal-base 1020 7)
> 357
>
> > (in-decimal-base 10110 2)
> 22
>
> etc.
>
> Not being a LISP guru, can't think of a "tail recursive" version
> immediately
Don't worry about it (at least not for the moment) -- a loop rewritten as a
tail recursion is still a loop and not necessarily better for it (no matter
what people will try to brain wash you into). Real improvements in conceptual
elegance come from replacing loops with higher order constructs.
> --assuming it'd be any better in this case. Still, it feels
> so... imperative and inelegant -- those stacked "setfs" look awful.
> (Please, no wisecracks like "what makes you think 'imperative =>
> inelegant'?" etc.)
>
> Any suggestions for improvement?
I think the following is a good way to conceptualize what's going on (doesn't
necessarily make for an efficient implementation, but you can always rewrite
for speed when needed later):
(in-decimal-base 1020 7)
1020 -> (1 0 2 0) \ +---+
* -->| + |
7 ^ (3 2 1 0) / +---+
Operators in boxes are REDUCE's those without are MAPCAR's. The first -> is an
UNFOLD (not predefined in common lisp and the opposite of a reduction, if you
want), but you can forget about that for the moment -- reductions and mappings
are more important.
Some more hints (lower-case functions you have to write yourself):
(1 0 2 0) = (decimal-digits 1020) ; first implement it however you like, then
; google unfold
(3 2 1 0) = (REVERSE (iota (LENGTH '(1 0 2 0))))
cheers
'as
p.s. You might get better answers to common lisp related questions in
comp.lang.lisp, however there tends to be a strong anti-functional bias there.
You could also switch to scheme and ask in comp.lang.scheme -- scheme is
of even more dubious practical value than common lisp, but if you want to
learn functional programming paradigms with a lispy language, it has some
social and technical advantages. You might also want to google SICP.
p.p.s. If you're not familiar with reductions, it's really easy:
(reduce '+ (list a b c d)) == a + b + c + d ; insert operator between list elements
(reduce '+ ()) == 0 ; neutral element of operator
Xcriber51
think this should do:
(defun in-decimal-base (n base)
(let ((result 0))
(do ((exp 1 (* base exp)))
((<= n 0))
(setf result (+ result (* (mod n 10) exp)))
(setf n (truncate n 10)))
result))
One could make this recursive--one being yours truly, just to see how it
can be done.
(defun in-decimal (n base)
(in-decimal-helper n base 0))
(defun in-decimal-helper (n base i)
(if (= n 0)
0
(+ (* (mod n 10) (expt base i))
(in-decimal-helper (truncate n 10) base (1+ i)))))
But I guess a solution based on your suggestion is the most LISP-like:
(defun digits (n)
(if (= n 0)
nil
(cons (mod n 10) (digits (truncate n 10)))))
(defun iota (x)
(cond ((zerop x) nil)
(t (append (iota (decf x)) (list x)))))
(defun in-decimal-baby (n base)
(setf digs (digits n))
(setf exps (iota (length digs)))
(reduce '+ (mapcar #'(lambda (x i) (* x (expt base i))) digs exps)))
(I couldn't find IOTA in my CL implementation so I grabbed one from Google
Code search, and I chose to name this last version in George Costanza (of
Seinfeld) fashion. :-D)
BTW I looked up "unfold," but after about half an hour on Google, the
world started to unfold before my eyes without any results. If you know
any implementation, please do quote its code here, and I'll have a look
how this can be coded with it.
--
I know this function is pretty trivial, and--more importantly--to get the
value of 1020 in 7 base, all I have to do is use "#7r1020" in CL. But
that's not the point. I'm just trying to map my imperative mind to the
paradigmatic thinking of LISP.
Thanks again for the tips, Alex. Appreciated.
Cheers
-- Ken
Geoffrey
> Hi --
>
> I wrote this function for converting numbers in base-N to decimal.
>
> (defun in-decimal-base (n base)
>
>
> Not being a LISP guru, can't think of a "tail recursive" version
> immediately--assuming it'd be any better in this case. Still, it feels
> so... imperative and inelegant -- those stacked "setfs" look awful.
> (Please, no wisecracks like "what makes you think 'imperative =>
> inelegant'?" etc.)
>
> Any suggestions for improvement?
>
> -- Ken
Tail recursion isn't terribly difficult to do: in fact, you don't even
need to understand the problem in order to translate code into that
form. The above is a perfectly acceptable imperative approach (though
certainly not optimized). Higher order constructs have already been
mentioned, and fold/unfold is a very attractive method for doing this.
So I'll just offer a very direct translation into a tail-recursive
call.
(defun in-decimal-base (n base)
(labels ((recurser (result i n)
(if (> n 0)
(let ((tmp (mod n (expt 10 (1+ i)))))
(recurser (+ result (* (/ tmp (expt 10 i)) (expt
base i))) (1+ i) (- n tmp)))
result)))
(recurser 0 0 n)))
What this does is define a recurser function. The trick is that
everything required for the next step of the computation is passed as
a parameter to this function. The variable "digit" vanished, because
it was only an intermediate step in calculating the next result: it's
computation has been inserted directly into the code for result. "tmp"
remains only because it's computation would have to be performed twice
without.
It doesn't actually require an understanding of how the algorithm
works in order to translate most imperative loops into tail-recursive
constructs: just take every value needed for the next stage of the
computation and make it a parameter to the recurser.
I hope this explanation helps.
Alexander Schmolck
[sorry, this got stuck in my drafts, hope it's still useful]
> You're right, Alex. I knew there was something too long-winded about it. I
> think this should do:
>
> (defun in-decimal-base (n base)
> (let ((result 0))
> (do ((exp 1 (* base exp)))
> ((<= n 0))
> (setf result (+ result (* (mod n 10) exp)))
> (setf n (truncate n 10)))
> result))
>
> One could make this recursive--one being yours truly, just to see how it
> can be done.
>
> (defun in-decimal (n base)
> (in-decimal-helper n base 0))
>
> (defun in-decimal-helper (n base i)
You can use LABELS for helper functions (it has the advantage that you won't
need to pass BASE and that it keeps the global namespace clean -- it has the
disadvantage that it makes testing and debugging them harder).
> (if (= n 0)
> 0
> (+ (* (mod n 10) (expt base i))
> (in-decimal-helper (truncate n 10) base (1+ i)))))
>
> But I guess a solution based on your suggestion is the most LISP-like:
>
> (defun digits (n)
> (if (= n 0)
> nil
> (cons (mod n 10) (digits (truncate n 10)))))
>
> (defun iota (x)
> (cond ((zerop x) nil)
> (t (append (iota (decf x)) (list x)))))
APPEND should always set off your warning bells. This code is very inefficient
-- quadratic rather than linear in x. This is a typical newbie mistake (I'm
suprised you found this code in a search) -- the standard idiom is to use CONS
and finally (N)REVERSE instead (or LOOP's COLLECT).
>
> (defun in-decimal-baby (n base)
> (setf digs (digits n))
> (setf exps (iota (length digs)))
This doesn't work -- it might appear to, but the consequences of the code
above are really undefined (and what it will do in most implementations is not
what you likely expect, although it appears to work the variables will be
global and lexically scoped). You need to define a variable with LET (or
DEFVAR etc.) before you can SETF it. The idiomatic way to write this is just:
(let* ((digs (digits n))
(exps (iota (length digs))))
...)
> (reduce '+ (mapcar #'(lambda (x i) (* x (expt base i))) digs exps)))
As an aside, whilst the #' can essentially always be safely omitted in front
of (lambda ...) (no change in meaning), it is generally better to write
(reduce #'fun ...) rather then (reduce 'fun ...) -- you need not worry what
the difference is at this stage, #' will always do what you want and ' might
not.
> (I couldn't find IOTA in my CL implementation so I grabbed one from Google
> Code search, and I chose to name this last version in George Costanza (of
> Seinfeld) fashion. :-D)
>
> BTW I looked up "unfold," but after about half an hour on Google, the
> world started to unfold before my eyes without any results.
> If you know any implementation, please do quote its code here, and I'll have
> a look how this can be coded with it.
Try this:
(defun unfoldl (seed next collect till &optional (tail '()))
(cond ((funcall till seed)
tail)
(:else (unfoldl (funcall next seed) next collect till
(cons (funcall collect seed) tail)))))
cheers,
'as