La forma más rápida de calcular un entero de 128 bits módulo un entero de 64 bits

9 minutos de lectura

avatar de usuario
usuario200783

Tengo un entero A sin signo de 128 bits y un entero B sin signo de 64 bits. ¿Cuál es la forma más rápida de calcular A % B – ¿Ese es el resto (64 bits) de dividir A por B?

Estoy buscando hacer esto en C o en lenguaje ensamblador, pero necesito apuntar a la plataforma x86 de 32 bits. Desafortunadamente, esto significa que no puedo aprovechar el soporte del compilador para enteros de 128 bits, ni la capacidad de la arquitectura x64 para realizar la operación requerida en una sola instrucción.

Editar:

Gracias por las respuestas hasta ahora. Sin embargo, me parece que los algoritmos sugeridos serían bastante lentos: ¿no sería la forma más rápida de realizar una división de 128 bits por 64 bits aprovechar el soporte nativo del procesador para la división de 64 bits por 32 bits? ¿Alguien sabe si hay una manera de realizar la división más grande en términos de unas pocas divisiones más pequeñas?

Re: ¿Con qué frecuencia cambia B?

Principalmente, estoy interesado en una solución general: ¿qué cálculo realizaría si es probable que A y B sean diferentes cada vez?

Sin embargo, una segunda situación posible es que B no varíe con tanta frecuencia como A; puede haber hasta 200 As para dividir entre cada B. ¿Cómo diferiría su respuesta en este caso?

  • ¿Con qué frecuencia cambia B?

    – usuario287792

    4 de abril de 2010 a las 16:28

  • ¿Qué tan rápido debe funcionar? ¿Cuántas operaciones de módulo de 128 por 64 por segundo espera?

    – GJ.

    10 de abril de 2010 a las 18:09

  • El algoritmo de Russian Peasant es simple pero usa bucles y no aprovecha la instrucción de división en x86. Puede usar el algoritmo aquí, se trata de una división de 64/32 bits por una instrucción de división de 32/16 bits, pero puede duplicarlo a 128/64 bits por 64/32 bits

    – phuclv

    29 de enero de 2014 a las 2:57

  • Si las respuestas quieren probar su código, esta respuesta wiki está disponible.

    – chux – Reincorporar a Monica

    22/09/2016 a las 18:47

  • El código tiene un error. Es interesante que no se informó en 6 años. Tratar A=2, B=1 va a bucle infinito. 0x8711dd11 mod 0x4388ee88 falla (resultado s/b 1, no 0x21c47745) así como otros. Sugerir while (X < A/2) –> while (X <= A/2) reparar. Tu pseudocódigo probado unsigned cafMod(unsigned A, unsigned B) { assert(B); unsigned X = B; while (X < A / 2) { X <<= 1; } while (A >= B) { if (A >= X) A -= X; X >>= 1; } return A; }

    – chux – Reincorporar a Monica

    31 de agosto de 2016 a las 18:49

  • @chux: Tienes toda la razón, arreglado. Probablemente no se informó antes porque solo sucede cuando A = 2ⁿ B o A = 2ⁿ B + 1. ¡Gracias!

    – café

    1 de septiembre de 2016 a las 1:13


  • Sí, en x86 asm implementando x<<=1 como add lo,lo/adc mid,mid/… es más eficiente que shl lo/rcl mid,1/… Pero en C el compilador debería hacer eso por ti. Por supuesto, en x86 asm, deberías usar bsr (escaneo de bits) o lzcnt (recuento de ceros a la izquierda) para encontrar la posición del bit establecido más alto, luego use shld hi, mid2, cl / … / shl low, cl para hacer todos los cambios en un solo paso en lugar de hacer un bucle para ese primero while (x <= A/2) lazo. En el modo de 32 bits, es tentador usar SSE2 para cambios XMM SIMD con elementos de 64 bits, especialmente para reducir la bifurcación para conteos de cero inicial >= 32

    – Peter Cordes

    17 de julio de 2019 a las 14:52

  • Gracias, creo que entiendo cómo los algoritmos descritos en sputsoft.com se aplican a esta situación. AFAICT, el algoritmo G muestra cómo realizar una división de mb-bit por nb-bit como una serie de divisiones de m-n+1 (n+1)b-bit por nb-bit, donde b es el número de bits por dígito. Luego, el algoritmo Q muestra cómo realizar cada una de estas (n+1) divisiones de b bits por nb bits como una única división de 2 b bits por b bits. Dado que el mayor dividendo que podemos manejar es de 64 bits, debemos establecer b=32. Por lo tanto, los algoritmos dividen nuestra división de 128 bits por 64 bits (m = 4, n = 2) en 3 divisiones de 64 bits por 32 bits. ¿Suena esto exacto?

    – usuario200783

    10 de abril de 2010 a las 12:40

  • Puedo decir que ya ha pensado más detalladamente en los algoritmos que yo cuando publiqué mi respuesta, por lo que no puedo decir con certeza si su recuento final de operaciones de división es correcto. Sin embargo, creo que tienes la idea básica de cómo proceder.

    – Dale Hagglund

    10 de abril de 2010 a las 14:36

  • Otro pensamiento: es posible que desee considerar dígitos de 16 bits si está escribiendo en C y, por lo tanto, no tiene acceso directo a las instrucciones de multiplicación 32b x 32b -> 64b, o no desea incrustar sus dígitos de 32 bits en un entero de 64 bits y utiliza la aritmética de 64 bits integrada del propio compilador. No puedo pensar en una razón sólida para evitar esto último, pero es posible que desee verificar el código ensamblador generado, si está realmente, realmente, realmente preocupado por la velocidad.

    – Dale Hagglund

    10 de abril de 2010 a las 14:42

  • Ese enlace de sputsoft parece no ser válido ahora. No estoy seguro de por qué, el sitio todavía está allí. Esta página parece estar conectado, en el sentido de que el kanooth-numbers biblioteca una vez fue llamada sputsoftnumbers.

    –Craig McQueen

    4 de septiembre de 2013 a las 4:50


  • La página de sputsoft ahora se encuentra aquí: janmr.com/blog/2009/08/…

    – Cheng Sun

    30 de julio de 2017 a las 20:53

  • @GJ, si el compilador admite enteros de 64 bits, será más fácil usar la operación mod para enteros de 64 bits. El método de caf es el que usa MSVC de todos modos para x86 de 32 bits, según mi evaluación superficial del ensamblaje. También incluye una optimización para dividendos por debajo de 2^32. Por lo tanto, puede codificarlo usted mismo o simplemente usar el soporte del compilador existente.

    – MSN

    5 de abril de 2010 a las 16:21

  • No estoy seguro de entender cómo funciona esto. B es de 64 bits, por lo que (AH % B) y ((2^64 – B) % B)) serán de 64 bits. ¿No nos dará un número de 128 bits al multiplicarlos juntos, dejándonos aún con la necesidad de realizar un módulo de 128 bits por 64 bits?

    – usuario200783

    10 de abril de 2010 a las 12:54

  • Gracias por la idea de ver cómo los compiladores implementan módulos de 64 bits por 64 bits en x86. Por lo que puedo decir, ni GCC (la función __udivmoddi4 en libgcc2.c) ni MSVC (ver ullrem.asm para la versión sin firmar) usan el método “Russian Peasant” de caf. En cambio, ambos parecen usar una variación del algoritmo Q en el enlace proporcionado por Dale Hagglund (con n = 2, b = 32), aproximando la división de 64 bits por 64 bits usando una división de 64 bits por 32 bits. , luego realice un ligero ajuste para corregir el resultado si es necesario.

    – usuario200783

    10 de abril de 2010 a las 14:02

  • Problema con este enfoque: El * la multiplicación necesita un resultado de 128 bits para hacer el último paso some_128_bit_positive_value % some_128_bit_positive_value y estamos de vuelta donde empezamos. Pruebe 0x8000_0000_0000_0000_0000_0000_0000_0000 mod 0xFFFF_FFFF_FFFF_FFFE. Diría que la respuesta debería ser 2, pero su algoritmo da 0 (suponiendo que el producto de su multiplicación es módulo de 64 bits). Este código funciona para “entero de 128 bits módulo a entero de 32 bits”. Tal vez mi prueba sea incorrecta, pero me gustaría saber el resultado de su prueba.

    – chux – Reincorporar a Monica

    31 de agosto de 2016 a las 20:01

  • @chux: Estoy de acuerdo en que la respuesta debería ser 2 por 0x80000000000000000000000000000000 % 0xFFFFFFFFFFFFFFFE. lo probé en calcla calculadora de precisión arbitraria cmdline. Confirmé que truncar a 64 bits (con un AND bit a bit con (2^64-1)) rompe la fórmula, por lo que esencialmente lo deja en el cuadrado 1. (((AH % B) * ((2^64 - B) % B))&(2^64-1) + (AL % B))&(2^64-1) % B == 0 pero (((AH % B) * ((2^64 - B) % B)) + (AL % B)) % B == 2. solía AH=A>>64 y AL=0.

    – Peter Cordes

    1 de septiembre de 2016 a las 9:01

  • Creo que tu pensamiento es más o menos correcto. Sí, también se conoce la idea de usar la división de punto flotante de doble precisión x87, pero el x87 solo admite la división de 63 bits porque el bit 64 está reservado para el signo de mantisa de acuerdo con: IEEE Standard 754 for Binary Floating-Point Arithmetic.

    – GJ.

    11 de abril de 2010 a las 7:03

  • Estaba hablando del formato de doble extensión compatible con x87. En formato doble, la fracción tiene solo 53 bits de longitud. En el extendido la fracción o más bien la mantisa tiene una longitud de 64 bits. Hay una diferencia entre este formato y los más pequeños. En formato extendido, el bit inicial de la mantisa es explícito a diferencia de los dobles o simples, pero no creo que cambie mucho. Debería ser posible almacenar exactamente enteros de 64 bits en este formato. El signo se almacena en el bit 79 en formato extendido.

    – Maciej Hehl

    11 de abril de 2010 a las 10:55

  • He comprobado el estándar IEEE y tienes razón. El signo de la mantisa se almacena en el último byte.

    – GJ.

    11 de abril de 2010 a las 16:13

  • Lo que describe es la llamada división de casos base como la describe Knuth en su algoritmo D (TAOCP Vol. 2). Se basa en el hecho de que si divide los dos “dígitos” superiores del dividendo por el dígito superior del divisor, el resultado es como máximo 2. Esto se prueba restando el resultado * divisor del dividendo/resto y ver si es negativo. Si es así, sumas el divisor y corriges el cociente hasta que el resto vuelve a ser positivo. Luego realiza un bucle para el siguiente dígito inferior, etc.

    – Rudy Velthuis

    14/03/2013 a las 12:30


  • Estar de acuerdo (((AH % B) * ((2^64 - B) % B)) + (AL % B)) % B tiene problemas

    – chux – Reincorporar a Monica

    31 de agosto de 2016 a las 20:03

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad