mersenneforum.org > Math Residue Number System
 Register FAQ Search Today's Posts Mark Forums Read

 2009-11-22, 18:44 #1 flouran     Dec 2008 72·17 Posts Residue Number System I was wondering what the residue number representation of -1 was? (Or for negative numbers in general) Last fiddled with by flouran on 2009-11-22 at 18:47
 2009-11-22, 19:01 #2 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 102578 Posts 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. Last fiddled with by Mini-Geek on 2009-11-22 at 19:05
2009-11-22, 21:22   #3
wblipp

"William"
May 2003
New Haven

23×103 Posts

Quote:
 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.

2009-11-22, 22:34   #4
flouran

Dec 2008

72·17 Posts

Quote:
 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.

Last fiddled with by flouran on 2009-11-22 at 23:30

2009-11-22, 22:42   #5
flouran

Dec 2008

34116 Posts

Quote:
 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 $Z_{42}$.
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

Last fiddled with by flouran on 2009-11-22 at 22:44

 2009-11-22, 22:47 #6 J.F.     Jun 2008 23·32 Posts How do you figure that this is wrong? (-1,-1,-1) corresponds to (1,2,6) mod (2,3,7).
2009-11-22, 22:50   #7
flouran

Dec 2008

72×17 Posts

Quote:
 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

Last fiddled with by flouran on 2009-11-22 at 23:30

 Similar Threads Thread Thread Starter Forum Replies Last Post blistervol Miscellaneous Math 35 2012-08-18 20:17 alpertron Miscellaneous Math 17 2012-04-30 15:28 CRGreathouse Math 4 2009-03-12 16:00 JuanTutors Math 3 2004-08-01 19:07 schneelocke PrimeNet 6 2003-11-22 01:26

All times are UTC. The time now is 12:38.

Sun Jan 23 12:38:05 UTC 2022 up 184 days, 7:07, 0 users, load averages: 1.97, 1.48, 1.28