Timeline for Efficiently checking if a number is divisible by 3
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 5, 2014 at 18:48 | comment | added | Voo |
It's true that the best way to write this in Java is to just use i % 3 == 0, but certainly not because an idiv instruction is particularly efficient. It's horribly inefficient (we can do with a multiplication and a shift) as a matter of fact and we can do much better, but a good compiler will do this for you. gcc certainly does, but I'm not sure if HotSpot does the same.
|
|
| Jun 3, 2014 at 18:59 | comment | added | Jerry Coffin |
By "this approach", I meant the OP's approach, not the i%3==0 (which I agree is pretty obviously correct--which is why I used it to create the "gold" value in my answer). As to clock efficiency: not saying his approach is more efficient, just that I can imagine there being at least one processor on which it could be.
|
|
| Jun 3, 2014 at 18:54 | comment | added | 200_success |
@JerryCoffin 1) If n % 3 == 0 is not the most obviously correct implementation, then I don't know what will convince you. 2) I've added more justification about clock efficiency. Also see benchmarks.
|
|
| Jun 3, 2014 at 18:47 | history | edited | 200_success | CC BY-SA 3.0 |
Added clock latency data
|
| Jun 3, 2014 at 18:32 | history | edited | 200_success | CC BY-SA 3.0 |
Intel IDIV instruction
|
| Jun 2, 2014 at 22:26 | comment | added | Jerry Coffin | On most processors, getting a remainder uses a division operation. If this approach worked correctly (I'm not sure it does) it's just barely possible that it could end up a little faster than using division. That would probably depend on the underlying processor though. | |
| Jun 2, 2014 at 22:08 | history | edited | 200_success | CC BY-SA 3.0 |
Added opcode dumps
|
| Jun 2, 2014 at 22:01 | history | answered | 200_success | CC BY-SA 3.0 |