c++ - sacar - Algoritmo de división de enteros

residuo de una division en c++

Question

Estaba pensando en un algoritmo en la división de grandes números: dividiendo con el resto bigint C por bigint D, donde conocemos la representación de C en la base b, y D es de la forma b ^ k-1. Probablemente sea lo más fácil de mostrar en un ejemplo. Intentemos dividir C = 21979182173 por D = 999.

• Escribimos el número como conjuntos de tres dígitos: 21 979 182 173
• Tomamos sumas (módulo 999) de conjuntos consecutivos, comenzando desde la izquierda: 21 001 183 356
• Añadimos 1 a los conjuntos que preceden a los que "pasamos de 999": 22 001 183 356

De hecho, 21979182173/999 = 22001183 y el resto 356.

He calculado la complejidad y, si no me equivoco, el algoritmo debería funcionar en O (n), siendo n el número de dígitos de C en la representación de la base b. También he hecho una versión muy cruda y no optimizada del algoritmo (solo para b = 10) en C ++, lo probé con el algoritmo de división de enteros general de GMP y realmente parece que es mejor que GMP. No pude encontrar nada como esto implementado en ninguna parte, así que tuve que recurrir a las pruebas contra la división general.

Encontré varios artículos que discuten lo que parecen ser asuntos similares, pero ninguno de ellos se concentra en implementaciones reales, especialmente en bases diferentes a 2. Supongo que eso se debe a la forma en que los números se almacenan internamente, aunque el algoritmo mencionado parece útil para, digamos, b = 10, incluso teniendo eso en cuenta. También intenté contactar a otras personas, pero, de nuevo, fue en vano.

Por lo tanto, mi pregunta sería: ¿hay un artículo o un libro o algo donde se describa el algoritmo antes mencionado, posiblemente discutiendo las implementaciones? Si no, ¿tendría sentido para mí intentar e implementar y probar un algoritmo de este tipo en, digamos, C / C ++ o este algoritmo es intrínsecamente malo?

Además, no soy programador y, si bien estoy razonablemente bien en la programación, no tengo mucho conocimiento de los "elementos internos" de las computadoras. Por lo tanto, perdone mi ignorancia: es muy posible que haya una o más cosas muy estúpidas en este post. Lo siento una vez más.

¡Muchas gracias!

Aclaración adicional de los puntos planteados en los comentarios / respuestas:

Gracias a todos, ya que no quería comentar todas las respuestas y consejos excelentes con la misma cosa, me gustaría abordar un punto que muchos de ustedes tocaron.

Soy plenamente consciente de que trabajar en las bases 2 ^ n es, en general, claramente la forma más eficiente de hacer las cosas. Casi todas las bibliotecas de Bigint usan 2 ^ 32 o lo que sea. Sin embargo, ¿qué pasaría si (y, enfatizo, sería útil solo para este algoritmo en particular?) Implementamos bigints como una matriz de dígitos en base b? Por supuesto, requerimos que b sea "razonable": b = 10, el caso más natural, parece bastante razonable. Sé que es más o menos ineficiente tanto en memoria como en tiempo, teniendo en cuenta cómo se almacenan internamente los números, pero he podido, si mis pruebas (básicas y posiblemente defectuosas) son correctas, producir resultados más rápido que la división general de GMP, lo que daría sentido a la implementación de tal algoritmo.

Ninefingers avisos que tendría que usar en ese caso una operación de módulo costosa. Espero que no: puedo ver si antiguo + nuevo se cruzó, por ejemplo, 999, solo mirando el número de dígitos de antiguo + nuevo + 1. Si tiene 4 dígitos, hemos terminado. Más aún, dado que antiguo <999 y nuevo <= 999, sabemos que si antiguo + nuevo + 1 tiene 4 dígitos (no puede tener más), entonces (antiguo + nuevo)% 999 equivale a eliminar el dígito más a la izquierda de ( old + new + 1), que supongo que podemos hacer a un precio bajo.

Por supuesto, no estoy discutiendo las limitaciones obvias de este algoritmo ni reclamo que no se pueda mejorar; solo se puede dividir con cierta clase de números y tenemos que saber a priori la representación del dividendo en la base b. Sin embargo, para b = 10, por ejemplo, este último parece natural.

Ahora, digamos que hemos implementado bignums como lo describí anteriormente. Diga C = (a_1a_2 ... a_n) en la base b y D = b ^ k-1. El algoritmo (que probablemente podría estar mucho más optimizado) sería así. Espero que no haya muchos errores tipográficos.

• si k> n, obviamente hemos terminado
• agregue un cero (es decir, a_0 = 0) al comienzo de C (en caso de que intentemos dividir, por ejemplo, 9999 con 99)
• l = n% k (mod para enteros "regulares" - no debería ser demasiado caro)
• old = (a_0 ... a_l) (el primer conjunto de dígitos, posiblemente con menos de k dígitos)
• para (i = l + 1; i <n; i = i + k) (Tendremos piso (n / k) o así iteraciones)
  • nuevo = (a_i ... a_ (i + k-1))
  • nuevo = nuevo + antiguo (esto es una adición de bigint, por lo tanto O (k))
  • aux = nuevo + 1 (de nuevo, adición de bigint - O (k) - que no me agrada)
  • si aux tiene más de k dígitos
    • borrar primer dígito de aux.
    • antiguo = antiguo + 1 (adición de bigint una vez más)
    • rellene el antiguo con ceros al principio, de modo que tenga tantos dígitos como debería
    • (a_ (ik) ... a_ (i-1)) = old (si i = l + 1, (a _ 0 ... a _ l) = old)
    • nuevo = aux
  • llene el nuevo con ceros al principio, de modo que tenga tantos dígitos como debería
  • (a_i ... a_ (i + k-1) = nuevo
• quot = (a_0 ... a_ (n-k + 1))
• rem = nuevo

Allí, gracias por discutir esto conmigo, como dije, me parece que es un algoritmo interesante de "casos especiales" para intentar implementar, probar y discutir, si nadie ve fallas fatales en él. Si es algo no ampliamente discutido hasta ahora, aún mejor. Por favor déjame saber lo que piensa. Disculpas por el mensaje tan largo.

Además, solo algunos comentarios más personales:

@Ninefingers: De hecho, tengo un conocimiento (muy básico) de cómo funciona GMP, qué hace y de los algoritmos generales de división bigint, así que pude entender gran parte de su argumento. También estoy consciente de que GMP está altamente optimizado y en cierto modo se personaliza para diferentes plataformas, por lo que no estoy tratando de "vencerlo" en general, eso parece tan fructífero como atacar un tanque con un palo puntiagudo. Sin embargo, esa no es la idea de este algoritmo, funciona en casos muy especiales (que GMP no parece cubrir). En una nota no relacionada, ¿estás seguro de que las divisiones generales se realizan en O (n)? Lo más que he visto hacer es M (n). (Y eso, si lo entiendo correctamente, en la práctica (Schönhage – Strassen, etc.) no puede alcanzar O (n). El algoritmo de Fürer, que aún no alcanza a O (n), es, si estoy en lo cierto, casi puramente teórico.)

@Avi Berger: En realidad, esto no parece ser exactamente lo mismo que "echar fuera nueve", aunque la idea es similar. Sin embargo, el algoritmo mencionado debería funcionar todo el tiempo, si no me equivoco.

Answer 1

Si necesita dividirse con frecuencia por el mismo divisor, usarlo (o una potencia de él) ya que su base hace que la división sea tan barata como el desplazamiento de bits es para los enteros binarios base 2.

Podrías usar la base 999 si quieres; no hay nada especial en el uso de una base de potencia de 10, excepto que hace que la conversión al entero decimal sea muy barata. (Puede trabajar una extremidad a la vez en lugar de tener que hacer una división completa sobre el entero entero. Es como la diferencia entre convertir un entero binario en decimal en lugar de convertir cada 4 bits en un dígito hexadecimal. Binario -> hex puede comenzar con los bits más significativos, pero la conversión a bases sin potencia de 2 tiene que ser LSB, primero utilizando la división.)

Por ejemplo, para calcular los primeros 1000 dígitos decimales de Fibonacci (10 ⁹ ) para una pregunta de golf de código con un requisito de rendimiento, mis 105 bytes de respuesta de código de máquina x86 usaron el mismo algoritmo que esta respuesta de Python : la habitual a+=b; b+=a a+=b; b+=a iteración de Fibonacci, pero se divide por (una potencia de) 10 cada vez que a vuelve demasiado grande.

Fibonacci crece más rápido que la propagación del acarreo, por lo que descartar los dígitos decimales bajos ocasionalmente no cambia los dígitos altos a largo plazo. (Mantienes unos cuantos extras más allá de la precisión que quieres).

La división por una potencia de 2 no funciona, a menos que mantengas un registro de cuántas potencias de 2 has descartado, porque la eventual conversión binaria -> decimal al final dependerá de eso.

Por lo tanto, para este algoritmo, debe realizar una adición de precisión extendida y una división por 10 (o la potencia de 10 que desee).

Almacené base-10 ⁹ extremidades en elementos enteros de 32 bits. Dividir por 10 ⁹ es trivialmente barato: solo un incremento de puntero para omitir la extremidad baja. En lugar de hacer un memmove realidad, simplemente memmove el puntero utilizado en la siguiente iteración de adición.

Creo que la división por una potencia de 10 que no sea 10 ^ 9 sería algo barata, pero requeriría una división real en cada extremidad, y propagar el resto a la siguiente extremidad.

La adición de precisión extendida es algo más costosa de esta manera que con las extremidades binarias, porque tengo que generar el procesamiento manualmente con una comparación: sum[i] = a[i] + b[i]; carry = sum < a; (comparación sin firmar). Y también ajuste manualmente a 10 ^ 9 en función de esa comparación, con una instrucción de movimiento condicional. Pero pude usar ese arrastre como una entrada para adc (instrucción x86 add-with-carry).

No necesita un módulo completo para manejar la envoltura además de la adición, porque sabe que ha envuelto como máximo una vez.

Esto desperdicia un poco más de 2 bits de cada extremidad de 32 bits: 10 ^ 9 en lugar de 2^32 = 4.29... * 10^9 . El almacenamiento de 10 dígitos de base por byte sería significativamente menos eficiente en espacio y mucho peor para el rendimiento, porque una adición binaria de 8 bits cuesta lo mismo que una adición binaria de 64 bits en una CPU moderna de 64 bits.

Tenía como objetivo el tamaño del código: para un rendimiento puro, habría utilizado extremidades de 64 bits con una base de 10 ^ 19 "dígitos". ( 2^64 = 1.84... * 10^19 , así que esto desperdicia menos de 1 bit por cada 64). Esto le permite realizar el doble de trabajo con cada instrucción de add hardware. Hmm, en realidad esto podría ser un problema: la suma de dos extremidades podría envolver el entero de 64 bits, por lo que solo verificar por > 10^19 ya no es suficiente. Puede trabajar en la base 5*10^18 , o en la base 10^18 , o hacer una detección de remoción más complicada que verifique el arrastre binario así como el arrastre manual.

Almacenar BCD empaquetado con un dígito por 4 bits de mordisco sería aún peor para el rendimiento, porque no hay soporte de hardware para bloquear el transporte de un mordisco a otro dentro de un byte.

En general, mi versión se ejecutó aproximadamente 10 veces más rápido que la versión de precisión extendida de Python en el mismo hardware (pero tenía espacio para una optimización significativa de la velocidad, al dividir con menos frecuencia). (70 segundos u 80 segundos frente a 12 minutos)

Aún así, creo que para esta implementación particular de ese algoritmo (donde solo necesitaba la adición y la división, y la división ocurrió después de cada una de las pocas adiciones), la elección de las extremidades base-10 ^ 9 fue muy buena. Hay algoritmos mucho más eficientes para el número Nth Fibonacci que no necesitan hacer mil millones de adiciones de precisión extendida.

Answer 2

Siento la necesidad de agregar a esto basado en mi comentario. Esto no es una respuesta, sino una explicación sobre el fondo.

Una biblioteca bignum usa lo que se llama extremidades: busca mp_limb_t en la fuente gmp, que generalmente es un campo de enteros de tamaño fijo.

Cuando haces algo como la suma, una forma (aunque ineficiente) de acercarte es hacerlo:

doublelimb r = limb_a + limb_b + carryfrompreviousiteration

Esta extremidad de tamaño doble atrapa el desbordamiento de limb_a + limb_b en el caso de que la suma sea mayor que el tamaño de la extremidad. Entonces, si el total es mayor que 2 ^ 32 si estamos usando uint32_t como el tamaño de nuestra extremidad, se puede detectar el desbordamiento.

¿Porqué necesitamos esto? Bueno, lo que normalmente haces es recorrer todas las extremidades; lo has hecho tú mismo al dividir tu entero y repasar cada una, pero primero lo hacemos con LSL (por lo tanto, la extremidad más pequeña primero) como harías la aritmética a mano.

Esto puede parecer ineficiente, pero esta es solo la forma C de hacer las cosas. Para realmente romper las armas grandes, x86 tiene adc como una instrucción - agregue con carry. Lo que esto hace es una aritmética y en sus campos y establece el bit de acarreo si la aritmética supera el tamaño del registro. La próxima vez que add o adc , los factores del procesador en el bit de acarreo también. En la resta se llama la bandera de préstamo.

Esto también se aplica a las operaciones de cambio. Como tal, esta característica del procesador es crucial para lo que hace que bignums sea rápido. Así que el hecho es que hay circuitos electrónicos en el chip para hacer esto, hacerlo en software siempre va a ser más lento.

Sin entrar en demasiados detalles, las operaciones se desarrollan a partir de esta capacidad de sumar, cambiar, restar, etc. Son cruciales. Ah, y usa el ancho completo del registro de su procesador por rama si lo está haciendo bien.

Segundo punto - conversión entre bases. No puede tomar un valor en medio de un número y cambiar su base, porque no puede explicar el desbordamiento del dígito debajo de él en su base original, y ese número no puede explicar el desbordamiento del dígito debajo. .. y así. En resumen, cada vez que desee cambiar la base, debe volver a convertir todo el bignum de la base original a su nueva base. Así que tienes que caminar el bignum (todas las extremidades) al menos tres veces. O, alternativamente, detecte desbordamientos costosos en todas las demás operaciones ... recuerde, ahora necesita hacer operaciones de módulo para resolver si se desbordó, mientras que antes el procesador lo estaba haciendo por nosotros.

También me gustaría agregar que si bien lo que tienes es probablemente rápido para este caso, ten en cuenta que como una gran biblioteca, gmp hace un buen trabajo para ti, como la administración de memoria. Si estás usando mpz_ , estás usando una abstracción sobre lo que he descrito aquí, para empezar. Finalmente, gmp usa un ensamblaje optimizado a mano con bucles desenrollados para casi todas las plataformas que haya escuchado, y más. Hay una muy buena razón por la que se envía con Mathematica, Maple et al.

Ahora, solo como referencia, material de lectura.

• Aritmética computacional moderna es un trabajo similar a Knuth para bibliotecas de precisión arbitrarias.
• Donald Knuth, Seminumerical Algorithms (El Arte de la Programación por Computadora, Volumen II).
• El blog de William Hart sobre la implementación de algoritmos para bsdnt en el que analiza varios algoritmos de división. Si está interesado en las bibliotecas bignum, este es un excelente recurso. Me consideré un buen programador hasta que empecé a seguir este tipo de cosas ...

En resumen, las instrucciones de ensamblaje de la división apestan, por lo que las personas generalmente calculan inversos y se multiplican, como lo hacen al definir la división en aritmética modular. Las diversas técnicas que existen (ver MCA) son en su mayoría O (n).

Edición: Ok, no todas las técnicas son O (n). La mayoría de las técnicas llamadas div1 (dividir por algo que no es más grande que una extremidad son O (n). Cuando creces, obtienes complejidad O (n ^ 2); esto es difícil de evitar.

Ahora, ¿podrías implementar bigints como una matriz de dígitos? Pues sí, por supuesto que podrías. Sin embargo, considere la idea justo debajo de la adición

/* you wouldn''t do this just before add, it''s just to 
   show you the declaration.
 */
uint32_t* x = malloc(num_limbs*sizeof(uint32_t));
uint32_t* y = malloc(num_limbs*sizeof(uint32_t));
uint32_t* a = malloc(num_limbs*sizeof(uint32_t));
uint32_t m;

for ( i = 0; i < num_limbs; i++ )
{
    m = 0;
    uint64_t t = x[i] + y[i] + m;
    /* now we need to work out if that overflowed at all */
    if ( (t/somebase) >= 1 ) /* expensive division */
    {
        m = t % somebase; /* get the overflow */
    }
}

/* frees somewhere */

Eso es un bosquejo aproximado de lo que está buscando para agregar a través de su esquema. Así que tienes que ejecutar la conversión entre bases. Así que necesitarás una conversión a tu representación para la base, luego volverás cuando hayas terminado, porque esta forma es muy lenta en cualquier otro lugar . No estamos hablando de la diferencia entre O (n) y O (n ^ 2) aquí, pero estamos hablando de una instrucción de división costosa por extremidad o de una conversión costosa cada vez que quiera dividir . Ver esto

A continuación, ¿cómo expandes tu división para la división de casos generales? Con eso, quiero decir cuando quieres dividir esos dos números x e y del código anterior. No se puede, es la respuesta, sin recurrir a instalaciones basadas en bignum, que son caras. Ver Knuth. Tomar módulo un número mayor que su tamaño no funciona.

Dejame explicar. Intente 21979182173 mod 1099. Supongamos aquí por simplicidad que el campo de mayor tamaño que podemos tener es de tres dígitos . Este es un ejemplo artificial, pero el mayor tamaño de campo que conozco si utiliza 128 bits con las extensiones gcc. De todos modos, el punto es, tú:

21 979 182 173

Divide tu número en miembros. Entonces tomas módulo y suma:

21 1000 1182 1355

No funciona Aquí es donde Avi es correcto, porque es una forma de expulsar nueves, o una adaptación de las mismas, pero no funciona aquí porque nuestros campos se han desbordado para empezar, estás usando el módulo para asegurarte de que cada campo permanezca dentro su tamaño de miembro / campo.

Entonces, ¿cuál es la solución? ¿Dividir su número en una serie de bignums de tamaño apropiado? ¿Y comenzar a usar las funciones de bignum para calcular todo lo que necesitas? Esto va a ser mucho más lento que cualquier forma existente de manipular los campos directamente.

Ahora tal vez solo está proponiendo este caso para dividir por una extremidad, no un bignum, en cuyo caso puede funcionar, pero la división de hensel y los inversos precomputados, etc., lo hacen sin el requisito de conversión . No tengo idea si este algoritmo sería más rápido que, por ejemplo, la división de hensel; Sería una comparación interesante; el problema viene con una representación común en toda la biblioteca bignum . La representación elegida en las bibliotecas de bignum existentes es por las razones que he ampliado: tiene sentido en el nivel de ensamblaje, donde se realizó por primera vez.

Como nota al margen; no tienes que usar uint32_t para representar tus extremidades. Utiliza un tamaño idealmente el tamaño de los registros del sistema (por ejemplo, uint64_t) para poder aprovechar las versiones optimizadas para ensamblajes. Entonces, en un sistema adc rax, rbx 64 bits adc rax, rbx solo establece el desbordamiento (CF) si el resultado sobrepasa 2 ^ 64 bits.

tl; versión de dr : el problema no es tu algoritmo o idea; es el problema de convertir entre bases, ya que la representación que necesita para su algoritmo no es la forma más eficiente de hacerlo en add / sub / mul, etc. Para parafrasear knuth: Esto le muestra la diferencia entre la elegancia matemática y la eficiencia computacional.

Answer 3

Su algoritmo es una variación de un algoritmo de base 10 conocido como "expulsión de nueves". Su ejemplo es usar base 1000 y "expulsar" 999''s (uno menos que la base). Esto solía enseñarse en la escuela primaria como una forma de hacer una comprobación rápida de los cálculos manuales. Tuve un profesor de matemáticas de la escuela secundaria que estaba horrorizado al saber que ya no se enseñaba y nos llenó.

Lanzar 999''s en base 1000 no funcionará como un algoritmo de división general. Generará valores congruentes módulo 999 para el cociente real y el resto, no los valores reales. Su algoritmo es un poco diferente y no he comprobado si funciona, pero se basa en el uso efectivo de la base 1000 y el divisor es 1 menos que la base. Si quisiera probarlo para dividir entre 47, primero tendría que convertirlo a un sistema de base de 48 números.

Google "arrojando nueves" para más información.

Edición: originalmente leí tu publicación un poco demasiado rápido, y lo sabes como un algoritmo de trabajo. Como @Ninefingers y @Karl Bielefeldt han expresado más claramente que yo en sus comentarios, lo que no está incluido en su estimación de rendimiento es la conversión a una base apropiada para el divisor particular en cuestión.