9th January 2016
I recently had an application in which I wanted to encode two positive integers, a and b, as a single encoded integer, c, with the following constraints:
- Usually the two integers would be small (less than 100), but they could each be as large as a million.
- The encoded integer c should be as small as possible.
- It should be possible to decode the integers without any additional information.
For example, one possible solution is to calculate 1000000 * a + b, but this doesn't satisfy the second condition, because for a=1 and b=2, c will be 1000002.
The solution I came up with I've called Faro-Encoding, named after the Faro Shuffle, the technique for interleaving two piles of cards into a single pile. It forms the basis for many card tricks.
The Faro-Encoding works as follows:
- Express the two numbers in binary.
- Interleave the two bitstrings, right-aligned, so their bits alternate.
- Convert the result to a decimal integer.
The Faro-Encode routine encodes two or more numbers:
(defun faro-encode (&rest numbers) (let ((n (length numbers)) (base 1) (result 0)) (loop (when (every #'zerop numbers) (return result)) (dotimes (i n) (incf result (* base (logand (nth i numbers) 1))) (setf (nth i numbers) (ash (nth i numbers) -1)) (setq base (* 2 base))))))
Here's an example:
CL-USER> (faro-encode 30 17) 854
The Faro-Decode routine takes an extra parameter to specify how many numbers have been encoded, and returns an array of the results:
(defun faro-decode (n encoded) (let ((a (make-array n :initial-element 0)) (base 1)) (loop (when (zerop encoded) (return a)) (dotimes (i n) (multiple-value-bind (d r) (truncate encoded 2) (when (plusp r) (incf (aref a i) base)) (setq encoded d))) (setq base (* 2 base)))))
Here's an example:
CL-USER> (faro-decode 2 854) #(30 17)
blog comments powered by Disqus