Hispanopedia Wiki
Articulo de referencia

Algoritmo de división

Un algoritmo de división es aquel que , dados dos números enteros N y D (numerador y denominador respectivamente), calcula su cociente y/o resto , resultado de la división eucli...

Hispanopedia WikiContenido en espanolLectura gratuita

Un algoritmo de división es aquel que , dados dos números enteros N y D (numerador y denominador respectivamente), calcula su cociente y/o resto , resultado de la división euclidiana . Algunos se aplican manualmente, mientras que otros se utilizan en el diseño de circuitos digitales y software.

Los algoritmos de división se dividen en dos categorías principales: división lenta y división rápida. Los algoritmos de división lenta producen un dígito del cociente final por iteración. Ejemplos de división lenta incluyen la restauración , la restauración no realizada, la no restauración y la división SRT . Los métodos de división rápida comienzan con una aproximación cercana al cociente final y producen el doble de dígitos del cociente final en cada iteración. [ 1 ] Los algoritmos de Newton-Raphson y Goldschmidt pertenecen a esta categoría.

Las variantes de estos algoritmos permiten utilizar algoritmos de multiplicación rápidos . Como resultado, para números enteros grandes, el tiempo de cálculo necesario para una división es el mismo, salvo por un factor constante, que el tiempo necesario para una multiplicación, independientemente del algoritmo de multiplicación utilizado.

La discusión hará referencia al formulario.norte/D=(Q,R){\displaystyle N/D=(Q,R)}, dónde

es la entrada, y

es el resultado.

División por resta repetida

El algoritmo de división más simple, incorporado históricamente a un algoritmo de máximo común divisor presentado en los Elementos de Euclides , Libro VII, Proposición 1, encuentra el resto dados dos enteros positivos utilizando solo restas y comparaciones:

función divide_unsigned ( N , D ) si D = 0 entonces error ( DivisiónPorCero ) fin R : = N Q : = 0 mientras R ≥ D hacer R : = R − D Q : = Q + 1 fin devolver ( Q , R ) fin

La demostración de que el cociente y el resto existen y son únicos (descrita en la división euclidiana ) da lugar a un algoritmo de división completo, aplicable tanto a números negativos como positivos, utilizando sumas, restas y comparaciones:

función divide ( N , D ) si D = 0 entonces error ( DivisiónPorCero ) fin si D < 0 entonces ( Q , R ) : = divide ( N , − D ) devolver ( − Q , R ) fin si N < 0 entonces ( Q , R ) : = divide ( − N , D ) si R = 0 entonces devolver ( − Q , 0 ) sino -- Ejemplo: N = -7, D = 3 -- divide(-N, D) = divide(7, 3) = (2, 1) -- R ≠ 0, por lo que devuelve (-2 - 1, 3 - 1) = (-3, 2) -- Comprobación: (-3)*3 + 2 = -7 devolver ( − Q − 1 , D − R ) fin fin -- En este punto, N ≥ 0 y D > 0 devolver divide_sin_signo ( N , D ) fin

Este procedimiento siempre produce R ≥ 0. Aunque es muy simple, requiere Ω (Q) pasos, por lo que es exponencialmente más lento que incluso algoritmos de división lentos como la división larga. Resulta útil si se sabe que Q es pequeño (al ser un algoritmo sensible al resultado ) y puede servir como especificación ejecutable.

Implementación alternativa

Una implementación alternativa incrementa el resto y lo reinicia cuando alcanza el divisor.

Paraincógnita,y∈norte0{\displaystyle x,y\in \mathbb {N} _{0}}, el algoritmo calculaq,r{\displaystyle q,r\,}de tal manera queincógnita=qy+r{\displaystyle x=qy+r\,}, con0≤r<y{\displaystyle 0\leq r<y}:

div⁡(incógnita,y)=⌊incógnita/y⌋{\displaystyle \operatorname {div} (x,y)=\left\lfloor x/y\right\rfloor }
incógnitamody=incógnita−y⌊incógnita/y⌋{\displaystyle x{\bmod {y}}=xy\left\lfloor x/y\right\rfloor }

Considere este código en Python :

def divide_unsigned2 ( numerador : int , denominador : int ) -> tupla [ int , int ] cociente : int = 0 resto : int = 0 for _ in range ( numerador ): resto += 1 if resto == denominador : cociente += 1 resto = 0 return cociente , resto

Notas

  • Los casos especiales son
incógnitamod1=0{\displaystyle x{\bmod {1}}=0}yincógnitamod0=incógnita{\displaystyle x{\bmod {0}}=x}. [ 2 ]
  • La variable quotientnunca se lee. Por lo tanto, cuando sus asignaciones ( resaltadas ) se eliminan del código y quotientse elimina de la lista de salida, divide_unsigned2 , al igual que divide_unsigned , seguirá calculando.incógnitamody{\displaystyle x{\bmod {y}}}.

Implementación alternativa como máquina contadora Una máquina contadora (CM) simple puede basarse en la implementación alternativa. Las instrucciones de la CM son [ 3 ] [ 4 ]

  • Z (n): Reemplazar r n por 0.
  • S (n): Sumar 1 a r n .
  • J (m, n, q): Si r m = r n , salta a la instrucción q; de lo contrario, continúa con la siguiente instrucción del programa.

El programa de la máquina contadora es [ 5 ]

1: J(1,5,0) 2: S(4) 3: J(4,2,6) 4: S(5) 5: J(0,0,1) 6: S(3) 7: Z(4) 8: S(5) 9: J(0,0,1)

Después de que el CM finaliza el cálculo en los valores iniciales de los registros R1=N, R2=D (registros restantes = 0),

El registro R3 contiene la (parte entera del) cociente de la división N/D, y
El registro R4 contiene el resto.

División larga

La división larga es el algoritmo estándar que se utiliza para dividir números de varias cifras expresados ​​en notación decimal con lápiz y papel. Consiste en desplazarse gradualmente desde el extremo izquierdo hacia el extremo derecho del dividendo, restando en cada paso el mayor múltiplo posible del divisor (a nivel de dígito); estos múltiplos se convierten en los dígitos del cociente, y la diferencia final es el resto.

Cuando se utiliza con una base binaria, este método constituye la base del algoritmo de división entera (sin signo) con resto que se describe a continuación. La división corta es una forma abreviada de la división larga, adecuada para divisores de un dígito. La división por bloques —también conocida como método de cocientes parciales o método del ahorcado— es una forma menos eficiente de la división larga, pero que puede resultar más fácil de comprender. Al permitir restar más múltiplos de los que se tienen en cada etapa, también se puede desarrollar una variante más flexible de la división larga.  

División entera (sin signo) con resto

El siguiente algoritmo, la versión binaria de la famosa división larga , dividirá N entre D , colocando el cociente en Q y el resto en R. En el siguiente pseudocódigo, todos los valores se tratan como enteros sin signo.

if D = 0 then error ( DivisionByZeroException ) end Q : = 0 -- Inicializar el cociente y el resto a cero R : = 0 for i : = n − 1 .. 0 do -- Donde n es el número de bits en N R : = R << 1 -- Desplazar R a la izquierda en 1 bit R ( 0 ) : = N ( i ) -- Establecer el bit menos significativo de R igual al bit i del numerador if R ≥ D then R : = R − D Q ( i ) : = 1 end end

Ejemplo

Si tomamos N=1100 2 (12 10 ) y D=100 2 (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 (desplazado a la izquierda en 1). Paso 4 : R=01 (estableciendo R(0) a N(i)). Paso 5 : R < D, por lo que se omite la instrucción.

Paso 2 : Establecer i=2 Paso 3 : R=010 Paso 4 : R=011 Paso 5 : R < D, instrucción omitida

Paso 2 : Establecer i=1 Paso 3 : R=0110 Paso 4 : R=0110 Paso 5 : R>=D, instrucción ingresada Paso 5b : R=10 (R−D) Paso 5c : Q=10 (establecer Q(i) a 1)

Paso 2 : Establecer i=0 Paso 3 : R=100 Paso 4 : R=100 Paso 5 : R>=D, instrucción ingresada Paso 5b : R=0 (R−D) Paso 5c : Q=11 (establecer Q(i) a 1)

fin Q=11 2 (3 10 ) y R=0.

Métodos de división lenta

Los métodos de división lenta se basan todos en una ecuación de recurrencia estándar [ 6 ].

Rj+1=B×Rj−qnorte−(j+1)×D,{\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}

dónde:

  • R j es el j -ésimo resto parcial de la división (  se incluye el paso R(0) := N(i)).
  • B es la base (generalmente 2 internamente en computadoras y calculadoras).
  • q n − ( j + 1) es el dígito del cociente en la posición n −( j +1), donde las posiciones de los dígitos están numeradas desde el menos significativo 0 hasta el más significativo n −1.
  • n es el número de dígitos en el cociente.
  • D es el divisor

Restablecer la división

La división restaurativa opera sobre números fraccionarios de punto fijo y depende de la suposición 0 < D < N.

Los dígitos cociente q se forman a partir del conjunto de dígitos {0,1}.

El algoritmo básico para la división restaurativa binaria (base 2) es:

R : = N D : = D << n -- R y D necesitan el doble del ancho de palabra de N y Q para i : = n − 1 .. 0 hacer -- Por ejemplo 31..0 para 32 bits R : = 2 * R − D -- Resta de prueba del valor desplazado (la multiplicación por 2 es un desplazamiento en la representación binaria) si R >= 0 entonces q ( i ) : = 1 -- Resultado: bit 1 sino q ( i ) : = 0 -- Resultado: bit 0 R : = R + D -- El nuevo resto parcial es el valor desplazado (restaurado) fin fin-- Donde: N = numerador, D = denominador, n = #bits, R = resto parcial, q(i) = bit #i del cociente

La división restaurativa no ejecutable es similar a la división restaurativa excepto que el valor de 2R se guarda, por lo que no es necesario volver a agregar D en el caso de R < 0.

División no restauradora

La división sin restauración utiliza el conjunto de dígitos { − 1, 1} para los dígitos del cociente en lugar de {0, 1}. El algoritmo es más complejo, pero tiene la ventaja, cuando se implementa en hardware, de que solo hay una decisión y una suma/resta por bit del cociente; no hay paso de restauración después de la resta, [ 7 ] lo que potencialmente reduce el número de operaciones hasta en un 50 % y permite que se ejecute más rápido. [ 8 ] El algoritmo básico para la división binaria (base 2) sin restauración de números no negativos es:

-- Entradas: N (Numerador), D (Denominador) -- n = número de bits -- R y D generalmente se almacenan en registros de ancho 2n o similar para manejar desplazamientosR : = N -- Inicializar el restopara i = n − 1 .. 0 hacer -- por ejemplo 31..0 para 32 bits -- Desplazar el resto a la izquierda (algebraicamente: 2 * R) si R >= 0 entonces R : = 2 * R - D ; -- Restar D q ( i ) : = 1 ; -- Registrar el bit cociente como 1 sino R : = 2 * R + D ; -- Sumar D (restaurar) q ( i ) : = - 1 ; -- Registrar el bit cociente como -1 fin si fin para

Siguiendo este algoritmo, el cociente se presenta en un formato no estándar que consta de los dígitos −1 y +1. Este formato debe convertirse a binario para obtener el cociente final. Ejemplo:

Si los dígitos −1 deQ{\displaystyle Q}se almacenan como ceros (0) como es común, entoncesPAG{\displaystyle P}esQ{\displaystyle Q}y computaciónMETRO{\displaystyle M}es trivial: realizar un complemento a uno (complemento bit a bit) en el originalQ{\displaystyle Q}.

Q : = Q − bit . bnot ( Q ) -- Apropiado si los dígitos −1 en Q se representan como ceros, como es común.

Finalmente, los cocientes calculados por este algoritmo siempre son impares, y el resto en R está en el rango −D ≤ R < D. Por ejemplo, 5 / 2 = 3 R −1. Para convertirlo a un resto positivo, realice un único paso de restauración después de que Q se haya convertido de la forma no estándar a la forma estándar:

Si R < 0, entonces Q : = Q − 1 R : = R + D -- Necesario solo si el resto es de interés. Fin si

El resto real es R >> n. (Al igual que en la división restaurativa, los bits de orden inferior de R se consumen al mismo ritmo que se producen los bits del cociente Q, y es común utilizar un único registro de desplazamiento para ambos).

División SRT

La división SRT es un método popular para la división en muchas implementaciones de microprocesadores . [ 9 ] [ 10 ] El algoritmo lleva el nombre de DW Sweeney de IBM , James E. Robertson de la Universidad de Illinois y KD Tocher del Imperial College de Londres . Todos ellos desarrollaron el algoritmo de forma independiente aproximadamente al mismo tiempo (publicado en febrero de 1957, septiembre de 1958 y enero de 1958, respectivamente). [ 11 ] [ 12 ] [ 13 ]

La división SRT es similar a la división no restaurativa, pero utiliza una tabla de búsqueda basada en el dividendo y el divisor para determinar cada dígito del cociente.

La diferencia más significativa radica en el uso de una representación redundante para el cociente. Por ejemplo, al implementar la división SRT de base 4, cada dígito del cociente se elige entre cinco posibilidades: −2, −1, 0, +1 o +2. Debido a esto, la elección de un dígito del cociente no tiene por qué ser perfecta; los dígitos posteriores pueden corregir pequeños errores. (Por ejemplo, los pares de dígitos del cociente (0,  +2) y (1,  −2) son equivalentes, ya que 0 × 4 + 2 = 1 × 4 − 2 ). Esta tolerancia permite seleccionar los dígitos del cociente utilizando solo algunos de los bits más significativos del dividendo y el divisor, en lugar de requerir una resta completa. Esta simplificación, a su vez, permite utilizar una base mayor que 2.

Al igual que en la división no restaurativa, los pasos finales consisten en una resta final de ancho completo para resolver el último bit del cociente y la conversión del cociente a formato binario estándar.

El infame error de división de punto flotante del procesador Intel Pentium original fue causado por una tabla de búsqueda codificada incorrectamente. Los procesadores Pentium utilizaban una tabla de 2048 celdas, de las cuales 1066 debían rellenarse, y los valores de cinco celdas se omitieron erróneamente. [ 14 ] [ 15 ] [ 16 ]

Métodos de división rápidos

división de Newton-Raphson

Newton-Raphson utiliza el método de Newton para hallar el recíproco deD{\displaystyle D}y multiplica ese recíproco pornorte{\displaystyle N}para hallar el cociente finalQ{\displaystyle Q}.

Los pasos de la división de Newton-Raphson son:

  1. Calcular una estimaciónincógnita0{\displaystyle X_{0}}para el recíproco1/D{\displaystyle 1/D}del divisorD{\displaystyle D}.
  2. Calcular estimaciones sucesivamente más precisas.incógnita1,incógnita2,…,incógnitaS{\displaystyle X_{1},X_{2},\ldots ,X_{S}}del recíproco. Aquí es donde se emplea el método de Newton-Raphson como tal.
  3. Calcula el cociente multiplicando el dividendo por el recíproco del divisor:Q=norteincógnitaS{\displaystyle Q=NX_{S}}.

Para aplicar el método de Newton para hallar el recíproco deD{\displaystyle D}, es necesario encontrar una funciónF(incógnita){\displaystyle f(X)}que tiene un cero enincógnita=1/D{\displaystyle X=1/D}. La función obvia de este tipo esF(incógnita)=Dincógnita−1{\displaystyle f(X)=DX-1}, pero la iteración de Newton-Raphson para esto no es útil, ya que no se puede calcular sin conocer previamente el recíproco deD{\displaystyle D}(además, intenta calcular el recíproco exacto en un solo paso, en lugar de permitir mejoras iterativas). Una función que sí funciona esF(incógnita)=(1/incógnita)−D{\displaystyle f(X)=(1/X)-D}, para lo cual la iteración de Newton-Raphson da

incógnitai+1=incógnitai−F(incógnitai)F′(incógnitai)=incógnitai−1/incógnitai−D−1/incógnitai2=incógnitai+incógnitai(1−Dincógnitai)=incógnitai(2−Dincógnitai),{\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),}

que se puede calcular a partir deincógnitai{\displaystyle X_{i}}utilizando únicamente la multiplicación y la resta, o utilizando dos multiplicaciones-sumas fusionadas .

Desde el punto de vista computacional, las expresionesincógnitai+1=incógnitai+incógnitai(1−Dincógnitai){\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}yincógnitai+1=incógnitai(2−Dincógnitai){\displaystyle X_{i+1}=X_{i}(2-DX_{i})}no son equivalentes. Para obtener un resultado con una precisión de 2 n bits utilizando la segunda expresión, se debe calcular el producto entreincógnitai{\displaystyle X_{i}}y(2−Dincógnitai){\displaystyle (2-DX_{i})}con el doble de la precisión dada deincógnitai{\displaystyle X_{i}}( n bits). En contraste, el producto entreincógnitai{\displaystyle X_{i}}y(1−Dincógnitai){\displaystyle (1-DX_{i})}Solo es necesario calcularlo con una precisión de n bits, porque los n bits principales (después del punto binario) de(1−Dincógnitai){\displaystyle (1-DX_{i})}son ceros.

Si el error se define comoεi=1−Dincógnitai{\displaystyle \varepsilon _{i}=1-DX_{i}}, entonces:

εi+1=1−Dincógnitai+1=1−D(incógnitai(2−Dincógnitai))=1−2Dincógnitai+D2incógnitai2=(1−Dincógnitai)2=εi2.{\displaystyle {\begin{aligned}\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{aligned}}}

Esta elevación al cuadrado del error en cada paso de iteración —la llamada convergencia cuadrática del método de Newton-Raphson— tiene como efecto que el número de dígitos correctos en el resultado se duplique aproximadamente en cada iteración , una propiedad que se vuelve extremadamente valiosa cuando los números involucrados tienen muchos dígitos (por ejemplo, en el dominio de los enteros grandes). Pero también significa que la convergencia inicial del método puede ser relativamente lenta, especialmente si la estimación inicial  incógnita0{\displaystyle X_{0}}Está mal elegido.

Estimación inicial

Para el subproblema de elegir una estimación inicialincógnita0{\displaystyle X_{0}}Es conveniente aplicar un desplazamiento de bits al divisor D para escalarlo de manera que 0,5  ≤ D ≤ 1. Aplicar el mismo desplazamiento de bits al numerador N garantiza que el cociente no cambie. Una vez dentro de un rango acotado, se puede utilizar una aproximación polinómica simple para obtener una estimación inicial.   

La aproximación lineal con mínimo error absoluto en el peor de los casos en el intervalo[0,5,1]{\displaystyle [0.5,1]}es:

incógnita0=4817−3217D.{\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.}

Los coeficientes de la aproximación linealT0+T1D{\displaystyle T_{0}+T_{1}D}se determinan de la siguiente manera. El valor absoluto del error es|ε0|=|1−D(T0+T1D)|{\displaystyle |\varepsilon _{0}|=|1-D(T_{0}+T_{1}D)|}. El mínimo del valor absoluto máximo del error se determina mediante el teorema de equioscilación de Chebyshev aplicado aF(D)=1−D(T0+T1D){\displaystyle F(D)=1-D(T_{0}+T_{1}D)}. El mínimo local deF(D){\displaystyle F(D)}ocurre cuandoF′(D)=0{\displaystyle F'(D)=0}, que tiene soluciónD=−T0/(2T1){\displaystyle D=-T_{0}/(2T_{1})}. La función en ese mínimo debe tener signo opuesto al de la función en los extremos, a saber,F(1/2)=F(1)=−F(−T0/(2T1)){\displaystyle F(1/2)=F(1)=-F(-T_{0}/(2T_{1}))}Las dos ecuaciones con dos incógnitas tienen una solución única.T0=48/17{\displaystyle T_{0}=48/17}yT1=−32/17{\displaystyle T_{1}=-32/17}y el error máximo esF(1)=1/17{\displaystyle F(1)=1/17}. Utilizando esta aproximación, el valor absoluto del error del valor inicial es menor que

|ε0|≤117≈0,059.{\displaystyle \vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.}

El mejor ajuste cuadrático a1/D{\displaystyle 1/D}en el intervalo es

incógnita:=14033−6411D+25699D2.{\displaystyle X:={\frac {140}{33}}-{\frac {64}{11}}D+{\frac {256}{99}}D^{2}.}

Se elige hacer que el error sea igual a un polinomio de Chebyshev de tercer orden reescalado de primera especie, y da un valor absoluto del error menor o igual a 1/99. Esta mejora es equivalente aregistro2⁡(registro⁡99/registro⁡17)≈0,7{\displaystyle \log _{2}(\log 99/\log 17)\approx 0.7}Iteraciones de Newton-Raphson, con un coste computacional inferior a una iteración.

Es posible generar un ajuste polinómico de grado superior a 2, calculando los coeficientes mediante el algoritmo de Remez . La desventaja es que la estimación inicial requiere más ciclos de cálculo, pero, idealmente, a cambio de un menor número de iteraciones del método de Newton-Raphson.

Dado que para este método la convergencia es exactamente cuadrática, se deduce que, a partir de un error inicialε0{\displaystyle \varepsilon _{0}},S{\displaystyle S}Las iteraciones darán una respuesta precisa a

PAG=−2Sregistro2⁡ε0−1=2Sregistro2⁡(1/ε0)−1{\displaystyle P=-2^{S}\log _{2}\varepsilon _{0}-1=2^{S}\log _{2}(1/\varepsilon _{0})-1}

Lugares binarios. Los valores típicos son:

Una estimación inicial cuadrática más dos iteraciones es suficientemente precisa para la precisión simple IEEE , pero tres iteraciones resultan insuficientes para la precisión doble . Una estimación inicial lineal más cuatro iteraciones es suficiente tanto para el formato doble como para el formato doble extendido .

Pseudocódigo

El siguiente código calcula el cociente de N y D con una precisión de P posiciones binarias:

Expresar D como M × 2 e donde 1 ≤ M < 2 (representación estándar de punto flotante) D'  := D / 2 e+1 // escalar entre 0,5 y 1, se puede realizar con desplazamiento de bits / resta de exponente N'  := N / 2 e+1 X  := 48/17 − 32/17 × D' // precalcular constantes con la misma precisión que D repetir⌈registro2⁡PAG+1registro2⁡17⌉{\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}tiempos // se pueden precalcular en función de P fijo X := X + X × (1 - D' × X) fin devolver N' × X

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

Iteración cúbica

Existe una iteración que utiliza tres multiplicaciones para elevar el error al cubo:

εi=1−Dincógnitai{\displaystyle \varepsilon _{i}=1-DX_{i}}
Yi=incógnitaiεi{\displaystyle Y_{i}=X_{i}\varepsilon _{i}}
incógnitai+1=incógnitai+Yi+Yiεi.{\displaystyle X_{i+1}=X_{i}+Y_{i}+Y_{i}\varepsilon _{i}.}

El término Y i ε i es nuevo.

Ampliando lo anterior,incógnitai+1{\displaystyle X_{i+1}}se puede escribir como

incógnitai+1=incógnitai+incógnitaiεi+incógnitaiεi2=incógnitai+incógnitai(1−Dincógnitai)+incógnitai(1−Dincógnitai)2=3incógnitai−3Dincógnitai2+D2incógnitai3,{\displaystyle {\begin{aligned}X_{i+1}&=X_{i}+X_{i}\varepsilon _{i}+X_{i}\varepsilon _{i}^{2}\\&=X_{i}+X_{i}(1-DX_{i})+X_{i}(1-DX_{i})^{2}\\&=3X_{i}-3DX_{i}^{2}+D^{2}X_{i}^{3},\end{aligned}}}

con el resultado de que el término de error

εi+1=1−Dincógnitai+1=1−3Dincógnitai+3D2incógnitai2−D3incógnitai3=(1−Dincógnitai)3=εi3.{\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-3DX_{i}+3D^{2}X_{i}^{2}-D^{3}X_{i}^{3}\\&=(1-DX_{i})^{3}\\&=\varepsilon _{i}^{3}.\end{aligned}}}

Esto es 3/2 del cálculo de la iteración cuadrática, pero lograregistro⁡3/registro⁡2≈1.585{\displaystyle \log 3/\log 2\approx 1.585}Con la misma convergencia, resulta ligeramente más eficiente. Dicho de otro modo, dos iteraciones de este método elevan el error a la novena potencia con el mismo coste computacional que tres iteraciones cuadráticas, que solo lo elevan a la octava potencia.

El número de bits correctos despuésS{\displaystyle S}iteraciones es

PAG=−3Sregistro2⁡ε0−1=3Sregistro2⁡(1/ε0)−1{\displaystyle P=-3^{S}\log _{2}\varepsilon _{0}-1=3^{S}\log _{2}(1/\varepsilon _{0})-1}

Lugares binarios. Los valores típicos son:

Una estimación inicial cuadrática más dos iteraciones cúbicas proporciona una precisión suficiente para un resultado de doble precisión según el estándar IEEE. También es posible utilizar una combinación de iteraciones cuadráticas y cúbicas.

El uso de al menos una iteración cuadrática garantiza que el error sea positivo, es decir, que el recíproco se subestime. [ 17 ] : 370 Esto puede simplificar un paso de redondeo posterior si se requiere un cociente redondeado con exactitud.

El uso de polinomios de mayor grado, ya sea en la inicialización o en la iteración, conlleva una degradación del rendimiento, puesto que las multiplicaciones adicionales necesarias se aprovecharían mejor realizando más iteraciones.

División Goldschmidt

La división de Goldschmidt [ 18 ] (en honor a Robert Elliott Goldschmidt) [ 19 ] utiliza un proceso iterativo de multiplicar repetidamente tanto el dividendo como el divisor por un factor común F i , elegido de tal manera que el divisor converja a 1. Esto hace que el dividendo converja al cociente buscado Q :

Q=norteDF1F1F2F2F…F….{\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}

Los pasos para la división de Goldschmidt son:

  1. Generar una estimación para el factor de multiplicación F i .
  2. Multiplica el dividendo y el divisor por F i .
  3. Si el divisor está suficientemente cerca de 1, devuelve el dividendo; de lo contrario, vuelve al paso 1.

Suponiendo que N / D se ha escalado de modo que 0  < D < 1, cada F i se basa en D :   

Fi+1=2−Di.{\displaystyle F_{i+1}=2-D_{i}.}

Al multiplicar el dividendo y el divisor por el factor se obtiene:

nortei+1Di+1=norteiDiFi+1Fi+1.{\displaystyle {\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 k de iteracionesQ=nortek{\displaystyle Q=N_{k}}.

El método Goldschmidt se utiliza en las CPU AMD Athlon y modelos posteriores. [ 20 ] [ 21 ] También se conoce como algoritmo Anderson Earle Goldschmidt Powers (AEGP) y está implementado en varios procesadores IBM . [ 22 ] [ 23 ] Aunque converge a la misma velocidad que una implementación de Newton-Raphson, una ventaja del método Goldschmidt es que las multiplicaciones en el numerador y en el denominador se pueden realizar en paralelo. [ 23 ]

Teorema del binomio

El método de Goldschmidt se puede utilizar con factores que permiten simplificaciones mediante el teorema del binomio . Supongamos quenorte/D{\displaystyle N/D}⁠ se ha escalado por una potencia de dos de tal manera queD∈(12,1]{\displaystyle D\in \left({\tfrac {1}{2}},1\right]}. ElegimosD=1−incógnita{\displaystyle D=1-x}yFi=1+incógnita2i{\displaystyle F_{i}=1+x^{2^{i}}}Esto produce

norte1−incógnita=norte⋅(1+incógnita)1−incógnita2=norte⋅(1+incógnita)⋅(1+incógnita2)1−incógnita4=⋯=Q′=norte′=norte⋅(1+incógnita)⋅(1+incógnita2)⋅⋅⋅(1+incógnita2(norte−1))D′=1−incógnita2norte≈1{\displaystyle {\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}}\approx 1}}}.

Después de n pasos(incógnita∈[0,12)){\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}, el denominador1−incógnita2norte{\displaystyle 1-x^{2^{n}}}se puede redondear a1 con un error relativo

εnorte=Q′−norte′Q′=incógnita2norte{\displaystyle \varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}

que es máximo en2−2norte{\displaystyle 2^{-2^{n}}}cuandoincógnita=12{\displaystyle x={\tfrac {1}{2}}}, proporcionando así una precisión mínima de2norte{\displaystyle 2^{n}}dígitos binarios.

Métodos de números enteros grandes

Los métodos diseñados para la implementación en hardware generalmente no escalan a enteros con miles o millones de dígitos decimales; estos ocurren frecuentemente, por ejemplo, en reducciones modulares en criptografía . Para estos enteros grandes, los algoritmos de división más eficientes transforman el problema para usar un pequeño número de multiplicaciones, que luego se pueden hacer usando un algoritmo de multiplicación asintóticamente eficiente como el algoritmo de Karatsuba , la multiplicación de Toom-Cook o el algoritmo de Schönhage-Strassen . El resultado es que la complejidad computacional de la división es del mismo orden (salvo una constante multiplicativa) que la de la multiplicación. Los ejemplos incluyen la reducción a multiplicación por el método de Newton como se describió anteriormente , [ 24 ] así como la división de Burnikel-Ziegler ligeramente más rápida , [ 25 ] los algoritmos de reducción de Barrett y Montgomery . [ 26 ] El método de Newton es particularmente eficiente en escenarios donde se debe dividir por el mismo divisor muchas veces, ya que después de la inversión inicial de Newton solo se necesita una multiplicación (truncada) para cada división.

División por una constante

La división por una constante D es equivalente a la multiplicación por su recíproco . Dado que el denominador es constante, también lo es su recíproco (1/ D ). Por lo tanto, es posible calcular el valor de (1/ D ) una sola vez en tiempo de compilación y, en tiempo de ejecución, realizar la multiplicación N · (1/ D ) en lugar de la división N/D . En aritmética de punto flotante, el uso de (1/ D ) presenta pocos problemas, [ a ] pero en aritmética de enteros , el recíproco siempre se evaluará como cero (suponiendo | D | > 1).

No es necesario usar específicamente (1/ D ); se puede usar cualquier valor ( X / Y ) que se reduzca a (1/ D ). Por ejemplo, para la división por 3, se podrían usar los factores 1/3, 2/6, 3/9 o 194/582. En consecuencia, si Y fuera una potencia de dos, el paso de división se reduciría a un desplazamiento rápido de bits a la derecha. El efecto de calcular N / D como ( N · X )/ Y reemplaza una división con una multiplicación y un desplazamiento. Nótese que los paréntesis son importantes, ya que N · ( X / Y ) se evaluará como cero.

Sin embargo, a menos que D mismo sea una potencia de dos, no hay X e Y que satisfagan las condiciones anteriores. Afortunadamente, ( N · X )/ Y da exactamente el mismo resultado que N / D en aritmética entera incluso cuando ( X / Y ) no es exactamente igual a 1/ D , pero "lo suficientemente cerca" como para que el error introducido por la aproximación esté en los bits que se descartan por la operación de desplazamiento. [ 27 ] [ 28 ] [ 29 ] La reducción de Barrett utiliza potencias de 2 para el valor de Y para hacer que la división por Y sea un simple desplazamiento a la derecha. [ b ]

Como ejemplo concreto de aritmética de punto fijo , para enteros sin signo de 32 bits, la división por 3 se puede reemplazar con una multiplicación por 2863311531 / 2 33 , una multiplicación ampliada por 2863311531 ( hexadecimal 0xAAAAAAAB) seguida de un desplazamiento de 33 bits a la derecha. El valor de 2863311531 se calcula como 2 33 / 3 y luego se redondea hacia arriba. De manera similar, la división por 10 se puede expresar como una multiplicación por 3435973837 (0xCCCCCCCD) seguida de una división por 2 35 (o un desplazamiento de 35 bits a la derecha). [ 31 ] : p230-234 OEIS proporciona secuencias de las constantes para la multiplicación como A346495 y para el desplazamiento a la derecha como A346496 .

Para la división general de enteros sin signo de x bits donde el divisor D no es una potencia de 2, la siguiente identidad convierte la división en dos sumas/restas de x bits, una multiplicación de x bits por x bits (donde solo se usa la mitad superior del resultado) y varios desplazamientos, después de precalculark=incógnita+⌈registro2⁡D⌉{\displaystyle k=x+\lceil \log _{2}{D}\rceil }ya=⌈2kD⌉−2incógnita{\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}:

⌊norteD⌋=⌊⌊norte−b2⌋+b2k−incógnita−1⌋ dónde b=⌊nortea2incógnita⌋{\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }

En algunos casos, la división por una constante se puede realizar en aún menos tiempo convirtiendo la "multiplicación por una constante" en una serie de desplazamientos y sumas o restas . [ 32 ] De particular interés es la división por 10, para la cual se obtiene el cociente exacto, con resto si es necesario. [ 33 ]

Error de redondeo

Cuando se realiza una operación de división, el cociente exactoq{\displaystyle q}y el restor{\displaystyle r}se aproximan para ajustarse a los límites de precisión de la computadora. El algoritmo de división establece:

[a=bq+r]{\displaystyle [a=bq+r]}

dónde0≤r<|b|{\displaystyle 0\leq r<|b|}.

En aritmética de punto flotante , el cocienteq{\displaystyle q}se representa comoq~{\displaystyle {\tilde {q}}}y el restor{\displaystyle r}comor~{\displaystyle {\tilde {r}}}introduciendo errores de redondeoϵq{\displaystyle \epsilon _{q}}yϵr{\displaystyle \epsilon _{r}}:

[q~=q+ϵq][r~=r+ϵr]{\displaystyle [{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]}

Este redondeo provoca un pequeño error que puede propagarse y acumularse en cálculos posteriores. Estos errores son particularmente pronunciados en procesos iterativos y al restar valores casi iguales, lo que se conoce como pérdida de significancia . Para mitigar estos errores, se emplean técnicas como el uso de dígitos de guarda o una mayor precisión (o precisión arbitraria ). [ 34 ] [ 35 ]

Véase también

Notas

  1. ↑ A pesar de lo "pequeño" problema que causa la optimización, esta optimización recíproca suele estar oculta tras una bandera de "matemáticas rápidas" en los compiladores modernos , ya que es inexacta.
  2. ↑ Los compiladores modernossuelen realizar esta optimización de multiplicación y desplazamiento de enteros; sin embargo, para una constante que solo se conoce en tiempo de ejecución, el programa debe implementar la optimización por sí mismo. [ 30 ]

Referencias

  1. ↑ Rodeheffer, Thomas L. (26 de agosto de 2008). División de enteros de software (PDF) (Informe técnico). Microsoft Research, Silicon Valley.
  2. ↑ Comparar: en el procedimiento divide_unsigned ,denominatordebe ser estrictamente positivo.
  3. ↑ Shepherdson, JC ; Sturgis, HE (1963). "Computabilidad de funciones recursivas" . Journal of the Association for Computing Machinery . 10 (2): 217– 255. doi : 10.1145/321160.321170 .
  4. ↑ Cutland, Nigel (1980). Computabilidad: Una introducción a la teoría de funciones recursivas (PDF) . Cambridge University Press . pág. 12. ISBN  9780521223843. Consultado el 16 de septiembre de 2025 .
  5. ↑ El código se ejecuta en el "Simulador URM" del Occidental College de Los Ángeles . Simulador (emulador) de Unlimited Register Machine (URM): una "URM virtual". Está basado en la especificación URM del libro de Nigel J. Cutland, Computability: An introduction to recursive function theory, publicado por Cambridge Press.
  6. ↑ Morris, James E.; Iniewski, Krzysztof (22 de noviembre de 2017). Manual de aplicaciones de dispositivos nanoelectrónicos . CRC Press. ISBN 978-1-351-83197-0.
  7. ↑ Shaw, Robert F. (1950). "Operaciones aritméticas en una computadora binaria" . Review of Scientific Instruments . 21 (8): 690. Bibcode : 1950RScI...21..687S . doi : 10.1063/1.1745692 . ISSN 0034-6748 . Archivado del original el 28 de febrero de 2022. Consultado el 28 de febrero de 2022 . 
  8. ↑ Flynn. "Stanford EE486 (División de aritmética computacional avanzada) – Material del capítulo 5 (División)" (PDF) . Universidad de Stanford . Archivado (PDF) del original el 18 de abril de 2022. Consultado el 24 de junio de 2019 . 
  9. ↑ Harris, David L.; Oberman, Stuart F.; Horowitz, Mark A. (9 de septiembre de 1998). División SRT: Arquitecturas, modelos e implementaciones (PDF) (Informe técnico). Universidad de Stanford. Archivado (PDF) del original el 24 de diciembre de 2016. Recuperado el 23 de diciembre de 2016 .
  10. ↑ McCann, Mark; Pippenger, Nicholas (2005). "Algoritmos de división SRT como sistemas dinámicos" . SIAM Journal on Computing . 34 (6): 1279– 1301. CiteSeerX 10.1.1.72.6993 . doi : 10.1137/S009753970444106X . hdl : 2429/12179 . Archivado del original el 24 de agosto de 2022. Recuperado el 24 de agosto de 2022 . 
  11. ↑ Cocke, John; Sweeney, DW (11 de febrero de 1957), Aritmética de alta velocidad en un dispositivo paralelo (Memorando de la compañía), IBM, pág. 20, archivado del original el 24 de agosto de 2022 , recuperado el 24 de agosto de 2022 {{citation}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
  12. ↑ Robertson, James (1958-09-01). "Una nueva clase de métodos de división digital". IRE Transactions on Electronic Computers . EC-7 (3). IEEE: 218– 222. Bibcode : 1958IRTEC...7..218R . doi : 10.1109/TEC.1958.5222579 . hdl : 2027/uiuo.ark:/13960/t0gt7529c .
  13. ↑ Tocher, KD (1958-01-01). "Técnicas de multiplicación y división para computadoras binarias automáticas" . The Quarterly Journal of Mechanics and Applied Mathematics . 11 (3): 364– 384. doi : 10.1093/qjmam/11.3.364 . Archivado del original el 24-08-2022 . Recuperado el 24-08-2022 .
  14. ↑ "Análisis estadístico del fallo de punto flotante" . Intel Corporation. 1994. Archivado del original el 23 de octubre de 2013. Consultado el 22 de octubre de 2013 .
  15. ↑ Oberman, Stuart F.; Flynn, Michael J. (julio de 1995). Un análisis de algoritmos e implementaciones de división (PDF) (Informe técnico). Universidad de Stanford. CSL-TR-95-675. Archivado (PDF) del original el 17 de mayo de 2017. Recuperado el 23 de diciembre de 2016 .
  16. ↑ Shirriff, Ken (28 de diciembre de 2024). "El error de Intel de 475 millones de dólares: el silicio detrás del fallo de la división Pentium" . Righto . Consultado el 30 de diciembre de 2024 .
  17. ↑ Ercegovac, Miloš D.; Lang, Tomás (2004). «Capítulo 7: División recíproca, raíz cuadrada recíproca y raíz cuadrada por aproximación iterativa». Aritmética digital . Morgan Kaufmann. págs. 367–395 . ISBN  1-55860-798-6.
  18. ↑ Goldschmidt, Robert E. (1964). Aplicaciones de la división por convergencia (PDF) (Tesis). Disertación de maestría. MIT OCLC 34136725. Archivado (PDF) del original el 10 de diciembre de 2015. Recuperado el 15 de septiembre de 2015 . 
  19. ↑ "Autores" . IBM Journal of Research and Development . 11 : 125–127 . 1967. doi : 10.1147/rd.111.0125 . Archivado del original el 18 de julio de 2018.
  20. ↑ Oberman, Stuart F. (1999). "Algoritmos de división de punto flotante y raíz cuadrada e implementación en el microprocesador AMD-K7" (PDF) . Actas del 14.º Simposio IEEE sobre Aritmética Computacional (Cat. n.º 99CB36336) . págs. 106-115 . doi : 10.1109/ARITH.1999.762835 . ISBN  0-7695-0116-8. S2CID 12793819 . Archivado (PDF) del original el 29-11-2015 . Recuperado el 15-09-2015 . 
  21. ↑ Soderquist, Peter; Leeser, Miriam (julio-agosto de 1997). "División y raíz cuadrada: cómo elegir la implementación correcta" . IEEE Micro . 17 (4): 56– 66. Bibcode : 1997IMicr..17d..56S . doi : 10.1109/40.612224 .
  22. ↑ SF Anderson, JG Earle, RE Goldschmidt, DM Powers. El modelo 91 de IBM 360/370: unidad de ejecución de punto flotante , IBM Journal of Research and Development , enero de 1997.
  23. 1 2 Guy, Even; Peter, Siedel; Ferguson, Warren (1 de febrero de 2005). "Análisis de error paramétrico del algoritmo de división de Goldschmidt" . Journal of Computer and System Sciences . 70 (1): 118– 139. doi : 10.1016/j.jcss.2004.08.004 .
  24. ↑ Hasselström, Karl (2003). División rápida de enteros grandes: una comparación de algoritmos (PDF) (tesis de maestría en Ciencias de la Computación). Instituto Real de Tecnología. Archivado del original (PDF) el 8 de julio de 2017. Recuperado el 8 de julio de 2017 .
  25. ↑ Joachim Ziegler, Christoph Burnikel (1998), Fast Recursive Division , Max-Planck-Institut für Informatik, archivado desde el original el 26 de abril de 2011 , consultado el 10 de septiembre de 2021{{citation}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
  26. ↑ Barrett, Paul (1987). «Implementación del algoritmo de cifrado de clave pública de Rivest Shamir y Adleman en un procesador de señales digitales estándar» . Actas de Advances in cryptology---CRYPTO '86 . Londres, Reino Unido: Springer-Verlag. págs. 311–323 . ISBN  0-387-18047-8.
  27. ↑ Granlund, Torbjörn; Montgomery, Peter L. (junio de 1994). "División por enteros invariantes mediante multiplicación" (PDF) . SIGPLAN Notices . 29 (6): 61–72 . CiteSeerX 10.1.1.1.2556 . doi : 10.1145/773473.178249 . Archivado (PDF) del original el 6 de junio de 2019. Recuperado el 8 de diciembre de 2015 . 
  28. ↑ Möller, Niels; Granlund, Torbjörn (febrero de 2011). " Improved Division by Invariant Integers" (PDF) . IEEE Transactions on Computers . 60 (2): 165–175 . Bibcode : 2011ITCmp..60..165M . doi : 10.1109/TC.2010.143 . S2CID 13347152. Archivado (PDF) del original el 22 de diciembre de 2015. Recuperado el 8 de diciembre de 2015 . 
  29. ↑ ridículo_pez. "Trabajo de división (Episodio III): División sin signo más rápida por constantes" Archivado el 8 de enero de 2022 en Wayback Machine . 2011.
  30. ↑ ridículo_pez. "libdivide, división entera optimizada" . Archivado del original el 23 de noviembre de 2021. Recuperado el 6 de julio de 2021 .
  31. ↑ Warren Jr., Henry S. (2013). Hacker's Delight (2.ª ed.). Addison Wesley - Pearson Education, Inc. ISBN  978-0-321-84268-8.
  32. ↑ LaBudde, Robert A.; Golovchenko, Nikolai; Newton, James; y Parker, David; Massmind: "División binaria por una constante" Archivado el 9 de enero de 2022 en Wayback Machine
  33. ↑ Vowels, RA (1992). "División por 10". Australian Computer Journal . 24 (3): 81– 85.
  34. ↑ L. Popyack, Jeffrey (junio de 2000). "Error de redondeo" . Universidad de Drexel .
  35. ↑ "9. Números de máquina, error de redondeo y propagación de errores" . College of Charleston . 8 de febrero de 2021.

Lecturas adicionales

  • Savard, John JG (2018) [2006]. "Técnicas aritméticas avanzadas" . quadibloc . Archivado del original el 3 de julio de 2018. Recuperado el 16 de julio de 2018 .
Lecturas relacionadas
6 articulos
AlgoritmoAlgoritmoEn matemáticas y ciencias de la computación , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigu...EnteroLos números enteros dispuestos en una línea numérica Un número entero es el número cero ( 0 ), un número natural positivo (1, 2, 3, . . .), o la ne...12 manzanas divididas en 4 grupos de 3 cada uno.CocienteEn aritmética , un cociente (del latín : quotiens 'cuántas veces', pronunciado / ˈk w oʊ ʃ ən t / ) es una cantidad producida por la división de do...RestoRestoDivisión de enteros con resto. En matemáticas , el resto es la cantidad "que queda" después de realizar algún cálculo. En aritmética , el resto es ...División euclidianaDivisión euclidianaEn aritmética , la división euclidiana (o división con resto ) es el proceso de dividir un número entero (el dividendo) por otro (el divisor), de f...Algoritmo de multiplicaciónUn algoritmo de multiplicación es un algoritmo (o método) para multiplicar dos números. Dependiendo del tamaño de los números, algunos algoritmos s...