Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
Using modular arithmetic for the decimal byte ring,  

Compute: 5 + (- 175+222)*13 = 

This is a question I'm supposed to understand before I start a assembly language course next semester. Can someone break down the steps in getting the anwser? I assume there is more here than basic PEMDOS math.

I'm having a difficult time finding a understandable resource online for modular arithmetic on decimal byte rings. Perhaps I should just be looking at one or the other..?

share|improve this question
3  
Can you please explain what you mean by "decimal byte rings"? Is your problem above using some modulus which you did not show? –  Amzoti Dec 29 '12 at 22:51
    
In an assembler context it would make some sense to understand "byte ring" as the ring of integers modulo 256. But "decimal byte ring" is a strange specification -- the integers modulo 256 is the same ring no matter whether we notate the representatives in decimal or something else (hexadecimal? binary?) –  Henning Makholm Dec 29 '12 at 23:38
    
Still, however, even "byte ring" with the meaning I suggest above is far from standard terminology. Pray tell, where did you find this "decimal byte ring" wording? –  Henning Makholm Dec 29 '12 at 23:39
    
@Azmoti This is all of the instruction I was given by my soon to be professor.. –  user54638 Dec 29 '12 at 23:45
    
@Henning My assumption, which may not be correct, is that if 'decimal' does not matter, then it was just put in there to ensure we understand that it doesn't matter if we use a different base. there were a couple unrelated problems of a different subject where he unnecessarily stated the base of a number which made no difference in the anwser. –  user54638 Dec 29 '12 at 23:45

1 Answer 1

up vote 0 down vote accepted

After the comment thread, I believe that "the decimal byte ring" must mean arithmetic modulo 256.

This is the same as ordinary arithmetic except you take all operands, intermediate and final results mod 256. Therefore

$$ 5 + (-175+222)\times 13 = 5 + (81+222)\times 13 $$ because $-175 \bmod 256 = 81$ (in contrast to the remainder operator of many programming languages the modulus operation always produces a number between 0 and 255);

$$ \cdots = 5 + 47 \times 13 $$ because $81+222=303$ and $303 \bmod 256=47$;

$$ \cdots = 5 + 99 $$ because $47\times 13 = 611$ and $611\bmod 256=99$;

$$ \cdots = 104 $$ which is itself mod 256.


Now, instead of this we could also just use ordinary arithmetic and take mod 256 once and for all at the end:

$$5+(-175+222)\times 13 = 5+47\times 13 = 5+611 = 616$$ and then $616\bmod 256=104$ again. This works because of the general rules $$ (a\bmod N)+(b\bmod N) \bmod N = (a+b)\bmod N$$ $$ (a\bmod N)-(b\bmod N) \bmod N = (a-b)\bmod N$$ $$ (a\bmod N)(b\bmod N) \bmod N = ab\bmod N$$ In practice one will often just reduce mod 256 at strategic places in the computation where the intermediate results would get impractically large otherwise.

Division is not defined modulo 256.


The reason why this is relevant is that we can think of it as arithmetic on numbers where we only remember the bottommost 8 bits of the binary representation. This happens fairly often in practice when we do arithmetic on 32- or 64-bit values but then only store 8 bits of the result in order to save space. Each combination of 8 remembered bits conceptually represents all the infinitely many integers that end with those 8 bits; we represent this infinite set of numbers with the one it would have been if the forgotten bits were all zeroes.

The reason why division is not allowed is that it would bring some of the forgotten bits into view, and then the result would not be well-defined.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.