如何从残数系统转换为混合基数系统? [英] How to Convert from a Residual Number System to a Mixed Radix System?

问题描述

我了解残数系统的概念和混合基数系统，但是我很难获得在简单的案例研究中可以使用的任何转换方法

I understand the concept of a Residual Number System and the concept of a Mixed Radix system, but I'm having difficulty getting any of the conversion methods I find to work in a simple case study.

我从Knuth的计算机编程艺术开始，但是在转换理论上有点过分了，一旦提到Euler，我就迷路了.维基百科对此主题有不错的部分，我尝试了此处，但两次无法回到我的起点.

I started at Knuth's Art of Computer Programming but that had a bit too much on the theory of the conversion, and once Euler was mentioned I was lost. Wikipedia has a nice section on the subject, which I tried here and here but both times I couldn't get back to the number where I started.

我在此处(PDF)，我在此处浓缩了相关部分，但我不理解乘法逆和它们的表示法.具体来说，y_2 = |(3-19)|(1/31)| _7 | _7 = | 5 * 5 | _7尤其是| 1/31 | _7 = 5

I found a good article here (PDF), which I condensed the relevant sections here, but I don't understand the multiplicative inverses and their notation. Specifically, how y_2 = |(3 - 19)|(1/31)|_7|_7 = |5 * 5|_7 Especially how |1/31|_7 = 5

推荐答案

关于模数(此处为7)，应采用乘法逆.由于模数7是质数，所以每个数字(模7)都有一个倒数.特别地，31_7 = 3_7(因为31 = 4 * 7 +3-如果我太教sorry，对不起)，并且它的倒数是5，因为3 * 5 = 15 = 1_7.所以我们可以写 | 1/31 | _7 = 5.

The multiplicative inverses are to be taken with respect to a modulus (here 7). Since the modulus 7 is prime, every number (modulo 7) has an inverse. In particular, 31_7 = 3_7 (since 31 = 4*7 +3 - sorry if I'm too didactic), and its inverse is 5 because 3 * 5 = 15 = 1_7. So we can write |1/31|_7 = 5.

现在

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

这篇关于如何从残数系统转换为混合基数系统?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！