3
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – davidlowryduda♦ Apr 22 '11 at 23:43
8
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Why do you say the 'r = b - (a/b)'? I do not see how that can be right. Please explaining me. example. 20 % 7 --> 7 - (20/7) = 4.142... and not 6. $\endgroup$ – Mixxiphoid Apr 23 '11 at 6:46
  • 2
    $\begingroup$ 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$). $\endgroup$ – Arturo Magidin Apr 23 '11 at 7:18
  • 1
    $\begingroup$ @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. $\endgroup$ – Arturo Magidin Apr 23 '11 at 7:20
  • 2
    $\begingroup$ @Arturo Magidin: Thanks a lot for clarifying! I would give you the credit, if that was an answer :P... $\endgroup$ – Mixxiphoid Apr 23 '11 at 9:36
  • 1
    $\begingroup$ Division is not fast, it is often non-determininistic (the time to calculate will change depending on the arguments on a lot of hardware) and frequently implemented with microcode. $\endgroup$ – hythis May 3 '18 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.