[Math] fastest way to calculate the remainder (modular)

modular arithmetic

I'm creating a computer application in which I need to be able to calculate the remainder of large numbers (more then $30$ digits). I was searching the Internet for the fastest way to calculate this, but no luck.

I tried one way:
Condition:
$\ a \ 'Modulus' \ b$

  1. $b$ must be smaller than $a$

Calculation: 

a / b = x
round x upwards = y  
b - ((y * b) - a) = remainder

If x is a round number, there is no remainder.

Now I have $2$ questions:

  1. Is my method (always) correct?
  2. Is there any faster way?

Thanks in advance!
Mixxiphoid

EDIT:
This is a homework project and I needed to make my own modulus function. That explains why I cannot use the $\%$. Also I builded in a check in my code whether the number was rounded downwards or upwards. If downwards, I'll add $1$.

I know computers can calculate these things fast, yet I want the most simple straight forward method to calculate this, since the numbers I use can become really big. And eventually dividing a big number costs $0.01$secs.. But if there isn't a really fast method, I just have to be happy with the fastest :).

Best Answer

You can't find information on the fastest way to calculate because it is one of the quickest operations that can be done on a computer. Using integer division (i.e. $\frac a b = \lfloor \frac a b \rfloor$), the modulo operation is just $r = a - (\frac a b) b$. In practice this can be done in tens of computer clock cycles, which is almost instantaneous. In general, whenever library functions are available for some function you should use those over anything you can write on your own; they are often the fastest known algorithms and optimized by the compiler. As mentioned in a comment above, most languages contain a modulo operation by default.

Related Question