Residue Number System

[flouran]

I was wondering what the residue number representation of -1 was? (Or for negative numbers in general)

[Mini-Geek]

I'm guessing you mean Prime95's residue thing at the end of an LL test?
I believe it would loop around to 2^p-2, (as the mod is 2^p-1) which would be (in binary) 111...111110, which would be (in hex) [some number 1-F]...FFFE, which would make a residue of 0xFFFFFFFFFFFFFFFE (think that's the right length).
So in general: for negative numbers x, it's the residue for 2^p-1+x.

[wblipp]

Originally Posted by flouran

I was wondering what the residue number representation of -1 was? (Or for negative numbers in general)

"-1" means that number which, when added to 1, results in zero. For example, in base 12 "clock arithmetic", "-1" is another name for 11. In "modulo p" arithmetic, it is another name for p-1.

[flouran]

Originally Posted by Mini-Geek

I'm guessing you mean Prime95's residue thing at the end of an LL test?

No. Not what I was asking.

[flouran]

Originally Posted by wblipp

"-1" means that number which, when added to 1, results in zero. For example, in base 12 "clock arithmetic", "-1" is another name for 11. In "modulo p" arithmetic, it is another name for p-1.

To be more precise, I mean the residue representation of -1 in .
Wikipedia gives a somewhat decent account of what RNS is: http://en.wikipedia.org/wiki/Residue_number_system

Thus, for example, 0 in RNS would be (0,0,0). 1 in RNS is (1,1,1). 2 in RNS is (0,2,2). 3 in RNS is (1,0,3). 41 in RNS is (1,2,6).

I think perhaps -1 would be (-1,-1,-1). But that seems wrong

[J.F.]

How do you figure that this is wrong? (-1,-1,-1) corresponds to (1,2,6) mod (2,3,7).

[flouran]

Originally Posted by J.F.

How do you figure that this is wrong? (-1,-1,-1) corresponds to (1,2,6) mod (2,3,7).

Well, I personally didn't think it was wrong, but I just wanted to be sure that I was correct.

Nice to see that I was correct