math - 如何从余数系统转换为混合基数系统？

Question

我理解 Residual Number System 的概念和 Mixed Radix system 的概念，但我很难找到在简单案例研究中使用的任何转换方法。

我从高德纳 (Knuth) 的《计算机编程艺术》开始，但其中关于转换理论的内容太多了，一提到欧拉，我就迷路了。维基百科有一个 nice section关于这个问题，我试过了here和 here但两次我都无法回到开始时的数字。

我找到了一篇好文章here (PDF) ，我浓缩了相关部分here ，但我不明白乘法逆元及其符号。具体来说，y_2 = |(3 - 19)|(1/31)|_7|_7 = |5 * 5|_7 特别是 |1/31|_7 = 5

Answer 1

乘法逆元是关于模数(这里是 7)。由于模数 7 是素数，因此每个数字(模数 7)都有一个倒数。特别是 31_7 = 3_7(因为 31 = 4*7 +3 - 如果我说得太笼统，抱歉)，它的倒数是 5，因为 3 * 5 = 15 = 1_7。所以我们可以写 |1/31|_7 = 5.

现在

y_2 = |(3 - 19) |(1/31)|_7 |_7
    = | (-16) * 5 |_7
    = | 5 * 5 |_7            since -16 = (-3)*7 + 5
    = 4