When to spot uses of modulo operator

[mx760]

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):

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;
}

[Duthomhas]

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.

[htirwin]

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.

[3hM2Nwbp]

I sometimes use the modulo operator to limit how high a counter will go.

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}

[Numeri]

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.

[mx760]

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:

#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?

[naraku9333]

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;?

[mx760]

That would just be what I had actually...

[Computergeek01]

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:

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?

[mx760]

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.

[htirwin]

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.

[Duthomhas]

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.

[mx760]

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.

[Duthomhas]

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.

[tition]

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 :)

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;
}

[mx760]

What is the purpose of your function?

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

for(int i = 0; i < SOME_LIMIT; i++)
{
     Tile[i]->posX = i % MAX_IN_A_ROW;
     Tile[i]->posY = i / MAX_IN_A_ROW;
}