64 bit by 32 bit division

Question

I am looking for a fast way to perform the following divison:

• Dividend is a signed 64 bit integer.
• Divisor is a signed 32 bit integer.
• Quotient should be a signed 64 bit integer, remainder is unnecessary.
• Low dword of the dividend is zero.

I am using only 32 bit data types, since 64 bit ones are poorly supported by the compiler, and no assembly. Accuracy can be somewhat compromised in favor of speed.

Any pointers on this one?

Answer 1

64/32 division is supported directly by i386 and possibly other machines, as long as the high word of the dividend is less than the divisor (i.e. the dividend is in the range of a 32x32->64 multiply by the divisor). If your compiler has minimal support for 64 bit types, it may be able to recognize this situation and take advantage of it.

Assuming you've already checked the generated asm and found that it does not take advantage of this, or if you know your cpu does not have such a division instruction, then you simply need to do long division like you learned in grade school.. except that it's base-4294967296 instead of base-10.

You might try reading the source to libgcc, since it contains code for 64/64 division for machines that don't have native support.

Edit: Actually, since you don't have a 64/32 divide operation, you may want to use base-65536. This is because naive long division requires dividing a "2-digit" number by a "1-digit" number at each step. Of course, now you're stuck doing more steps..