Reverse Translation Analysis

Three values are required to define the relationship between a residue number system and a mixed radix number system for any particular radix. These are the residue digit, res, the mixed radix digit,dig, and the carry, cry. If you know any two of these values you can determine what the other one must be.

The relationship can be expressed in the following python code which takes a carry digit and a residue digit and returns a mixed radix digit.

The function takes the carry and residue digits as arguments and returns the mixed radix digit. It can be reversed by storing its output in an array and then sorting the array by different keys according to the values desired to be used as inputs or as outputs. That requires R**2 storage for any module R.

If dif=mod(res-cry,rads[rind), then we can write:

By calculating dif outside the function, we can reduce the storage required for the reverse conversion from R**2 to R for any module, but sacrifice some speed.

The function also takes the rind input which is an index into two arrays of constants needed for the computation. These constants only need to be computed once and stored as part of a translation program. The arrays are invs, the list of multiplication inverses needed for the translation and rads, the list of radices.

As a personal convention, I almost always use the first few primes as radices, start with the smallest, and list them left to right.

You can translate a number from residue to a mixed radix notation by iterating the cel function over a range of residue digits.

Polynomial number systems make it easy to determine the magnitude of a number. Residue number systems: not so much. You generally have to decode the whole number before you have an idea of the magnitude of a residue number. In polynomial number systems, you only have to look at the most significant digit to derive a range of possible values of the whole number. Looking at the same number from both a polynomial and residue perspective might be advantageous.

Mixed radix notation is, of course, a polynomial numbering system with the same radices as a residue number system. Using radices of 3, 5, and 7, we can express numbers to a range of 105. The residue digits for 77 would be 2, 2, and 0, and the mixed radix digits would be 2, 0, and 5. In this mixed radix system, the least significant digit would be worth one, the next digit would be worth 3, and most significant digit would be worth 15. 77=2+15*5, and 77 is 2 mod 3, 2 mod 5, and zero mod 7.

Translation analysis takes a list of residue/mixed radix pairs and determines if they match. Forward translation analysis starts with the smallest mixed radix radix and reverse translation analysis starts from the largest. Forward translation analysis amounts to translating the residue number into mixed radix and checking that it matches the given mixed radix digits. Reverse translation analysis starts with the largest mixed radix digit. If we follow certain rules, subsequent stages of the algorithm will not change the most significant mixed radix digits, so a list of residue/mixed radix pairs can be checked with previous entries.

At any stage of the reverse analysis it is possible to determine what residue/mixed pairs can be used in the next state of the analysis without conflicting with more significant pairs. In general for a residue number of N radices, you can choose any residue/mixed pairs you want for the most significant digits, but there comes a point where the options diminish rapidly, then disappear altogether.

If we know the most significant residue digit and the most significant mixed radix digit, then we also know the carry digit. Any previous total must have the same residue digit as the carry. That means for a radix Rn where we have selected the carry, the possible totals have been reduced by a ratio of 1/Rn.

At the next stage of the algorithm, we find the carry for the next smaller mixed radix to be S. The R carry from the first stage will change for the second stage, but we can calculate that the new value T will be from the mixed radix digit for the second stage. With this information we can reduce the total possibilities for new values for the third stage to 1/(Rn*Rn-1). The process can continue for as many digit pairs a desired.

Below is a table of the decode process for 61267.

The left six columns of the table are the residue digits of the values produced by the decode process as each successive residue digit is processed starting with the 1 in the radix 3 column. The window is the forward product of the residue modules. The range is the reverse product of the residue modules. The window is the possible range of decodes. The range is the possible range of carries.

The carry column contains the decoded carries. The carry for the last row is 16 because we are only using the one residue digit of 16 for the decode. 102 is the decoded carry for 11, 0 using modules 13 and 17 and 52 is the decoded carry for 1,0,8 using 11, 13, and 17.

If the range of carry is greater than the window of decodes, the translation can't proceed any farther. If the window is 1155 and the range is 2431, then any carry greater than 1155 would mean the list of pairs produces a carry greater than the window and can't be expressed as an integer. We can look at this table as a set of two overlapping triangular matrices, and we can reproduce any row of the right triangular matrix using only information from residue/mixed pairs that are as significant, or more significant than row desired. So any conclusions we draw about value of a set of top pairs using that information can also be applied to all their children where the children are further translated less significant pairs.

The information in the table below was derived from lists of pairs analyzed in this top-down manner. Notice that it exactly matches the information derived from a forward translation shown above.

Here is the reverse translation python code that produced the above results:

The routine takes a list of residue digits, a list of mixed radix digits, and a count as arguments. The count in the number of residue/mixed pairs to analyze. The routine starts with the most significant pair and computes the carry for the next level. Then it computes the carry for the next most significant pair and adjusts the more significant digits of the carry according the digit and the residue value of the number that the digit would add to the total in a forward translation.

I will close with a larger table for a different number. Sometimes the patterns are easier to see if you use larger numbers.