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

  • 0
    I'm havi$n$g trouble u$n$derstanding. 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.2011-04-22

1 Answers 1

8

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.

  • 0
    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.2018-05-03