User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 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:
 Originally Posted by abady-1 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.
Can you clarify the context of your question? There's no order relationship on the integers mod n. That's because they cycle. For example in the integers mod 5, the successor of 4 is zero. There's no way to define a sensible order relation. So you can't define min or max.

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 co-primes. 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:
 Originally Posted by CRGreathouse 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.
Thank you for this information.

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 ,

,

modular arithmetic similarities number base arithmetic

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post Joolz Number Theory 2 October 3rd, 2012 06:15 AM aaron-math Number Theory 3 August 27th, 2012 08:51 AM fe phi fo Number Theory 4 May 26th, 2012 03:22 PM mathslog Number Theory 1 April 6th, 2012 03:08 PM Ciachyou Number Theory 1 January 23rd, 2009 11:58 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      