# fastest way to calculate the remainder (modular)

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

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

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.01secs.. But if there isn't a really fast method, I just have to be happy with the fastest :).

-
I'm having trouble understanding. You are trying to find the remainder when you divide a large integer by another integer, and so you use the 'mod' operation? What computer language are you coding this in (as different languages handle this differently)? Many even have a '%' operation, which is the actual mod. Further, many will round a/b down automatically as well. –  mixedmath Apr 22 '11 at 23:43

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.
Your formula is incorrect: it should be $r = a - (a/b)b$, where $a/b$ is integer division (i.e., the largest $q$ such that $qb \leq a$). –  Arturo Magidin Apr 23 '11 at 7:18
@Mixxiphoid: You need to do integer division, nor rational division: the integer division of $a$ by $b$ is the floor of $a/b$; it equals that largest integer $q$ such that $qb\leq a$. Brandon's formula should be r = a-(a/b)*b, where $a/b$ is integer division. For example, if $a=20$ and $b=7$ so you want the remainder of $20$ modulo $7$, then integer division 20/7 is 2 (since $2\times 7\leq 20$, but $3\times 7\gt 21$), so $r = a - (a/b)b = 20 - (20/7)7 = 20-2(7) = 6$. Integer division is the usual division that computers can do, via repeated subtraction. –  Arturo Magidin Apr 23 '11 at 7:20