create account

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

View this thread on: hive.blogpeakd.comecency.com
· @abdulmath · (edited)
$7.62
Sistemas de Numeración | Serie Computación y Programación #5
<div class="text-justify">
<div class="pull-right"><img src="https://cdn.steemitimages.com/DQmcmr2RbL8btQssCtVrErcVkKuU5L1b1WEDgEqKVfuEXAQ/Programacion.png"/><center><sub><sub>Elaborada por @abdulmath, con GIMP.</sub></sub></center></div>Saludos queridos asiduos lectores de mi blog, bienvenidos. Este post es la cuarta entrega de la serie <b>Computación y Programación</b>, 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 <b>Algoritmo de  Karatsuba</b>, 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.

<br>La Serie <b>Computación y Programación</b> 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.
<hr>
<center>
https://cdn.steemitimages.com/DQmdpxUb7HtnNdmxthWLKfUjnPA5sind9336Fgw5iy7pfv3/SeparadorGMath12.png</center>
<hr>

<h2><div class="phishy">El Algoritmo de  Karatsuba</div></h2>

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 <b>Algoritmo de Karatsuba</b> 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](https://es.wikipedia.org/wiki/Anatoli_Karatsuba) y por el otro Matemático Ruso [Yuri Petrovich Ofman](https://es.wikipedia.org/wiki/Yuri_Petr%C3%B3vich_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. <i>Multiplication of Many-Digital Numbers by Automatic Computers</i>. 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 <b>divide y vencerás,</b> ya que con este algoritmo, se reducen los posibles productos que se producen al multiplicar dos número naturales de <b>n</b> dígitos, a 4 productos de número de <b>n/2</b> dígitos.

A manera general, podemos decir que reduce el producto de dos números de <b>n</b> dígitos aproximadamente:
<center>https://cdn.steemitimages.com/DQmWnvtjWGLz6nawdtZzZd6HeB5K18tSfaNreQm1X5aBx6P/Img41.png</center>
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
<center>https://cdn.steemitimages.com/DQmfBvMPmXCEPFCX6ehXFuKNSRf7TByhzqMrUq4E8gphG8R/Img42.png</center>
productos posibles de un solo dígito. Podemos tratar un caso particular, si tenemos:
<center>https://cdn.steemitimages.com/DQmbKMy11p5ys1DNzSTXH6D5SgLcQUAfsxwmHJi5cu5CiYV/Img43.png</center>
entonces el número de productos exactos es:
<center>https://cdn.steemitimages.com/DQmf9JqYu7iRWNFj7JdwG169RNraW24cb17RSGAHG9hFjNF/Img44.png</center>
respectivamente.

En resumen, la idea principal y básica del <b>Algoritmo de Karatsuba</b> es construir una fórmula o ecuación que nos permita poder calcular el producto de dos números naturales grandes, digamos, <b>a</b> y <b>b</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:
<center>https://cdn.steemitimages.com/DQmQPhgcLerRjRoHYq5cD4gwatsUKuE4kMCMkNzYTHbjMVd/Img45.png</center>
Entonces, el producto es
<center>https://cdn.steemitimages.com/DQmUoy9WxTbXf5APLWdqevoSaMPgsFUETSf9u1WJtz1Efe6/Img46.png</center>
donde
<center>https://cdn.steemitimages.com/DQmdEFgjFYvUfUjZEzfgwN5ZjJtDE55c4pHdTuUbJ7WwVnA/Img47.png</center>
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:
<center>https://cdn.steemitimages.com/DQmNm5FLgWQ4ZL7rQsA7E39VMempR9QicT54jRYmCAUTdeg/Img48.png</center>
ya que
<center>https://cdn.steemitimages.com/DQmWgTPyvS6EXCtZ6yuBpytMawLv8AB8UZR8pSxkB6vmKCA/Img49.png</center>

<hr>
<center>https://cdn.steemitimages.com/DQmXDYS97XY5Ak4JQ8dRoTDseYfjTrW9gfCtFWUrNGEufe5/SeparadorGMath19.png</center>
<hr>

<h4>Ejemplo 01:  Calcular el producto de 1234 y 6789.</h4>

<br>Para calcular el producto de estos dos número siguiendo el algoritmo antes descrito, tenemos que elegir m=2, así tenemos lo siguiente:
<center>https://cdn.steemitimages.com/DQmWG3EhhYrgCaz9iH2wqF7szaZrthxXTrxNjVR8erFCAfA/Img50.png</center>
donde
<center>https://cdn.steemitimages.com/DQmbz77aQN9JutBanoQHuAGBCx1pmzGgwDXq8D6LPtJET2J/Img51.png</center>
Luego, 
<center>https://cdn.steemitimages.com/DQmTaKf8BNsw9YHg83CVJTNMXiaypmsM8h6KgnFVX6Gq94G/Img52.png</center>
Entonces, tenemos que el producto es igual a:
<center>https://cdn.steemitimages.com/DQma4QSQcmjUtSt2LJKwSEUynbbQJiSrYixXWWBpq4WgGLB/Img53.png</center>

<center>https://cdn.steemitimages.com/DQmdpxUb7HtnNdmxthWLKfUjnPA5sind9336Fgw5iy7pfv3/SeparadorGMath12.png</center>
<hr>
Queridos amigos y lectores, espero hayan disfrutado de este quinto post de la serie de <b>Computación y Programación</b>, 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.

<br>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. <i>Multiplication of Many-Digital Numbers by Automatic Computers</i>. Translation in Physics-Doklady, 7, pp. 595–596. 1963 y Proceedings of the USSR Academy of Sciences 145: 293-294. 1962.
+  A. A. Karatsuba. <i>The Complexity of Computations</i>. Proceedings of the Steklov Institute of Mathematics 211:169-183. 1995.

<hr>

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

|<a href="https://steemit.com/castellano/@abdulmath/sistemas-de-numeracion-or-serie-computacion-y-programacion-1">Sistemas de Numeración #1</a>|<a href="https://steemit.com/castellano/@abdulmath/sistemas-de-numeracion-or-serie-computacion-y-programacion-2">Sistemas de Numeración #2</a>|
|---|---|
|<a href="https://steemit.com/spanish/@abdulmath/sistemas-de-numeracin-serie-computacin-y-programacin-3-1528868926"><b>Sistemas de Numeración #3</b></a>|<a href="https://steemit.com/spanish/@abdulmath/sistemas-de-numeracin-serie-computacin-y-programacin-4-1528950578"><b>Sistemas de Numeración #4</b></a>|
<hr>

Todas las ecuaciones fueron creadas y editadas por @abdulmath con https://cdn.steemitimages.com/DQmYbufK9HG9LpAUVgEcFSNVmZG2irkjVy1duWbYqVyVtf4/LateX.png, y GIMP.

<center>
https://cdn.steemitimages.com/DQmPqz2gevojVdxDQRk7wFj5uHqtD8VrmDKaAC3FYqrDKfJ/FinalGMath01.png
<br><sub>Imagen elaborada por @abdulmath, diseñadas y editada con Karbon y GIMP.</sub></center>
</div>
👍  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , and 77 others
properties (23)
authorabdulmath
permlinksistemas-de-numeracion-or-serie-computacion-y-programacion-5
categoryspanish
json_metadata{"tags":["spanish","knowledge","technological","proconocimiento","stem-espanol"],"users":["abdulmath"],"image":["https://cdn.steemitimages.com/DQmcmr2RbL8btQssCtVrErcVkKuU5L1b1WEDgEqKVfuEXAQ/Programacion.png","https://cdn.steemitimages.com/DQmdpxUb7HtnNdmxthWLKfUjnPA5sind9336Fgw5iy7pfv3/SeparadorGMath12.png","https://cdn.steemitimages.com/DQmWnvtjWGLz6nawdtZzZd6HeB5K18tSfaNreQm1X5aBx6P/Img41.png","https://cdn.steemitimages.com/DQmfBvMPmXCEPFCX6ehXFuKNSRf7TByhzqMrUq4E8gphG8R/Img42.png","https://cdn.steemitimages.com/DQmbKMy11p5ys1DNzSTXH6D5SgLcQUAfsxwmHJi5cu5CiYV/Img43.png","https://cdn.steemitimages.com/DQmf9JqYu7iRWNFj7JdwG169RNraW24cb17RSGAHG9hFjNF/Img44.png","https://cdn.steemitimages.com/DQmQPhgcLerRjRoHYq5cD4gwatsUKuE4kMCMkNzYTHbjMVd/Img45.png","https://cdn.steemitimages.com/DQmUoy9WxTbXf5APLWdqevoSaMPgsFUETSf9u1WJtz1Efe6/Img46.png","https://cdn.steemitimages.com/DQmdEFgjFYvUfUjZEzfgwN5ZjJtDE55c4pHdTuUbJ7WwVnA/Img47.png","https://cdn.steemitimages.com/DQmNm5FLgWQ4ZL7rQsA7E39VMempR9QicT54jRYmCAUTdeg/Img48.png","https://cdn.steemitimages.com/DQmWgTPyvS6EXCtZ6yuBpytMawLv8AB8UZR8pSxkB6vmKCA/Img49.png","https://cdn.steemitimages.com/DQmXDYS97XY5Ak4JQ8dRoTDseYfjTrW9gfCtFWUrNGEufe5/SeparadorGMath19.png","https://cdn.steemitimages.com/DQmWG3EhhYrgCaz9iH2wqF7szaZrthxXTrxNjVR8erFCAfA/Img50.png","https://cdn.steemitimages.com/DQmbz77aQN9JutBanoQHuAGBCx1pmzGgwDXq8D6LPtJET2J/Img51.png","https://cdn.steemitimages.com/DQmTaKf8BNsw9YHg83CVJTNMXiaypmsM8h6KgnFVX6Gq94G/Img52.png","https://cdn.steemitimages.com/DQma4QSQcmjUtSt2LJKwSEUynbbQJiSrYixXWWBpq4WgGLB/Img53.png","https://cdn.steemitimages.com/DQmYbufK9HG9LpAUVgEcFSNVmZG2irkjVy1duWbYqVyVtf4/LateX.png","https://cdn.steemitimages.com/DQmPqz2gevojVdxDQRk7wFj5uHqtD8VrmDKaAC3FYqrDKfJ/FinalGMath01.png"],"links":["https://es.wikipedia.org/wiki/Anatoli_Karatsuba","https://es.wikipedia.org/wiki/Yuri_Petr%C3%B3vich_Ofman","https://steemit.com/castellano/@abdulmath/sistemas-de-numeracion-or-serie-computacion-y-programacion-1","https://steemit.com/castellano/@abdulmath/sistemas-de-numeracion-or-serie-computacion-y-programacion-2","https://steemit.com/spanish/@abdulmath/sistemas-de-numeracin-serie-computacin-y-programacin-3-1528868926","https://steemit.com/spanish/@abdulmath/sistemas-de-numeracin-serie-computacin-y-programacin-4-1528950578"],"app":"steemit/0.1","format":"markdown"}
created2018-06-15 19:13:21
last_update2018-06-15 19:17:21
depth0
children9
last_payout2018-06-22 19:13:21
cashout_time1969-12-31 23:59:59
total_payout_value5.817 HBD
curator_payout_value1.804 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length8,413
author_reputation44,913,742,198,559
root_title"Sistemas de Numeración | Serie Computación y Programación #5"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id60,894,378
net_rshares3,041,540,031,331
author_curate_reward""
vote details (141)
@abdulmath ·
$0.51
Hola @angelica7, gracias por tomarte el tiempo de leerme, en estos momentos de mundial. Siempre trabajando. No bajando los brazos. Saludos y un abrazo. Besos.
👍  ,
properties (23)
authorabdulmath
permlinkre-abdulmath-sistemas-de-numeracion-or-serie-computacion-y-programacion-5-20180615t195644485z
categoryspanish
json_metadata{"tags":["spanish"],"users":["angelica7"],"app":"steemit/0.1"}
created2018-06-15 19:56:45
last_update2018-06-15 19:56:45
depth1
children0
last_payout2018-06-22 19:56:45
cashout_time1969-12-31 23:59:59
total_payout_value0.384 HBD
curator_payout_value0.126 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length158
author_reputation44,913,742,198,559
root_title"Sistemas de Numeración | Serie Computación y Programación #5"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id60,898,040
net_rshares204,353,260,359
author_curate_reward""
vote details (2)
@angelica7 ·
Felicitaciones por tu trabajo @abdulmath. Aprendiendo y trabajando con el fútbol en vivo.
Buena vibra.
👍  , , , ,
properties (23)
authorangelica7
permlinkre-abdulmath-sistemas-de-numeracion-or-serie-computacion-y-programacion-5-20180615t194324845z
categoryspanish
json_metadata{"tags":["spanish"],"users":["abdulmath"],"app":"steemit/0.1"}
created2018-06-15 19:43:27
last_update2018-06-15 19:43:27
depth1
children0
last_payout2018-06-22 19:43:27
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length102
author_reputation500,346,430,788,126
root_title"Sistemas de Numeración | Serie Computación y Programación #5"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id60,896,996
net_rshares2,845,498,039
author_curate_reward""
vote details (5)
@codebyte ·
<center>
<h4>¡Felicitaciones tu publicación ha sido seleccionada para ser destacada por el  Proyecto de Curación @Codebyte! </h4>

![comments.png](https://steemitimages.com/DQmZiH5YECWcnEj7WLbNnJ9Q3JrRjiqCtiuhe4o8CVc3ix6/comments.png)

Si deseas contribuir y conocer sobre este proyecto puedes seguirlo y estar atento a sus publicaciones. Ingresando [aquí](https://steemit.com/spanish/@codebyte/reporte-de-curacion-codebyte-15-06-18) podrás ver el reporte en donde tu publicación ha sido destacada.

</center>
properties (22)
authorcodebyte
permlinkre-abdulmath-sistemas-de-numeracion-or-serie-computacion-y-programacion-5-20180616t025102358z
categoryspanish
json_metadata{"tags":["spanish"],"users":["codebyte"],"image":["https://steemitimages.com/DQmZiH5YECWcnEj7WLbNnJ9Q3JrRjiqCtiuhe4o8CVc3ix6/comments.png"],"links":["https://steemit.com/spanish/@codebyte/reporte-de-curacion-codebyte-15-06-18"],"app":"steemit/0.1"}
created2018-06-16 02:51:06
last_update2018-06-16 02:51:06
depth1
children1
last_payout2018-06-23 02:51:06
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length509
author_reputation674,171,012,317
root_title"Sistemas de Numeración | Serie Computación y Programación #5"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id60,930,479
net_rshares0
@abdulmath ·
Saludos @codebyte, muchas gracias por su apoyo, espero sigan llevando su proyecto por buen camino. Saludos y un abrazo extensivo a todo el equipo.
properties (22)
authorabdulmath
permlinkre-codebyte-re-abdulmath-sistemas-de-numeracion-or-serie-computacion-y-programacion-5-20180616t131306013z
categoryspanish
json_metadata{"tags":["spanish"],"users":["codebyte"],"app":"steemit/0.1"}
created2018-06-16 13:13:15
last_update2018-06-16 13:13:15
depth2
children0
last_payout2018-06-23 13:13:15
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length146
author_reputation44,913,742,198,559
root_title"Sistemas de Numeración | Serie Computación y Programación #5"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id60,977,383
net_rshares0
@duque ·
hola profe
properties (22)
authorduque
permlinkre-abdulmath-sistemas-de-numeracion-or-serie-computacion-y-programacion-5-20180616t004036336z
categoryspanish
json_metadata{"tags":["spanish"],"app":"steemit/0.1"}
created2018-06-16 00:41:03
last_update2018-06-16 00:41:03
depth1
children2
last_payout2018-06-23 00:41:03
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length10
author_reputation787,503,542,576
root_title"Sistemas de Numeración | Serie Computación y Programación #5"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd0
post_id60,920,432
net_rshares0
@abdulmath ·
Hola @duque. Gracias por visitarme, Saludos y un abrazo.
properties (22)
authorabdulmath
permlinkre-duque-re-abdulmath-sistemas-de-numeracion-or-serie-computacion-y-programacion-5-20180616t131355032z
categoryspanish
json_metadata{"tags":["spanish"],"users":["duque"],"app":"steemit/0.1"}
created2018-06-16 13:16:03
last_update2018-06-16 13:16:03
depth2
children0
last_payout2018-06-23 13:16:03
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length56
author_reputation44,913,742,198,559
root_title"Sistemas de Numeración | Serie Computación y Programación #5"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id60,977,634
net_rshares0
@abdulmath ·
Hola @duque. Gracias por visitarme, Saludos y un abrazo.
properties (22)
authorabdulmath
permlinkre-duque-re-abdulmath-sistemas-de-numeracion-or-serie-computacion-y-programacion-5-20180616t131759743z
categoryspanish
json_metadata{"tags":["spanish"],"users":["duque"],"app":"steemit/0.1"}
created2018-06-16 13:18:06
last_update2018-06-16 13:18:06
depth2
children0
last_payout2018-06-23 13:18:06
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length56
author_reputation44,913,742,198,559
root_title"Sistemas de Numeración | Serie Computación y Programación #5"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id60,977,816
net_rshares0
@utopian-io ·
#### Hi @abdulmath!

Your post was upvoted by utopian.io in cooperation with steemstem - supporting knowledge, innovation and technological advancement on the Steem Blockchain.

#### Contribute to Open Source with utopian.io
Learn how to contribute on <a href="https://join.utopian.io">our website</a> and join the new open source economy.

**Want to chat? Join the Utopian Community on Discord https://discord.gg/h52nFrV**
properties (22)
authorutopian-io
permlink20180617t141603357z
categoryspanish
json_metadata{"tags":["utopian.tip"],"app":"utopian-io"}
created2018-06-17 14:16:03
last_update2018-06-17 14:16:03
depth1
children1
last_payout2018-06-24 14:16:03
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length423
author_reputation152,955,367,999,756
root_title"Sistemas de Numeración | Serie Computación y Programación #5"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id61,100,072
net_rshares0
@abdulmath ·
Gracias a la comunidad de @utopian-io por el apoyo, me estimulan a seguir trabajando. Saludos.
properties (22)
authorabdulmath
permlinkre-utopian-io-20180617t141603357z-20180617t215011879z
categoryspanish
json_metadata{"tags":["spanish"],"users":["utopian-io"],"app":"steemit/0.1"}
created2018-06-17 21:50:12
last_update2018-06-17 21:50:12
depth2
children0
last_payout2018-06-24 21:50:12
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length94
author_reputation44,913,742,198,559
root_title"Sistemas de Numeración | Serie Computación y Programación #5"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id61,145,237
net_rshares0