How do you implement the remainder method % for integers in java? How fast is it?

Question

Naive implementation: if you want to find p % q, subtract q from p until you get a number < q. This takes p/q subtractions, and p/q comparisons.

How does Java actually do this, and how fast is it?

Java does it by asking the CPU to do it, and it is fast. How fast? Well, relative to what??? — Andreas, May 28 '16 at 10:15
I don't think this is a duplicate, because the question is asked in the context of Java. There is more going on when JVM gets involved. — Sergey Kalinichenko, May 28 '16 at 10:25

score 3 · Accepted Answer · edited May 23 '17 at 12:22

When Java compiler sees % operator, it generates one of the typed rem bytecode instructions, e.g. irem, lrem, frem, drem, etc. The actual instruction depends on the type. For two ints the instruction is irem.

These instructions get interpreted by JVM, producing CPU actions for obtaining the remainder.

Most CPUs these days (at least, the ones capable of running Java) have built-in instructions that take a divisor and a dividend, and produce a quotient and remainder pair. That is why % operator is as fast as the division operator /.

See this Q&A for information on how the instruction itself may be implemented in the CPU.

score 0 · Answer 2 · answered May 28 '16 at 12:13

How does Java actually do this

Java uses the underlying CPU instruction.

how fast is it?

Most CPUs support integer division which also produces a remainder. The original 8086 did this. This is not cheap but it is O(1) in terms of time in modern CPUs.

Note: -5 % 3 = -2 i.e. -5 = -1 * 3 + -2

How do you implement the remainder method % for integers in java? How fast is it?

2 Answers2