La aritmética computacional estudia métodos eficientes para realizar operaciones matemáticas fundamentales mediante algoritmos optimizados. En este artículo, exploraremos los algoritmos de suma, resta, multiplicación y división en el contexto de la computación, destacando su implementación y complejidad.
1. Suma y Resta
En el sistema decimal y binario, la suma y la resta se realizan de manera similar, con propagación de acarreo o préstamo.
1.1 Algoritmo de Suma
Dados dos números \(A\) y \(B\) de \(n\) dígitos cada uno:
- Se alinean los números por la derecha.
- Se suman dígito a dígito desde la posición menos significativa.
- Si la suma excede la base (\(b\)), se genera un acarreo hacia la siguiente posición.
- Se repite hasta completar la suma.
En el caso binario (\(b = 2\)), la suma se reduce a:
$$ \large 0+0 = 0, \quad 1+0 = 1, \quad 0+1 = 1, \quad 1+1 = 10 $$
La complejidad es \(O(n)\), ya que se procesan \(n\) dígitos.
1.2 Algoritmo de Resta
La resta sigue un procedimiento similar pero con préstamos cuando el minuendo es menor que el sustraendo en una posición dada:
- Se alinean los números por la derecha.
- Se restan los dígitos en cada posición.
- Si el minuendo es menor que el sustraendo, se toma un préstamo de la posición siguiente.
- Se repite hasta completar la resta.
En binario:
$$ 0 – 0 = 0, \quad 1 – 0 = 1, \quad 1 – 1 = 0, \quad 0 – 1 = 1 \text{ (con préstamo de la siguiente posición)} $$
La complejidad es \(O(n)\).
2. Multiplicación
2.1 Algoritmo Tradicional
El método clásico de multiplicación sigue la estructura de sumas de productos parciales:
- Se multiplican los dígitos de un número con cada dígito del otro.
- Se desplazan los productos parciales según su posición.
- Se suman los productos parciales.
Para dos números de nn dígitos, la complejidad es \(O(n^2)\).
2.2 Algoritmo de Karatsuba
Este algoritmo divide los números en partes más pequeñas y reduce la cantidad de multiplicaciones necesarias mediante: $$ \Large XY = X_1Y_1 \cdot b^{2m} + (X_1Y_2 + X_2Y_1) \cdot b^m + X_2Y_2 $$
donde \(X_1, X_2, Y_1, Y_2\) son mitades de \(X\) y \(Y\), y \(b^m\) es la base elevada a la mitad del tamaño.
La complejidad mejora a \(O(n^{\log_2 3}) \approx O(n^{1.585})\).
3. División
3.1 Algoritmo de División Larga
La división larga sigue estos pasos:
- Se toma el primer segmento del dividendo con al menos el mismo número de dígitos que el divisor.
- Se encuentra el cociente de la división de este segmento entre el divisor.
- Se multiplica el divisor por este cociente y se resta del segmento tomado.
- Se baja el siguiente dígito del dividendo y se repite hasta completar la operación.
La complejidad es \(O(n^2)\), aunque optimizaciones como la división binaria reducen el costo en algunos casos.
3.2 División Rápida de Newton-Raphson
Basada en el método iterativo: $$ \huge x_{k+1} = x_k(2 – Dx_k) $$
donde \(D\) es el divisor. Convergencia rápida reduce la complejidad a \(O(n \log n)\).
Conclusión
Los algoritmos de operaciones básicas en aritmética computacional varían en eficiencia dependiendo de la estructura numérica y la implementación en hardware o software. Métodos como Karatsuba y Newton-Raphson optimizan la multiplicación y la división respectivamente, mostrando la importancia del diseño algorítmico en el procesamiento numérico.