Lispology

About me

Feeds

Faro-encoding numbers

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

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.

Faro-Encode

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

Faro-Decode

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