mersenneforum.org > Math Residue Number System
 User Name Remember Me? Password
 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 2·3·23·31 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

237310 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

72·17 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 02:50.

Thu Dec 1 02:50:32 UTC 2022 up 105 days, 19 mins, 0 users, load averages: 0.82, 0.78, 0.85

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔