Mixed Radix Numbers

[rickyboy]

Sorry that this is not anything about guiserver.  :-)  But have you heard of this: http://en.wikipedia.org/wiki/Mixed_radix">Wikipedia:Mixed Radix?



It turns out that it is not uncommon that I use these, so I wrote a newLISP module which helps the newLISP programmer to make and use them.  Here are usage examples.

Code Select Expand

> (load "mixed-radix.lsp")
MAIN
> (mixed-radix:new HHMMSS (hours minutes seconds) (1 60 60))
HHMMSS
> (HHMMSS:to-minutes '(3 34 42))
214.7
> (HHMMSS:to-seconds '(3 34 42))
12882
> (HHMMSS:from-minutes 214.7)
(3 34 42)
> (HHMMSS:from-seconds 12882)
(3 34 42)
> (HHMMSS:+ '(3 34 42) '(1 54 59))
(5 29 41)

Recently, my real estate agent wanted to know the square footage of the finished portions of my basement, so I thought "Perfect job for newLISP!"  :-)



When the following is loaded in newLISP

Code Select Expand

;;--------------------------------------
;; Application: Floor plan lengths

(load "mixed-radix.lsp")

(mixed-radix:new ftin (feet inches) (1 12))

(define rawdims '((laundry ((5 5) (2 11) (4 6.5))
                           ((7 1.5)))
                  (bath ((4 10.5))
                        ((7 1)))
                  (family-room ((10 4.5) (8 11.5) (0 1))
                               ((12 1) (10 0) (0 1)))))

(define (dim<-rawdim rawdim)
  (list (rawdim 0)
        (apply ftin:add (rawdim 1))
        (apply ftin:add (rawdim 2))))

(define dims (map dim<-rawdim rawdims))

(define (sqft<-dim dim)
  (list (dim 0)
        (mul (ftin:to-feet (dim 1))
             (ftin:to-feet (dim 2)))))

;; Show and tell.
(println "Dimensions:")
(println dims)
(define sqftages (map sqft<-dim dims))
(println "SQ FTages:")
(println sqftages)
(println "Total SQ FT = " (apply add (map last sqftages)))

it yields

Code Select Expand

Dimensions:
((laundry (12 10.5) (7 1.5)) (bath (4 10.5) (7 1)) (family-room (
   19 5)
  (22 2)))
SQ FTages:
((laundry 91.734375) (bath 34.53125) (family-room 430.4027778))
Total SQ FT = 556.6684028

Hmm ...  Not a large area, but nonetheless correct.  Incidently, the reason why there are multiple ftins for the width or breadth dimensions of a room was because I couldn't measure the room straight across in one shot (either the length was too long for the tape measure or I had to measure around obstacles like cases or door frames) -- I figured to let newLISP due the adding.  :-)



Here is the module's code from mixed-radix.lsp.  Enjoy (as Norman would say)!  --Ricky

Code Select Expand

;;;; mixed-radix.lsp -- Mixed radix numbers for newLISP
;;;; Author: Rick Hanson
;;;; Date: 9 June 2007

(context 'mixed-radix)

;;;-------------------------------------
;;; Slots and Constructor

(define labels '())
(define bases '())

(define-macro (mixed-radix:new mrn-symbol mrn-labels mrn-bases)
  (letex (mrn-labels mrn-labels mrn-bases mrn-bases)
    (MAIN:new 'mixed-radix mrn-symbol)
    (let (ctx (eval mrn-symbol)
          unqualify (lambda (symb) (replace ".*:" (string symb) "" 0)))
      (setq ctx:labels (quote mrn-labels))
      (setq ctx:bases (quote mrn-bases))

      ;; Setup the conversion functions for new instances.
      (dolist (label ctx:labels)
        (set (sym (append "to-" (unqualify label)) ctx)
             (letex ($$idx $idx fsym (sym 'mid-units<-mixrad ctx))
               (curry fsym $$idx)))
        (set (sym (append "from-" (unqualify label)) ctx)
             (letex ($$idx $idx fsym (sym 'mixrad<-mid-units ctx))
               (curry fsym $$idx))))
      mrn-symbol)))

;;;-------------------------------------
;;; Utilities used in this context.

(define (compose)
  (apply (lambda (f g) (expand (lambda () (f (apply g (args)))) 'f 'g))
         (args) 2))

(define-macro (kurry f)
  (letex ($f (eval f)
          $cargs (map eval (args)))
    (lambda () (apply $f (append (quote $cargs) (args))))))

(define (butlast xs) (0 (- (length xs) 1) xs))

;; This version of `unfold' uses `while' and `setq' (for reasons of
;; time and space efficiency) -- "don't pay any attention to the man
;; behind the curtain!" :-)
(define (unfold p f g s post)
  (let (acc '())
    (while (not (p s))
      (push (f s) acc -1)
      (setq s (g s)))
    (post p f g s acc)))

;;;-------------------------------------
;;; Method Definitions

(define (low-units<-mixrad M (bases bases))
  "Convert a mixrad `M' to a scalar in low-order units with respect
to the list of bases `bases'."
  (rotate bases -1)
  (apply MAIN:add
    (map (lambda (i) (mul (M i) (apply mul (i bases))))
         (sequence 0 (- (length M) 1)))))

(define (high-units<-mixrad M (bases bases))
  "Convert a mixrad `M' to a scalar in high-order units with
respect to the list of bases `bases'."
  (div (low-units<-mixrad M) (apply mul bases)))

(define (mid-units<-mixrad mid M)
  "Convert a mixrad `M' to a scalar in `mid'-order units with
respect to the list of bases `bases'.  `mid' is zero-based.  This
function acts as if the radix point of `M' were after the
`mid'-th digit (from the left).  For instance to convert 3 hours,
34 minutes, 42 seconds into minutes, say
    (mixed-radix:new HHMMSS (hours minutes seconds) (1 60 60))
    (HHMMSS:mid-units<-mixrad 1 '(3 34 42))
which yields 214.7, as expected."
  (letn (mid+1 (+ mid 1)
         basesL (0 mid+1 bases)
         digitsL (0 mid+1 M)
         basesR (cons 1 (mid+1 bases))
         digitsR (cons 0 (mid+1 M)))
    (MAIN:add (low-units<-mixrad digitsL basesL)
              (high-units<-mixrad digitsR basesR))))

(define (mixrad<-low-units N (bases bases))
  "Convert `N', which is a scalar in low-order units, to a mixrad,
with respect to the list of bases 'bases'."
  (rotate bases -1)
  (unfold (lambda (s) (>= (s 1) (length bases)))
          (lambda (s) (/ (s 0) (apply mul ((s 1) bases))))
          (lambda (s) (list (mod (s 0) (apply mul ((s 1) bases))) (+ (s 1) 1)))
          ;; In the seed, keep track of the latest remainder AND an
          ;; incrementing index with which we use to slice `bases':
          (list N 0)
          ;; In the post-processor, add the last remainder into the
          ;; last entry in the accumulated list:
          (lambda (p f g s res0)
            (append (butlast res0) (list (MAIN:add (s 0) (last res0)))))))

;; This is not used by any method or instance conversion function, but
;; is here for completion sake.
(define (mixrad<-high-units N (bases bases))
  "Convert `N', which is a scalar in high-order units, to a mixrad,
with respect to the list of bases 'bases'."
  (mixrad<-low-units (apply mul (cons N bases))))

(define (mixrad<-mid-units mid N)
  "Convert `N', which is a scalar in mid-order units, to a mixrad,
with respect to the list of bases 'bases'."
  (mixrad<-low-units (apply mul (cons N ((+ mid 1) bases)))))

;; Now it's easy to define a normalization function.
(define (normalize M)
  "Return the canonical representation of mixrad `M' with respect to
the list of bases `bases'."
  (mixrad<-low-units (low-units<-mixrad M)))

(define (component-wise-operator op) (compose normalize (kurry map op)))
(define mixed-radix:add (component-wise-operator MAIN:add))
(define mixed-radix:sub (component-wise-operator MAIN:sub))
(define mixed-radix:+ mixed-radix:add)
(define mixed-radix:- mixed-radix:sub)

(context MAIN)


[rickyboy]

http://www.rickhanson.org/code/mixed-radix.pdf">This code rendering is easier on the eyes than the previous post's code block. :)

[newdep]

Nice code Rick!! i like the "mixed radix" solution...



I was struggling with the HHMMSS last time also because i needed to calculate

the uptime of a machine since 1970 in seconds back to now and spilt it

into HH MM SS ;-) The variable to context is a nice solution i would not have thought of that ;-) Also very usefull for statistics..



Greetings, Norman.

[Fanda]

Quite interesting! I like the math and the newLISP tricks! Also very useful.



Hint: Exchange 'butlast' to newLISP's 'chop'.



It seems that reading "The Art of Computer Programming" by Donald Knuth could be really interesting. I have never read it, but I have seen many notes mentioning this book.



Fanda

[cormullion]

That's good stuff - I can use this a lot for my astronomy stuff.



Do you get the "to-" and "from-" functions for all the units that you define? And can you mul and div too?

[rickyboy]

Thanks, guys, for the great comments.  I wish I could say that I wrote that all by my lonesome in a monastic cell on Mt. Athos, but alas, this is a product of common thievery and only a little mild inspiration on my part.  :-)



Norman:

I assume you refer to the way to make an instance of a mixed radix number.  At first I was thinking of a CommonLispy way of doing it, like

Code Select Expand

(define-mixed-radix hhmmss ...)
Then I was wondering how to write define-mixed-radix and what namespace it was going to "pollute" with all the conversions and other operators.  Then I read Lutz's manual http://newlisp.org/downloads/newlisp_manual.html#proto_types">here and said "Ah!  This must be the newLISPy way to do this!"  So, that's theft number one.  :-)  Also, this line in Lutz's example saved me a lot of heartache:

Code Select Expand

(set 'ctx (eval ctx)) ; get context out of symbol
Thanks Lutz!



Fanda:

Touché!  That is correct about chop.  Hmmm, something tells me that I should have remembered this from http://www.alh.net/newlisp/phpbb/viewtopic.php?p=8656#8656">before. (Yup, that was me telling someone about chop.  Do you ever get the feeling sometimes that you are getting dumber as the years go on?  It happens to me too frequently.  :-)  BTW, how does Knuth's TAoCP enter into this?  Curious, 'cause I loved Seminumerical Algorithms.



cormullion:

Yes, you get all the to-* and from-* (conversion) functions for all the units you list in the mixed-radix:new call.  Look at the code for mixed-radix:new -- the conversion functions get defined by way of the sets in the dolist there.



And yes, you can mul and div them, but you have to add code yourself for that (or I can add it for you).  I put a substrate for component-wise operations at the bottom.  If you want them, put them right there -- they'll look like what's already there for add and sub, e.g.:

Code Select Expand

(define mixed-radix:mul (component-wise-operator MAIN:mul))
(define mixed-radix:div (component-wise-operator MAIN:div))


OK, here's theft number 2: I stole the idea for the unfold operator http://srfi.schemers.org/srfi-1/srfi-1.html#unfold">from Prof. Olin Shivers, but I wrote an imperative version of it and changed his optional tail-gen function to an optional post-processor post which can reach all the run-time components of the unfold call (which should make it general enough).  I think it's an improvement on tail-gen, since tail-gen can't reach the other components (i.e. the seed, the seed generator, the seed mapper, etc.).



Also, I liked how normalize turned out.  I didn't start out writing it this way.  I first wrote it with all the divs and mods, and then stepped back and said, "Hey, this is just mixrad<-low-units in drag!"  :-)  That was another one of my "duh!" moments -- the unfolder is already a normalizer, so normalizing a mixed radix is just folding it into a scalar in low units and then unfolding it back into a mixed radix!  That made the definition into a nice one-liner and I re-used some code.



Cheers,  --Rick



P.S. -- OK, that's not too much stealing, but you should see what I stole from Bob Bae (alias frontera{,000}) last week -- I should go to jail for that!  Or perhaps look into a burglar's outfit, complete with a Zorro-like mask.  :-)

[Fanda]

Thanks, guys, for the great comments.  I wish I could say that I wrote that all by my lonesome in a monastic cell on Mt. Athos, but alas, this is a product of common thievery and only a little mild inspiration on my part.  :-)

I usually don't call it a thievery, but I think about it as "being inspired by somebody else" - because, who would put it all together if not you?



*** Take all the best pieces and combine them into something brilliant ***

BTW, how does Knuth's TAoCP enter into this?  Curious, 'cause I loved Seminumerical Algorithms.

It's mentioned on the bottom of the wikipedia page in References :-)

http://en.wikipedia.org/wiki/Mixed_radix#References">http://en.wikipedia.org/wiki/Mixed_radix#References

OK, here's theft number 2: I stole the idea for the unfold operator http://srfi.schemers.org/srfi-1/srfi-1.html#unfold">from Prof. Olin Shivers, but I wrote an imperative version of it and changed his optional tail-gen function to an optional post-processor post which can reach all the run-time components of the unfold call (which should make it general enough).  I think it's an improvement on tail-gen, since tail-gen can't reach the other components (i.e. the seed, the seed generator, the seed mapper, etc.).

Yes, that's something I was wondering about, because I haven't seen it yet. I am still looking for some high-level constructs, because they seem to make life easier :-)

P.S. -- OK, that's not too much stealing, but you should see what I stole from Bob Bae (alias frontera{,000}) last week -- I should go to jail for that!  Or perhaps look into a burglar's outfit, complete with a Zorro-like mask.  :-)

I actually like if people steal from my code because it shows that there is something useful!!! :-)

[Bob Bae has to be proud about his code now ;-)]



Fanda