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

Here's an example:

CL-USER> (faro-decode 2 854) #(30 17)

blog comments powered by Disqus