3

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.

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.

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

Ry-
  • 218,210
  • 55
  • 464
  • 476
eyepatch
  • 85
  • 6

1 Answers1

1

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.

Now

y_2 = |(3 - 19) |(1/31)|_7 |_7
    = | (-16) * 5 |_7
    = | 5 * 5 |_7            since -16 = (-3)*7 + 5
    = 4
lmsteffan
  • 840
  • 4
  • 13
  • I now understand how you get |-16|_7 = 5, that's an unusual way of handling negative modulus in my experience, but I can work with that. I'm still lost on this |(1/31)|_7 = 5 business. I understand that |31|_7 = |3|_7, but I'm not following you on the inverse. 3 * 5 = 15, but |15|_7 = 0. – eyepatch Apr 12 '13 at 19:55
  • ahem... 15 = 2*7 + 1, therefore |15|_7 =1. – lmsteffan Apr 12 '13 at 20:27