When to spot uses of modulo operator

May 29, 2012 at 11:48pm
closed account (4ET0pfjN)
I understand % (mod) operator returns remainder. The only real use I know when to use it is for determining whether a value is even/odd. I would love to take advantage of it more often as I was trying to write a function that sums digits as in e.g. 1331 = 1 + 3 + 3 + 1 = 8. I managed to find the algorithm employing mod so no need for the post. So what tips and examples so that I can easily recognize when to effectively use mod operator?

My non-mod sum digits solution (not straightforward algorithm I admit):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long sumDigits_v1(const long &sumMe)
{	
	char* numToCharList = new char[1000];//to know how many zeros to divide by multiple of 10... so 1331 becomes: {'1','3','3','1'}
	long divisorList[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};//get char len via strlen to know which divisor to use
	
	itoa(sumMe, numToCharList, 10);
	
	long curDivisorIndx = strlen(numToCharList) - 1;
	long curNumToCharListIndx = 0;
	
	long sum = 0;
	
	for ( long i = curDivisorIndx, j = curNumToCharListIndx;
		i >= 0; 
		sum = sum + atol(&numToCharList[j])/divisorList[i], 
		--i, ++j);
	delete[] numToCharList;
	return sum;
}
Last edited on May 30, 2012 at 2:57am
May 29, 2012 at 11:56pm
It is really just a math question. How often do you need to find the remainder of something? For some problems it is very useful. For others, it is not at all useful.

The trickier questions come when you can manage data using integers, in which case you figure something out.
May 30, 2012 at 12:13am
When you need to find if an integer divides another integer.

The euclidian algorithm for greatest common factor uses it. The greatest common factor between two integers gcf(a,b) = gcf(b, a%b).

It can be used to limit the output of a random number function.


May 30, 2012 at 12:46am
closed account (3hM2Nwbp)
I sometimes use the modulo operator to limit how high a counter will go.

1
2
3
4
5
6
7
8
9
10
int array[20];
int i = 0;
for(int j = 0; j < 20; ++j)
{
  array[j] = i;
  i = (i + 1) % 10;  // i will be from 0 to 9
}

// array - {0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9}
May 30, 2012 at 1:54am
The Modulus operator is also used a lot in algorithms that test whether a number is prime, or primality tests. The sum of the digits in a number is the same as that number modulo 9.
Last edited on May 30, 2012 at 1:54am
May 30, 2012 at 4:23am
closed account (4ET0pfjN)
Another use of mod I use mod is generating random numbers, and I understand that if let's say let a = divident, b = divisor[/]b, then [b]a%b is b/t 0 to b - 1.

For e.g. for a pseudo random num b/t 1 - 10:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <ctime>
#include <cstdlib>

using namespace std;

int main()
{
   srand(time(0));
   int low = 1;
   int high = 10;
   
   int num = rand()%high + low;

   return 0;
}


But what if I wanted a range of let's say: 3 - 9, 2 - 9?
May 30, 2012 at 5:37am
mx760 wrote:
But what if I wanted a range of let's say: 3 - 9, 2 - 9?

Maybe int num = rand()%(high-(low-1)) +low;?
Last edited on May 30, 2012 at 5:38am
May 30, 2012 at 6:24pm
closed account (4ET0pfjN)
That would just be what I had actually...
May 30, 2012 at 6:44pm
For another example let's take a look at the world of tile based game programming. If you want to turn a one dimensional array into a two dimensional array simply:
1
2
3
4
5
for(int i = 0; i < SOME_LIMIT; i++)
{
     Tile[i]->posX = i % MAX_IN_A_ROW;
     Tile[i]->posY = i / MAX_IN_A_ROW;
}


See here when the integer 'i' equals 1, it will give the second tile in the "Tile" array a position of 1,0. But each time 'i' hits the 'MAX_IN_A_ROW' limit it will start counting at 0 again for posX but it will continue counting for posY. Does this make any sense?
May 30, 2012 at 7:31pm
closed account (4ET0pfjN)
Can someone please answer my original post, how do I generate pseudo random num in the range:

But what if I wanted a range of let's say: 3 - 9, 2 - 9?
OP by mx760

Can you elaborate, Computergeek01? That be great.
Last edited on May 30, 2012 at 7:34pm
May 30, 2012 at 7:51pm
Can someone please answer my original post, how do I generate pseudo random num in the range:


int num = rand() % 7 + 3; int num = rand() % 8 + 2;
or like naruku posted
int num = rand()%(high-(low-1)) +low;

If you seeded rand with an unsigned int, the range will be between 0 to 4,294,967,295.

Any number divided by 7 will have a maximum remainder of 6, and a minimum remainder of 0.

So (rand() % 7) + 3 will be between 3 and 9.




Last edited on May 30, 2012 at 8:15pm
May 30, 2012 at 8:01pm
What do you mean a range of 3 - 9, 2 - 9?
That looks like two very distinct ranges. Are you just giving two different examples?

Start somewhere at the beginning of main() with:
rand( time( NULL ) );

To generate a number in a range [first, last] (inclusive):
n = (rand() % (last - first + 1)) + first;

So, for example, the range 3 - 9 would be:
n = (rand() % 7) + 3;

and 2 - 9 would be:
n = (rand() % 8) + 2;

Hope this helps.
Jun 2, 2012 at 2:12pm
closed account (4ET0pfjN)
Thanks Duoas and iseeplusplus, that makes perfect sense.

Now can someone also show how to use mod to express change like convert $5.00 to amount of quarters, pennies, etc? I'm starting to be more comfortable w/ the mod operator. I also understand it's not always efficient as its really 3 operations and better to use bitwise and if divisor is power of 2 for compiler optimization.
Jun 2, 2012 at 3:54pm
You are mistaking language-level elements for optimized machine-level elements.

The compiler is smart enough to optimize things like * and / for power-of-two operations into bit shifts.
Jun 2, 2012 at 7:25pm
Here is my most complicated use of %: its a function to invert X mod N, that is, find a number Y such that X*Y=1 mod N. I guess it is an use of % exactly for what it is stands for :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int InvertModN(int X, int N)
{ int q, r, p, d; // d - divisor, q - quotient, r - remainder, p is the number to be divided
  int vD[2], vP[2], temp;
  vP[0]=1; vP[1]=0; // at any given moment, p=vP[0]*N+vP[1]*X
  vD[0]=0; vD[1]=1;   // at any given moment, d=vD[0]*N+vD[1]*X
  p=N; d=X; d%=N; if (d<0){d+=N; }
  while (d>0)
  { q=p/d;
    r=p%d;
    p=d;
    d=r;
    for(int i=0; i<2; i++)
    { temp=vP[i];
      vP[i]= vD[i];
      vD[i]= temp-q*vD[i];
    }
  }
  assert(p==1); //if X and N were relatively prime this should be so. Otherwise the function was not called properly.
  p=vP[1]%N;
  if (p<0)
    p+=N;
  return p;
}
Last edited on Jun 2, 2012 at 7:29pm
Jun 2, 2012 at 8:31pm
closed account (4ET0pfjN)
What is the purpose of your function?

Also, would some kindly explain to me Computergeek01's code posted:

1
2
3
4
5
for(int i = 0; i < SOME_LIMIT; i++)
{
     Tile[i]->posX = i % MAX_IN_A_ROW;
     Tile[i]->posY = i / MAX_IN_A_ROW;
}
Topic archived. No new replies allowed.