64 bits por división de 32 bits

Busco una forma rápida de realizar el siguiente Divison:64 bits por división de 32 bits

dividendos es un poco entero de 64.
Divisor es un entero de 32 bits con signo.
El cociente debe ser un entero de 64 bits con signo, el resto no es necesario.
Low dword of the dividend is zero.

estoy usando sólo 32 bits tipos de datos, ya que el 64 los bits son poco compatibles con el compilador, y ningún montaje. La precisión puede verse un tanto comprometida a favor de la velocidad.

¿Alguna sugerencia en este caso?

Fuente

2010-08-12 uj2

Si tus 32 bits más bajos son 0, entonces no tendrás un resto de todos modos. – ysap

@ysap: No es cierto. Considere '(1L << 32)/3'. –

Tengo curiosidad, ¿está utilizando un procesador de 32 bits, con un compilador de C razonablemente actualizado, que no admite bien los enteros de 64 bits? ¿Qué es esta combinación frustrante? – mctylr

La división 64/32 es soportada directamente por i386 y posiblemente por otras máquinas, siempre que la palabra alta del dividendo sea menor que el divisor (es decir, el dividendo esté en el rango de 32x32-> 64 multiplica por el divisor) Si su compilador tiene soporte mínimo para tipos de 64 bits, puede reconocer esta situación y aprovecharla.

Suponiendo que ya ha comprobado el asm generado y ha descubierto que no lo aprovecha, o si sabe que su CPU no tiene dicha instrucción de división, entonces simplemente necesita hacer una división larga como aprendió en escuela primaria ... excepto que es base-4294967296 en lugar de base-10.

Puede intentar leer la fuente en libgcc, ya que contiene el código para la división 64/64 para máquinas que no tienen soporte nativo.

Editar: En realidad, dado que no tiene una operación de división 64/32, es posible que desee utilizar base-65536. Esto se debe a que la división larga ingenua requiere dividir un número de "2 dígitos" por un número de "1 dígito" en cada paso. Por supuesto, ahora estás atrapado haciendo más pasos ..

Fuente

2010-08-13 06:58:04

Knuth tiene una discusión sobre la división larga, y describe el algoritmo de división larga. Si vas por el camino de mirar eso, Knuth tiene una optimización donde puedes abandonar el ciclo antes de tiempo. Es muy difícil de probar, solo ayuda en un pequeño número de casos y puede omitirse de manera segura. – janm

Respuesta

Cuestiones relacionadas