Sistemas de Numeración | Serie Computación y Programación #5

Saludos queridos asiduos lectores de mi blog, bienvenidos. Este post es la cuarta entrega de la serie Computación y Programación, en el seguiremos tratando el tema de los sistemas de numeración y su representación numérica en las diferentes bases. En esta oportunidad trataremos el Algoritmo de Karatsuba, el cual es un algoritmo para realizar multiplicaciones rápidas. Estos temas son parte de un curso de Programación y diseño de algoritmos.

La Serie Computación y Programación en su primera edición, consiste en una entrega diaria, donde hablaremos de un tema, en la misma abordaremos los aspectos teóricos, describiremos algunos ejemplos con el objetivo de visualizar y explicar como aplicar lo tratado durante la publicación. La misma está dirigida al público en general, pero con especial atención a estudiantes universitarios, que deseen estudiar o estudien computación, ingeniería en computación y carreras afines. Estoy abierto a sus comentarios y dudas que puedan surgir en el desarrollo del mismo. Sin perder más tiempo, iniciemos.

---

---

El Algoritmo de Karatsuba

Como ya hemos visto, todos los procesos para realizar las representaciones numéricas entre las diferentes bases numéricas, lo podemos describir como un algoritmo. Incluso sumar números, se puede describir como procesos algorítmicos.

Ahora bien, el Algoritmo de Karatsuba nos provee un procedimiento para realizar productos de números muy grandes, pero de manera mucho más eficiente o rápida.

Este algoritmo fue desarrollado por el Matemático Ruso Anatolii Alexeevitch Karatsuba y por el otro Matemático Ruso Yuri Petrovich Ofman aproximadamente alrededor del año 1960 y publicado oficialmente en el año1962, en Proceedings of the USSR Academy of Sciences #145.

• A. Karatsuba and Yu. Ofman. Multiplication of Many-Digital Numbers by Automatic Computers. Translation in Physics-Doklady, 7, pp. 595–596. 1963 y Proceedings of the USSR Academy of Sciences 145: 293-294. 1962.

Con este algoritmo, podemos decir que el procedimiento usado es del tipo coloquialmente hablando divide y vencerás, ya que con este algoritmo, se reducen los posibles productos que se producen al multiplicar dos número naturales de n dígitos, a 4 productos de número de n/2 dígitos.

A manera general, podemos decir que reduce el producto de dos números de n dígitos aproximadamente:

posibles productos de un solo dígito, el cual es exacto cuando n es una potencia de 2.

Así, tenemos entonces un algoritmo más rápido, que el algoritmo básico del producto de números naturales, que requiere

productos posibles de un solo dígito. Podemos tratar un caso particular, si tenemos:

entonces el número de productos exactos es:

respectivamente.

En resumen, la idea principal y básica del Algoritmo de Karatsuba es construir una fórmula o ecuación que nos permita poder calcular el producto de dos números naturales grandes, digamos, a y b, usando tres multiplicaciones de números más pequeños que los dados inicialmente, cada uno con aproximadamente la mitad de dígitos de a o de b, además, de algunas sumas.

Formalmente:
Si a y b son dos números naturales de n dígitos escritos en forma de representación decimal. Entonces, para cualquier entero positivo m menor que n, uno puede separar los dos números dados de la siguiente manera:

Entonces, el producto es

donde

Como podemos apreciar, las ecuaciones anteriores necesitan de 4 productos, pero estos pueden ser calculados con solo tres multiplicaciones, esto es, que una de los cuatro posibles productos podría ser descartado usando algunas sumas adicionales con:

ya que

---

---

Ejemplo 01: Calcular el producto de 1234 y 6789.

Para calcular el producto de estos dos número siguiendo el algoritmo antes descrito, tenemos que elegir m=2, así tenemos lo siguiente:

donde

Luego,

Entonces, tenemos que el producto es igual a:

---

Queridos amigos y lectores, espero hayan disfrutado de este quinto post de la serie de Computación y Programación, de igual manera los invito para la próxima entrega de esta serie, donde continuaremos tratando este tan bonito tema de los sistemas de numeración y otros aspectos. Espero que esto pueda servir de apoyo a ustedes, hijos, nietos, sobrinos o amigos que quieran aprender un poco más del maravilloso mundo de las matemáticas y la computación. No olviden dejar sus comentarios. Saludos y nos leemos pronto.

Si desean consultar un poco más del tema pueden usar las siguientes referencias.

• Knuth, Donald Ervin. The art of computer programming. Vol. 1, 2, y 3. Pearson Education, 1997.
• Knuth, Donald Ervin. Fundamental algorithms: the art of computer programming. 1973.
• Knuth, Donald Ervin. Computer programming as an art. ACM Turing award lectures. ACM, 2007.
• A. A. Karatsuba and Yu. Ofman. Multiplication of Many-Digital Numbers by Automatic Computers. Translation in Physics-Doklady, 7, pp. 595–596. 1963 y Proceedings of the USSR Academy of Sciences 145: 293-294. 1962.
• A. A. Karatsuba. The Complexity of Computations. Proceedings of the Steklov Institute of Mathematics 211:169-183. 1995.

---

También los invito a leer las anteriores publicaciones de está serie de Computación y Programación, que estoy seguro serán de su interés:

Sistemas de Numeración #1	Sistemas de Numeración #2
Sistemas de Numeración #3	Sistemas de Numeración #4

---

Todas las ecuaciones fueron creadas y editadas por @abdulmath con , y GIMP.

_{Imagen elaborada por @abdulmath, diseñadas y editada con Karbon y GIMP.}