
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
September 21st, 2013, 12:44 AM  #1 
Newbie Joined: Sep 2013 Posts: 8 Thanks: 0  comparison with modular arithmetic
Hi, I am working on operations( addition, subtraction, multiplication) with the residue number system instead of integers, and I have to find minimum, maximum and average of a group of numbers in their residue number representation. Could I find any way to apply comparison with modular arithmetic? I do not if (mod) operation could help or not! Thank you : ) 
September 21st, 2013, 10:52 AM  #2  
Senior Member Joined: Aug 2012 Posts: 2,409 Thanks: 753  Re: comparison with modular arithmetic Quote:
You could define the mean as the sum divided by the number of things you're adding ... for example in the integers mod 5, the mean of 1 and 3 is 2. But the mean of 1 and 4 is zero. So I don't know how helpful this is.  
September 21st, 2013, 02:33 PM  #3 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: comparison with modular arithmetic
these are difficult operations in RNS. You can add easily enough, but division won't typically be possible so I don't even know how you could take the average. Minimum and maximum are really tough, you'd almost be better off converting out of RNS, computing min/max, and converting back.

September 21st, 2013, 05:30 PM  #4 
Newbie Joined: Sep 2013 Posts: 8 Thanks: 0  Re: comparison with modular arithmetic
This is an example of a residue number system(RSN): First: you have to determine the base of modulus that you're working on to determine the range of integers that you can represent in RSN: Let's suppose the base is RNS= { 8,7,5}, all coprimes. So, the range of integers that you can represent uniquely in this RNS is: 8 * 7 * 5 = 280 ( 0 >279) Now, let we suppose that you want to convert integer (12) to RNS), you will do the following: 12 > { 12 mod 8 , 12 mod 7 , 12 mod 5} > { 4,5,2} > equivalent to 12 in decimal. 17 > { 17 mod 8 , 17 mod 7 , 17 mod 5} > { 1,3,2} > equivalent to 17 in decimal. The question is: Could I compare between 12 and 17 by using there RNS forms {4,5,2} & {1,3,2} with the help of other available information or not? BTW, I can do addition,multiplication easily if these operations help to find min/max and average. Thank you Maschke and CRGreathouse for responding, looking for great solutions Best regards, 
September 21st, 2013, 08:40 PM  #5 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: comparison with modular arithmetic
The trouble is that, philosophically, working in RNS {a1, a2, ..., ak} is basically just working mod LCM(a1, a2, ..., ak) and so there isn't really any such thing as order. In your example with bases {8, 7, 5} it's easy to see that (with 1 = (1, 1, 1) and (0, 0, 0) = 0 as usual) (7, 6, 4) + 1 = 0 and so (7, 6, 4) = 559 is also 1  everything 'wraps around' mod the LCM 560. If you have external information about how to map these to usual integers  say, to the canonical representation where each number represents the smallest nonnegative number of that residue  then you can impose an order, but there's no good way to do it from inside the RNS since it doesn't have an order on its own. 
September 22nd, 2013, 04:46 PM  #6  
Newbie Joined: Sep 2013 Posts: 8 Thanks: 0  Re: comparison with modular arithmetic Quote:
To generalise the problem, I am looking for numerical system that simplified large numbers complexity and overhead when I do operations on them? So, Is there any suggestion as an alternative of RNS, which has properties that I can do operations such as max/min and so on? Thanks!  

Tags 
arithmetic, comparison, modular 
Search tags for this page 
modular arithmetic college,comparison using modular arithmetic,modular arithmetic similarities number base arithmetic
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
modular arithmetic  Joolz  Number Theory  2  October 3rd, 2012 06:15 AM 
Modular Arithmetic  aaronmath  Number Theory  3  August 27th, 2012 08:51 AM 
Modular arithmetic  fe phi fo  Number Theory  4  May 26th, 2012 03:22 PM 
Modular arithmetic  mathslog  Number Theory  1  April 6th, 2012 03:08 PM 
Modular arithmetic help  Ciachyou  Number Theory  1  January 23rd, 2009 11:58 AM 