My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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 : )
abady-1 is offline  
 
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.
Maschke is online now  
September 21st, 2013, 02:33 PM   #3
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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,
abady-1 is offline  
September 21st, 2013, 08:40 PM   #5
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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!
abady-1 is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
arithmetic, comparison, modular



Search tags for this page
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 aaron-math 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





Copyright © 2019 My Math Forum. All rights reserved.