With 64bit operands, IMUL+SAR is between 10 and 25 times faster than IDIV on current x86 hardware. (div speed is very dependant on the values being divided. eg:

With 64bit operands, IMUL+SAR is between 10 and 25 times faster than IDIV on current x86 hardware. (div speed is very dependant on the values being divided. eg: on Sandy Bridge arch, latency is between 40 and 103 cycles.) With these deltas, the first few checks are essentially free. A large number of the numbers to check will be eliminated early and never try the expensive idiv tests.