Algoritmo de división

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de febrero de 2022; las comprobaciones requieren 13 ediciones .

El algoritmo de división es un algoritmo que calcula para dos enteros dados y su cociente y/o resto, el resultado de la división con un resto de . Algunos de los algoritmos están diseñados para cálculos manuales, otros se implementan en circuitos digitales y software. $norte$ $D$

Los algoritmos de división se dividen en dos grandes categorías: división lenta y división rápida. Los algoritmos de división lenta producen un dígito del resultado por iteración. Ejemplos de división lenta son los algoritmos de división con recuperación , sin recuperación y SRT . Los métodos de división rápida comienzan aproximando el cociente final y producen el doble de dígitos en el resultado final en cada iteración. Los algoritmos de Newton-Rapson y Goldschmidt entran en esta categoría.

Las variantes de estos algoritmos permiten el uso de algoritmos de multiplicación rápida . Como resultado, para números enteros grandes, el tiempo de cálculo requerido para la división será el mismo (hasta un factor constante) que el tiempo requerido para realizar la multiplicación, cualquiera que sea el algoritmo de los enumerados que no se aplique.

La discusión utilizará la notación donde ${\ estilo de visualización N/D = (Q, R)}$

$norte$ - numerador (dividendo)
$D$ - denominador (divisor)

son números de entrada, y

$q$ - privado
$R$ - resto

son la salida.

División por resta

El algoritmo más simple, históricamente integrado en el algoritmo del máximo común divisor y presentado en los Principia de Euclides , Libro VII Proposición 1, encuentra el resto de una división de dos números enteros positivos usando solo la resta y la comparación:

R : = N mientras que R >= D hacer R : = R − D final retorno R

La prueba de que el cociente y el resto existen y son únicos (descrito en el artículo División con resto ) da un algoritmo de división completo basado en sumas, restas y comparaciones:

función dividir ( N , D ) si D = 0 entonces error ( DivisionByZero ) terminar si D < 0 entonces ( Q , R ) : = dividir ( N , − D ); volver ( − Q , R ) terminar si N < 0 entonces ( Q , R ) : = dividir ( − N , D ) si R = 0 entonces volver ( − Q , 0 ) si no volver ( − Q − 1 , D − R ) end end -- Aquí N >= 0 y D >= 0 devuelven divide_unsigned ( N , D ) end función divide_unsigned ( N , D ) Q : = 0 ; R : = N while R >= D do Q : = Q + 1 R : = R − D fin volver ( Q , R ) fin

Este procedimiento siempre da . Al ser muy simple, el algoritmo requiere pasos y, por lo tanto, es exponencialmente más lento que algoritmos como la división larga. El algoritmo es útil si se sabe que (los pasos) son pocos (dependiendo del volumen de salida). $R\geqslant0$ ${\ estilo de visualización \ Omega (Q)}$ $q$

División de columnas

La división larga es un algoritmo estándar de números decimales de varios dígitos que se utiliza para la división con lápiz y papel. Se desplaza gradualmente de izquierda a derecha desde el dividendo, restando el mayor múltiplo posible del divisor en cada paso. El multiplicador se convierte en un cociente y la diferencia final se convierte en el resto de la división.

Cuando el algoritmo se usa en base 2, este método forma la base para dividir números naturales con un resto. La división corta es una variante de la división larga, adecuada para dividir por un solo dígito. El algoritmo de decremento , también conocido como el método del cociente fraccionario, es un tipo de división por columna menos eficiente, pero es más fácil de entender. Permitir que se reste un múltiplo más grande que el que se hace en cada paso permite más libertad para crear variantes de división larga.

División de enteros (sin signo) con resto

El algoritmo anterior, una versión binaria de la conocida división en longitud , divide colocando el cociente en y el resto en . Todos los valores se tratan como enteros sin signo. $norte$ $D$ $q$ $R$

si D = 0 entonces error ( DivisionByZeroException ) end -- División por cero Q : = 0 -- Los valores iniciales del cociente y resto son 0 R : = 0 para i : = n − 1 .. 0 do -- Aquí n es un bit numérico en N R : = R << 1 -- Desplazamiento a la izquierda de R en 1 bit R ( 0 ) : = N ( i ) -- Iguala el bit menos significativo de R al bit i del dividendo si R >= D entonces R : = R − D Q ( i ) : = 1 fin fin Ejemplo

Toma ( ) y ( ) ${\ estilo de visualización N = 1100_{2}}$ ${\ estilo de visualización 12_ {10))$ $D=100_{2}$ ${\ estilo de visualización 4_ {10))$

Paso 1 : Establecer R = 0 y Q = 0
Paso 2 : Tomar i = 3 (uno menos que el número de bits en N)
Paso 3 : R = 00 (cambiar 1 a la izquierda)
Paso 4 : R = 01 (poner R (0 ) igual a N(i))
Paso 5 : R < D, omita el comando

Paso 2 : Establecer i = 2
Paso 3 : R = 010
Paso 4 : R = 011
Paso 5 : R < D, omitir comando

Paso 2 : Establecer i = 1
Paso 3 : R = 0110
Paso 4 : R = 0110
Paso 5 : R >= D, se ejecuta el comando
Paso 5b : R = 10 (R−D)
Paso 5c : Q = 10 (establecer Q(i) igual a 1)

Paso 2 : Establecer i = 0
Paso 3 : R = 100
Paso 4 : R = 100
Paso 5 : R >= D, se ejecuta el comando
Paso 5b : R = 0 (R−D)
Paso 5c : Q = 11 (establecer Q(i) igual a 1)

Fin ( ) y .
$Q=11_{2}$ ${\ estilo de visualización 3_ {10))$ $R=0$

Métodos de división lenta

Todos los métodos de división lenta se basan en la relación de recurrencia estándar [1]

R_{j+1}=B\veces R_{j}-q_{n-(j+1)}\veces D,

dónde:

${\ Displaystyle R_ {j}}$ es el j-ésimo resto parcial de la división
B es la base del número (generalmente igual a 2 en computadoras y calculadoras)
${\ Displaystyle q_ {n-(j+1)))$ es el dígito del cociente en la posición , donde las posiciones de los dígitos se numeran desde los dígitos menos significativos (0) hasta los dígitos más significativos ( ) ${\ estilo de visualización n-(j+1)}$ $n-1$
$norte$ − número de caracteres en privado
$D$ − divisor

División de Restauración

La división reconstructiva funciona con números fraccionarios de punto flotante y depende de una suposición . ${\ estilo de visualización 0<D<N}$

Los números privados se forman a partir del conjunto . $q$ $\{0,1\}$

Algoritmo de recuperación básico para binario (base 2):

R : = N D : = D << n -- R y D deben ser palabras dos veces más largas que N y Q para i : = n − 1 .. 0 do -- Por ejemplo, 31..0 para R de 32 bits : = 2 * R − D -- Resta de prueba del valor desplazado (multiplicar por 2 es un cambio en la interpretación binaria) si R >= 0 entonces q ( i ) : = 1 -- El resultado es el bit 1 sino q ( i ) : = 0 -- El resultado es el bit 0 R : = R + D -- El nuevo resto parcial es igual al valor desplazado (restaurado) end end -- Aquí: N = dividendo, D = divisor, n = número de bits, R = resto parcial, q(i) = bit #i del cociente

La variante del algoritmo que no implementa lo retiene explícitamente y, por lo tanto , no necesita volver a agregarse en el caso de . ${\ estilo de visualización 2R}$ $D$ ${\ estilo de visualización R <0}$

División no restauradora

La división sin restauración usa un conjunto de dígitos para los dígitos del cociente en lugar de . El algoritmo es más complejo, pero tiene la ventaja cuando se implementa en chips de que solo hay una decisión y una suma/resta por bit de cociente. No hay un paso de recuperación después de la resta, lo que puede reducir el número de operaciones a la mitad y permite que el algoritmo se ejecute más rápido [2] . Algoritmo de división sin restauración para números positivos binarios (base 2): ${\ estilo de visualización \ {-1,1 \}}$ $\{0,1\}$

R : = N D : = D << n -- R y D deben ser palabras dos veces más largas que N y Q para i = n − 1 .. 0 do -- Por ejemplo, 31..0 para 32 bits si R > = 0 entonces q [ i ] : = + 1 R : = 2 * R − D otra cosa q [ i ] : = − 1 R : = 2 * R + D final si final -- Aquí: N = dividendo, D = divisor, n = número de bits, R = resto parcial, q(i) = bit #i del cociente.

Si seguimos este algoritmo, obtenemos el cociente en un formato no estándar, que consta de los números -1 y +1. Este formulario debe convertirse a formato binario. Ejemplo:

Convertir cociente a dígitos : $\{0,1\}$
Comienzo:	$Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}$
1. Formamos un término positivo:	${\ estilo de visualización P = 11101010 \,}$
2. Formamos un término negativo:	${\ estilo de visualización M = 00010101 \,}$
3. Reste: : ${\ estilo de visualización PM}$	${\ estilo de visualización Q = 11010101 \,}$
El término negativo se representa en inversa binaria , no en complemento a dos.

Si los caracteres −1 se almacenan como ceros (0), como en la representación habitual, entonces el cálculo es trivial: realiza un complemento bit a bit (un bit se reemplaza por el complemento de un bit) del original . $q$ $PAGS$ $q$ $METRO$ $q$

Q : = Q − bit . bnot ( Q ) -- Si los dígitos −1 en Q se representan como ceros.

Finalmente, los cocientes calculados por este algoritmo siempre son impares y el resto R está dentro de . Por ejemplo, . Para llevarlo a un resto positivo, tomamos un paso de recuperación después de que se haya reducido de una forma no estándar a una estándar: $-D\leqslant R\leqslant D$ ${\ estilo de visualización 5/2 = 3R-1}$ $q$

si R < 0 entonces Q : = Q − 1 R : = R + D termina si

El verdadero resto es R >> n. Al igual que con la recuperación, los bits menos significativos se usan en el mismo orden en que se forman los bits del cociente , y tiene sentido usar un solo cambio de registro para ambos números al mismo tiempo. $R$ $q$

División de la SRT

La división lleva el nombre de las primeras letras de los nombres de los creadores (Sweeney, Robertson, Tocher). La división SRT es un método de división popular en muchos microprocesadores [3] [4] . La división es similar a la división sin recuperación, pero usa una tabla de búsqueda basada en el dividendo y el divisor para determinar el cociente.

La diferencia más significativa es que se utiliza una representación redundante para lo privado. Por ejemplo, si se implementa la división en base 4 de SRT, cada dígito del cociente se elige entre cinco posibilidades : . En vista de esto, la elección del dígito del cociente no tiene por qué ser exacta. Más tarde, las cifras del cociente se pueden corregir. Por ejemplo, pares de dígitos y son equivalentes porque . Esta tolerancia le permite seleccionar los dígitos del cociente basándose solo en los pocos bits más significativos del dividendo y el divisor, en lugar de restar por la longitud total. Esta simplificación, a su vez, permite el uso de una base para números mayores de 2. ${\ estilo de visualización \ {-2,-1,0,+1,+2\))$ ${\ estilo de visualización {0,+2}}$ ${\ estilo de visualización {1,-2}}$ $0{\times }4+2=1{\times }4-2$

Al igual que la división sin restauración, los pasos finales son restar la longitud total de los números para obtener el último bit del cociente y convertir el cociente a binario estándar.

El infame error de división flotante en los procesadores Intel Pentium fue causado una tabla de búsqueda codificada incorrectamente. Cinco de las 1066 celdas de la tabla se omitieron por error [5] [6] .

Métodos de división rápida

División de Newton-Rapson

La división de Newton-Rapson usa el método de Newton para encontrar el recíproco de un número y multiplica ese recíproco por para encontrar el cociente resultante . $D$ $norte$ $q$

Pasos de división de Newton-Rapson:

Calculamos la aproximación por el recíproco del divisor . $X_{0}$ ${\ estilo de visualización 1/D}$ $D$
Calculamos sucesivamente aproximaciones más precisas del recíproco. Este es el lugar donde, de hecho, se utiliza el método de Newton-Rapson. ${\displaystyle X_{1},X_{2},\ldots,X_{S))$
Calculamos el cociente multiplicando el dividendo por el inverso del divisor: . $Q=NX_{S}$

Para aplicar el método de Newton para encontrar el recíproco de un número, necesitas encontrar una función que tenga cero en el punto . Obviamente, esta función es , pero las iteraciones de Newton-Rapson no son exitosas para ella, ya que no se pueden realizar sin conocer el recíproco del número (además, el método intenta calcular el recíproco exacto en un solo paso, y no hacer mejoras iterativas ). La función que funciona es aquella para la que la iteración de Newton-Rapson da $D$ $f(X)$ ${\ estilo de visualización X = 1/D}$ ${\ estilo de visualización f (X) = DX-1}$ $D$ ${\ estilo de visualización f (X) = (1/X)-D}$

X_{i+1}=X_{i}-{f(X_{i}) \sobre f'(X_{i})}=X_{i}-{1/X_{i}-D \ sobre -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),

que se puede calcular usando solo una multiplicación y una resta o dos multiplicaciones- sumas . $X_{yo}$

Desde un punto de vista computacional, las expresiones y no son equivalentes. Para obtener una precisión de 2n bits utilizando la segunda expresión, debe calcular el producto entre y con doble precisión hasta la precisión especificada ( n bits). Por el contrario, el producto debe calcularse solo con una precisión de n bits, ya que los n bits iniciales (después del punto binario) son cero. $X_{i+1}=X_{i}+X_{i}(1-DX_{i})$ $X_{i+1}=X_{i}(2-DX_{i})$ $X_{yo}$ ${\ estilo de visualización (2-DX_ {i})}$ $X_{yo}$ $X_{yo}$ ${\ estilo de visualización (1-DX_ {i})}$ ${\ estilo de visualización (1-DX_ {i})}$

Si el error se define como , entonces ${\ estilo de visualización \ varepsilon _ {i} = 1-DX_ {i}}$

{\begin{alineado}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\ &=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i)) ^{2}.\\\end{alineado}}

Este error cuadrático en cada paso de iteración (la llamada convergencia cuadrática del método de Newton-Rapson) tiene el efecto de que el número de dígitos correctos en el resultado se duplica aproximadamente para cada iteración , una propiedad que se vuelve extremadamente importante cuando los números encontrados tienen muchos dígitos. . Pero también significa que la convergencia inicial del método puede ser relativamente lenta, especialmente si el valor se elige mal. $X_{0}$

Para el subproblema de elegir una estimación inicial, es conveniente aplicar un desplazamiento al divisor para que quede entre , mientras que al dividendo se le aplica el mismo desplazamiento para que el cociente no cambie. Entonces uno puede usar la Aproximación Lineal en la forma $X_{0}$ $D$ $0{,}5\leqslant D\leqslant 1$ $norte$

X_{0}=T_{1}+T_{2}D\aprox. {\frac{1}{D}}\,

para inicializar el método de Newton-Rapson. Para minimizar el error absoluto máximo de esta aproximación en el intervalo , se debe usar ${\ estilo de visualización [0{,} 5,1]}$

X_{0}={48 \más de 17}-{32 \más de 17}D.\,

Los coeficientes de aproximación lineal se definen como sigue. El valor absoluto del error es . El mínimo del valor absoluto máximo del error se determina de acuerdo con el teorema de oscilación equivalente de Chebyshev aplicado a . El mínimo local de la función estará en el punto donde , que tiene solución . La función en este mínimo debe tener un valor con signo opuesto con respecto a los puntos extremos del intervalo, a saber, . Dos igualdades en dos incógnitas dan una única solución y , y el error máximo es . Al usar esta aproximación, el valor absoluto del error del valor inicial es menor que $|\varepsilon _{0}|=|1-D(T_{1}+T_{2}D)|$ $F(D)=1-D(T_{1}+T_{2}D)$ ${\ estilo de visualización F (D)}$ $F'(D)=0$ $D=-T_{1}/(2T_{2})$ $F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))$ ${\ estilo de visualización T_ {1} = 48/17}$ $T_{2}=-32/17$ ${\ estilo de visualización F (1) = 1/17}$

\vert \varepsilon _{0}\vert \leqslant {1 \over 17}\approx 0{,}059.\,

Es posible formar un polinomio de grado superior a 1 calculando los coeficientes según el algoritmo de Remez . Luego, la aproximación inicial requiere más cálculo, lo que puede compensarse con un número menor de iteraciones de Newton-Rapson.

Dado que la convergencia de este método es exactamente cuadrática, se sigue que es suficiente

S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17))\right\lceil \,

pasos para calcular el valor hasta lugares binarios. Esto es equivalente a 3 para IEEE sencillos y 4 para dobles y dobles extendidos . $PAGS\,$

Pseudocódigo

El siguiente pseudocódigo calcula el cociente de N y D , hasta P dígitos binarios:

Expresar D como donde (representación de punto flotante estándar) // convertir a un valor entre 0,5 y 1, lo que se puede hacer desplazando bits / restando el exponente // constantes precalculadas con la misma precisión que los tiempos de repetición de D // se pueden calcular en anticipo para una P fija devolución final

{\displaystyle M\veces 2^{e))

{\ estilo de visualización 1 \ leqslant M <2}

D^{\prime }{\dos puntos}=D/2^{e+1}

N^{\prime }{\dos puntos}=N/2*{e+1}

X{\colon }=48/17-32/17\times D^{\prime }

\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,

X{\colon }=X+X\times (1-D^{\prime }\times X)

N^{\prime }\veces X

Por ejemplo, para la división de punto flotante de doble precisión, este método utiliza 10 multiplicaciones, 9 sumas y 2 desplazamientos.

Variantes de la división de Newton-Rapson

El método de división de Newton-Rapson se puede modificar para que sea un poco más rápido. Después de cambiar N y D para que D esté en el intervalo [0.5, 1.0], inicializamos con

X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right )

Esta es la mejor aproximación cuadrática y da un valor de error absoluto de como máximo . Los parámetros se eligen de forma que se elija un error igual al valor del tercer orden del polinomio de Chebyshev de primera especie. Los coeficientes deben calcularse previamente y codificarse en el método. ${\frac{1}{D))$ ${\ estilo de visualización 1/99}$

Luego, en el ciclo, usamos una iteración que eleva el error a un cubo.

E:=1-D\cdot X

Y:=X\cdot E

X:=X+Y+Y\cdot E

Si el bucle se ejecuta hasta que se acerca a los bits iniciales, entonces el número de iteraciones será como máximo $X$ ${\ estilo de visualización 1/D}$ $PAGS$

\left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil

que es igual al número de veces 99 al cubo para obtener . Después ${\ estilo de visualización 2^{P+1}}$

Q:=N\cdot X

es igual al cociente hasta bits. $PAGS$

El uso de polinomios de mayor grado en inicializaciones o iteraciones da como resultado un impacto en el rendimiento, ya que sería mejor utilizar multiplicaciones adicionales para hacer más iteraciones.

División de Goldschmidt

La división de Goldschmidt [7] (Robert Elliott Goldschmidt) usa un proceso iterativo de multiplicar repetidamente el dividendo y el divisor por el mismo factor , elegido para que el divisor converja a 1. Esto hace que el dividendo converja al cociente : $F_{yo}$ $q$

Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots}}{F_{\ldots}}}

Pasos de la división de Goldschmidt:

Generamos una aproximación para el multiplicador . $F_{yo}$
Multiplica el dividendo y el divisor por . $F_{yo}$
Si el divisor está lo suficientemente cerca de 1, devuelve el dividendo; de lo contrario, vuelve al paso 1.

Suponga escalado al valor , cada uno basado en : ${\ estilo de visualización N/D}$ ${\ estilo de visualización 0 <D <1}$ $F_{yo}$ $D$

F_{i+1}=2-D_{i}.

Multiplicamos el dividendo y el divisor por el factor y obtenemos:

{\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1} {F_{i+1}}}.

Después de un número suficiente de iteraciones . $k$ ${\ Displaystyle Q = N_ {k}}$

El método Goldschmidt se utiliza en los procesadores AMD Athlon y posteriores [8] [9] . También se conoce como el algoritmo Anderson Earle Goldschmidt Powers (AEGP) y se implementa en varios procesadores de IBM [10] [11] . Aunque la convergencia del método es la misma que la de la implementación de Newton-Rapmon, una de las ventajas del método de Goldschmidt es que las multiplicaciones en el numerador y el denominador se pueden realizar en paralelo [11] .

Teorema del binomio

El método de Goldschmidt se puede utilizar con factores que permitan la simplificación con el binomio de Newton . Supongamos que N/D se multiplica por una potencia de dos de modo que . Elegimos y . Esto da $D\in ({\tfrac {1}{2)),1]$ ${\ estilo de visualización D = 1-x}$ $F_{i}=1+x^{2^{i))$

{\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+ x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1 +x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\aprox. 1} }

Después de los pasos , el denominador se puede redondear con un error relativo $norte$ $(x\in [0,{\tfrac {1}{2))))$ ${\ estilo de visualización 1-x^{2^{n}}}$ $una$

\varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}

que tiene un valor máximo en , proporcionando una precisión mínima en dígitos binarios. ${\ estilo de visualización 2 ^ {-2 ^ {n}}}$ $x={1 \sobre 2}$ $2^{n}$

Métodos para números grandes

Los métodos destinados a ser implementados en hardware no suelen contar con números enteros con miles o millones de dígitos decimales, lo cual es común, por ejemplo, en cálculos de módulo en criptografía . Para estos números grandes, los algoritmos más eficientes convierten el problema en el uso de una pequeña cantidad de multiplicaciones, lo que se puede hacer con algoritmos de multiplicación asintóticamente eficientes , como el algoritmo de Karatsuba , la multiplicación de Tum-Cook o el algoritmo de Schönhage-Strassen . Como resultado , la complejidad computacional de la división será del mismo orden (hasta la multiplicación por una constante) que la multiplicación. Los ejemplos incluyen la reducción a la multiplicación de Newton como se describe anteriormente [12] , así como los algoritmos ligeramente más rápidos de la división de Bournickel-Ziegler [ 13] , Baret y Montgomery [14] . El método de Newton, en particular, es efectivo en escenarios donde se deben realizar múltiples divisiones por un número determinado, ya que después de encontrar inicialmente el recíproco, solo se necesita una multiplicación (reducida) para cada multiplicación.

División por una constante

Dividir por una constante es equivalente a multiplicar por su recíproco . Como el denominador es constante, el recíproco también es constante . Luego puede calcular el valor una vez y durante los cálculos realizamos la multiplicación en lugar de la división . En la aritmética de coma flotante, el uso causa un pequeño problema relacionado con la optimización del código por parte de los compiladores [a] , pero en la aritmética de enteros , el resto siempre será cero, siempre que . $D$ ${\frac{1}{D))$ ${\ estilo de visualización 1/D}$ $N\times {\frac {1}{D))$ ${\ estilo de visualización N/D}$ ${\frac{1}{D))$ ${\ estilo de visualización | D |> 1}$

No es necesario usar exactamente , puede usar cualquier valor que se reduzca a . Por ejemplo, al dividir por 3 , puede usar fracciones , o . Por lo tanto, cuando es una potencia de dos, el paso de división se puede reducir a un desplazamiento rápido a la derecha. Como efecto, el cálculo de cómo reemplaza la división con la multiplicación y el desplazamiento. Tenga en cuenta que es precisamente este procedimiento el que es esencial aquí, ya que dará como resultado cero. ${\ estilo de visualización 1/D}$ $X/Y$ ${\ estilo de visualización 1/D}$ $1/3$ ${\ estilo de visualización 2/6}$ ${\ estilo de visualización 3/9}$ ${\ estilo de visualización 194/582}$ $Y$ ${\ estilo de visualización N/D}$ ${\frac {N\veces X}{Y))$ $N\times {\frac {X}{Y))$

Sin embargo, si ya es una potencia de dos, no existen y se cumplen las condiciones anteriores. Afortunadamente, da exactamente el mismo resultado en aritmética de enteros que , incluso si no es exactamente igual a , pero "lo suficientemente cerca", de modo que el error introducido por la aproximación está en los bits que desaparecerán después de la operación de desplazamiento [15] [ 16 ] [17] [segundo] $D$ $X$ $Y$ ${\frac {N\veces X}{Y))$ ${\ estilo de visualización N/D}$ $X/Y$ ${\ estilo de visualización 1/D}$

Como ejemplo específico de aritmética de punto fijo , para enteros sin signo de 32 bits, la división por 3 se puede reemplazar por multiplicar por , es decir, multiplicar por 2863311531 ( hexadecimal 0xAAAAAAAB) seguido de un desplazamiento a la derecha de 33 bits. El valor 2863311531 se calcula como , luego se redondea hacia arriba. De manera similar, una división por 10 se puede expresar como una multiplicación por 3435973837 (0xCCCCCCCD) seguida de una división por (o un desplazamiento a la derecha de 35 bits) [19] . OEIS da una secuencia de constantes para la multiplicación como A346495 y para el desplazamiento a la derecha como A346496 . ${\ estilo de visualización {\ tfrac {2863311531} {2 ^ {33}}}}$ ${\tfrac {2^{33}}{3}}$ $2^{{35}}$

Para una división de enteros sin signo de bits comunes donde el divisor no es una potencia de dos, la siguiente identidad transforma la división en sumas/restas de dos bits, una multiplicación de números de bit por bit (donde solo la mitad superior del resultado se utiliza), y varios turnos, precálculo y : $X$ $D$ $X$ $X$ $X$ $k=x+\lceil \log _{2}{D}\rceil$ $a=\left\lceil {\tfrac {2^{k}}{D}}\right\rceil -2^{x}$

$\left\lpiso {\frac {N}{D}}\right\rpiso =\left\lpiso {\frac {\left\lpiso {\frac {Nb}{2}}\right\rpiso +b {2^{kx-1}}}\derecha\rpiso$ dónde $b=\left\lpiso {\frac {Na}{2^{x))}\right\rpiso$

En algunos casos, la división por una constante se puede hacer incluso en menos tiempo reemplazando la "multiplicación por una constante" con una serie de cambios y sumas o restas [20] . De particular interés es la división por 10, para la cual se obtiene el cociente exacto con un resto si es necesario [21] .

Véase también

Notas

↑ A pesar de cuán "pequeño" es el problema causado por la optimización, esta optimización generalmente se oculta detrás del indicador "matemáticas rápidas" en los compiladores modernos .
↑ Los compiladores modernos normalmente implementan esta optimización de multiplicación y desplazamiento de enteros. Para constantes conocidas solo en tiempo de ejecución, el programa debe implementar la optimización por sí mismo [18]

↑ Morris, Iniewski, 2017 .
↑ Flynn Stanford EE486 (División Aritmética Informática Avanzada) - Folleto del Capítulo 5 (División) . Universidad de Stanford . Consultado el 10 de enero de 2022. Archivado desde el original el 18 de abril de 2022. (indefinido)
↑ Harris, Oberman, Horowitz, 1998 .
↑ McCann, Pippenger, 2005 , pág. 1279-1301.
↑ Análisis estadístico de defectos de punto flotante . Corporación Intel (1994). Consultado el 22 de octubre de 2013. Archivado desde el original el 23 de octubre de 2013. (indefinido)
↑ Oberman, Flynn, 1995 .
↑ Goldschmidt, 1964 .
↑ Oberman, 1999 , pág. 106-115.
↑ Soderquist, Leeser, 1997 , pág. 56-66.
↑ Anderson, Earle, Goldschmidt, Powers, 1997 .
↑ 1 2 Guy, Peter, Ferguson, 2005 , p. 118–139.
↑ Hasselstrom, 2003 .
↑ Burnikel, Ziegler, 1998 .
↑ Barrett, 1987 , pág. 311-323.
↑ Granlund, Montgomery, 1994 , pág. 61–72.
↑ Möller, Granlund, 2011 , pág. 165–175.
↑ ridículo_pez. "Labor of Division (Episode III): Faster Unsigned Division by Constants" Archivado el 8 de enero de 2022 en Wayback Machine . 2011.
↑ ridiculous_fish libdivide, división de enteros optimizada . Consultado el 6 de julio de 2021. Archivado desde el original el 23 de noviembre de 2021. (indefinido)
↑ Warren Jr., 2013 , pág. 230-234.
↑ La Budde, Robert A.; Golovchenko, Nikolái; Newton, James; Parker, David; Massmind: Binary Division by a Constant Archivado el 9 de enero de 2022 en Wayback Machine .
↑ Vocales, 1992 , p. 81–85.

Literatura

Vocales RA. División por 10 // Australian Computer Journal. - 1992. - T. 24 , núm. 3 .
James E. Morris, Krzysztof Iniewski. Manual de aplicaciones de dispositivos nanoelectrónicos . - CRC Press, 2017. - ISBN 978-1-351-83197-0 .
David L. Harris, Stuart F. Oberman, Mark A. Horowitz. División SRT: Arquitecturas, Modelos e Implementaciones . — Universidad de Stanford, 1998.
Mark McCann, Nicolás Pippenger. Algoritmos de división SRT como sistemas dinámicos // SIAM Journal on Computing. - 2005. - T. 34 , núm. 6 _ -doi : 10.1137/ S009753970444106X .
Stuart F. Oberman, Michael J. Flynn. Un análisis de algoritmos e implementaciones de división . — Universidad de Stanford, 1995.
Robert E. Goldschmidt. Aplicaciones de la División por Convergencia . - MIT, 1964. - (Tesis de maestría).
Stuart F.Oberman. División de coma flotante y algoritmos de raíz cuadrada e implementación en el microprocesador AMD-K7 // Actas del Simposio IEEE sobre aritmética informática. - 1999. - S. 106-115 . -doi : 10.1109/ ARITH.1999.762835 .
Peter Soderquist, Miriam Leeser. División y raíz cuadrada: elegir la implementación correcta // IEEE Micro. - 1997. - julio-agosto ( vol. 17 , número 4 ). -doi : 10.1109/ 40.612224 .
SF Anderson, JG Earle, RE Goldschmidt, DM Powers. IBM 360/370 modelo 91: unidad de ejecución de coma flotante // IBM Journal of Research and Development . - 1997. - Enero.
Incluso Guy, Siedel Peter, Warren Ferguson. Un análisis de error paramétrico del algoritmo de división de Goldschmidt // Journal of Computer and System Sciences. - 2005. - febrero ( vol. 70 , número 1 ). -doi : 10.1016/ j.jcss.2004.08.004 .
Karl Hasselström. División rápida de enteros grandes: una comparación de algoritmos . - Royal Institute of Technology, 2003. - ((tesis) M.Sc. en Informática).
Christoph Burnickel, Joachim Ziegler. División recursiva rápida . — Max-Planck-Institut für Informatik, 1998.
Pablo Barrett. Implementación del algoritmo de cifrado de clave pública de Rivest Shamir y Adleman en un procesador de señal digital estándar // Procedimientos sobre Avances en criptología --- CRYPTO '86 . — Londres, Reino Unido: Springer-Verlag, 1987. — págs. 311–323. — ISBN 0-387-18047-8 .
Torbjörn Granlund, Peter L. Montgomery. División por Enteros Invariantes mediante Multiplicación // Avisos SIGPLAN. - 1994. - junio ( vol. 29 , número 6 ). -doi : 10.1145/ 773473.178249 .
Niels Möller, Torbjörn Granlund. División mejorada por enteros invariantes // Transacciones IEEE en computadoras. - 2011. - febrero ( vol. 60 , número 2 ). -doi : 10.1109/ TC.2010.143 .
Henry S Warren Jr. El placer del hacker . — 2. — Addison Wesley - Pearson Education, Inc. , 2013. - ISBN 978-0-321-84268-8 .

Lectura para leer más

John JG Savard. Técnicas Aritméticas Avanzadas . cuadribloc (2018). Consultado el 16 de julio de 2018. Archivado desde el original el 3 de julio de 2018. (indefinido)

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin