versión PDF
Contents
1. del arreglo de enteros comenzando por el d gito menos significativo esta tarea la realiza la funci n void readNumber int aa int x de tal suerte que las operaciones validaciones y manipulaci n de dichos n meros en el programa se hace sobre arreglos de enteros 2 2 Codificaci n de Suma utilizando acarreos Se codific la funci n void add int A int B int C para computar la suma de dos n meros mayores de 100 d gitos representados en forma de arreglo de enteros Recibe como entrada los n meros arreglos A B y C y regresa la suma A B en C La suma de dos n meros se realiza usando el m todo tradicional es decir se suma d gito a d gito cada elemento del mismo arreglo cuando la suma es mayor que la base 10 se hace acarreo y se contin a con el siguiente hasta recorrer todos los elementos de los arreglos ten idioma ingl s 1 bill n equivale a mil millones as que 2 x 10 es igual a 2 billones en idioma ingl s 2 2 1 Algoritmo Suma utilizando acarreos El procedimiento anterior se encuentra en el seudoc digo del algoritmo lalgorithm1 Algorithm 1 Algoritmo para suma de dos n meros grandes representados como arreglos de enteros procedure ADD A B Cl gt Output C A B BASE 10 for cada ndice en A i y B i do sum Ali Bli carry if sum gt BASE then carry 1 sum sum BASE else carry 0 end if Cli sum end for end procedure Dado que para realizar la suma es necesario2. donde plante algunos problemas de complejidad computacional Kolmogorov estableci que dos d gitos de n bits no podr an ser multiplicados en menos de n operaciones En una semana Karatsuba un estudiante de 25 a os encontr un algoritmo Divide y vencer s que multiplicaba dos n meros de n d gitos en n 9 operaciones refutando as la suposici n inicial de Kolmogorov Kolmogorov hizo p blico tal descrubrimiento hasta 1962 en la revista cient fica sovi tica Proceedings of the USSR Academy of Sciences El art culo hab a sido escrito por Kolmogorov en colaboraci n con Yuri Ofman pero nombraba a A Karatsuba y Yu Ofman como los autores Karatsuba se dio cuenta de la publicaci n cuando recibi una copia del art culo por parte de la editorial de la revista 2 3 2 Algoritmo de Karatsuba Como se ha visto arriba el m todo tradicional para multiplicar 2 n meros de n bits requiere n multiplicaciones El algoritmo de Karatsuba s lo requiere n 9 o aproximadamente nl opera ciones Sea x y y dos n meros de n bits partimos a x y y en dos mitades como se muestra en la figura figure2 Figure 2 Partici n de zx y y Si tratamos cada mitad como un n mero de gt bits entonces el producto lo podemos expresar como sigue xy a2 b c2 d 1 ac2 ad bc 22 bd 2 La ecuaci n calcula el producto de x y y con cuatro multiplicaciones de n meros de 5 bits y algunas sumas y corrimientos multiplic
3. numX int numY int result la cual im plementa el algoritmo de Karatsuba la varaible B representa la base decimal El algoritmo algorithm2 contiene dicho seudoc digo 2 3 3 Otras funciones codificadas Las siguientes funciones son necesarias para el funcionamiento del programa por ejemplo la funci n toLeft es de suma importancia ya que hace un corrimiento a la izquierda que equivale a multiplicar un n mero por una potencia de su base en este caso decimal y es un paso necesario por el algoritmo de Karatsuba e main Funci n principal del programa Desde aqu se invoca a la funci n karatsuba e karatsuba Funci n que implementa el algoritmo de karatsuba para multiplicar dos n meros grandes e add Implementa la suma de dos n meros grandes e substraction Implementa la resta de dos n meros grandes Algorithm 2 Multiplicaci n por m todo de Karatsuba procedure KARATSUBA A B C gt Output result numX numY a mitad izquierda de numX b mitad derecha de numX c mitad izquierda de num Y d mitad derecha de num Y ul a b u2 c d u lt KARATSUBA ul u2 U 4 KARATSUBA a c w 4 KARATSUBA b d return v B u v w 4 B2 w end procedure e intToArray Convierte a arreglos de enteros un n mero ingresado en modo caracter e toLeft Hace un corrimiento a la izquierda equivalente a multiplicar a un n mero por una potencia de su base e substraction Implementa la
4. resta de dos n meros grandes e incrementa Incrementa en 1 un n mero grande e makeEvenSize Agrega el n mero de ceros necesarios a un arreglo para que su longitud sea par logrando que se pueda dividir en 2 por el algoritmo de Karatsuba e doEqualsDigits Convierte la longitud de dos arreglos en iguales agregando ceros e putsOnes Funci n auxiliar que inicializa arreglos e readNumber Convierte n meros le dos en caracter en representaci n de arreglos de enteros Los c digos de estas funciones se pueden ver en el archivo main c 3 Manual de usuario 3 1 Compilaci n del programa Para la compilaci n del programa se debe tener instalado el compilador GCC Luego ir a la carpeta del c digo fuente y escribir lo siguiente gcc main c o main o 3 2 Ejecuci n Para ejecutar el programa basta abrir una l nea de comandos e ir a la carpeta del c digo fuente del programa previamente compilado y escribir lo siguiente y presionar la tecla enter main o option donde option es el tipo de operaci n que deseamos hacer 1 para sumar 2 para multiplicar mediante algoritmo de Karatsuba Por ejemplo Para hacer una suma main o 1 Para multiplicar por Karatsuba main o 2 a continuaci n el progama solicita los 2 n meros a calcular se debe ingresar cada n mero mediante el teclado o copiando y pegando y presionando la tecla enter tras haber ingresado cada uno El programa calcular el resultado Ejemplo de e
5. 646765080376060 2876271973043325040489004042834683045180362047526041049871720052217399054563078056908757059254435 Yanis MacBook Air karatsubaNB yani i Figure 11 Ejecuci n de multiplicaci n de Karatsuba para d gitos mayores de 100 Se compara el resultado obtenido en Mathematica y es correcto 80600 i Untitled 2 In 9 57 444 979 123 456 123 456 789 123 456 789 123 456789 123 456 789123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 121 12 894867 963 748 695574 791 234 567 891 234 567 891 234 567 891 234 567 891 234 567 891 234 567 891 234 567 891 234567 891 234 567 891 235 Out 9 J 740745 420 977 266 989 862 829 335 359 366 276 426 684 974 081005 971 735 326 969 389 647 967 043 968 964 698 289 962 352 610960 006 931 950803 760 602 876271 973 043 325040 489 004 042834 683 045 180 362 047 526 041 049 871 720052 217 399 054563 078 056 908757 059 254 435 prime factorization divisors scientific notation digits gt more n E Figure 12 Comparaci n con Mathematica References 1 Ullman Aho Hopcroft The Design and Analysis Of Computer Algorithms Addison Wesley 1974 2 C H Papadimitriou S Dasgupta and U V Vazirani Algorithms 10
6. 6789123456789123456789123456789123456789123456789123456789123456789123456789123456789123 Num 2 935634123456123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123 RESULTADO 1392423246912246913578246913578246913578246913578246913578246913578246913578246913578246913578246913578246 Yanis MacBook Air karatsubaNB yani Figure 7 Ejecuci n del programa con n mero de m s de 100 d gitos Se compara el resultado obtenido en Mathematica y es correcto eoo Untitled 2 h 456789 123 456 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456789 123 456 789123 456 789 123 456 789 123 935634123 456 123 456789 123 456789 123 456 789123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 Out 7 1392423 246 912 246913578 246 913578 246 913 578246 913 578 246 913 578 246 913578 246 913 578246 913578246 913 578 246913 578 246 prime factorization divisors scientific notation digits more E Figure 8 Comparaci n con Mathematica 4 3 Ejemplo 3 Multiplicaci n con Karatsuba Yanis MacBook Air karatsubaNB yani main o 2 Num 1 456789123456123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123 Num 2 935634123456123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123 RESULTADO 4273874911291610334871006290303113944624111598945109168186106961073424096
7. 91662597345982785000302972654623138187541484 5449788998017689232585589467153489701721389936289290170857190405425090639992990874560891109129 Yanis MacBook Air karatsubaNB yani E Figure 9 Ejecuci n de multiplicaci n de Karatsuba para d gitos mayores de 100 Se compara el resultado obtenido en Mathematica y es correcto eoo Untitled 2 Ins 456789 123 456 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 935 634123 456 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 456 789 123 Out 8 427387 491129161033 487 100629 030 311 394462 411 159 894510 925 326 610690 758 710 456 190 810 221 622909 987 055 009 752 487 108 881875 414 845 449788 998 017 689232 585 589 467153 489 701 721389 936 289 290 170 857 190 405 425 090 639 992 990 874 560891 109 129 prime factorization divisors scientific notation digits more a E Figure 10 Comparaci n con Mathematica 4 4 Ejemplo 4 Multiplicaci n con Karatsuba Yanis MacBook Air karatsubaNB yani main o 2 Num 1 57444979123456123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789121 Num 2 12894867963748695574791234567891234567891234567891234567891234567891234567891234567891234567891234567891235 RESULTADO 740745420977266989862829335359366276426684974081005967566258048336203071104017156666560358543103560419
8. Complejidad Computacional Aritm tica de grandes n meros Multiplicaci n por Karatsuba Yani WWW yaniweb com 25 de febrero de 2014 Resumen Se presenta una implementaci n para computar aritm tica de n meros grandes mayores a 100 d gitos y multiplicaci n de stos mediante el algoritmo de Karatsuba La implementaci n se hizo en lenguaje C Este documento tambi n est en ndice de contenido 2 2 SS wis 9 205 9 9 8 E UR NOR OSUN S S SONOS ROB ss 2 2 1 1 Representaci n de n meros grandes ll sn 2 2 2 Codificaci n de Suma utilizando acarreos lll sn 2 2 2 1 Algoritmo Suma utilizando acarreos llle 3 CD 3 2L MS xxx 3 bbOEOR ECKE OX Ac3 o ww AR S s d rd m E 3 TT 4 2 3 3 Otras funciones codificadas 22e 5 6 3 1 Compilaci n del programa 6 INA NECIO O 6 7 ara E 7 DMPMMDII V 8 AOS 9 rara ras 9 1 Problema Aritm tica de grandes n meros Construir un m dulo para el manejo de n meros enteros grandes n mero de d gitos gt 100 Represente n meros grandes como listas de enteros sin signos Construya la suma de enteros grandes procediendo seg n la intuici n m s elemental llevando acarreos Construya el producto de enteros grandes procediendo seg n el algoritmo de Karatsuba del tipo divide y vencer s que aparece en el libro de Ullman Design and analysis of algorithms 2 Soluci n El program
9. a se codific en lenguaje C se hicieron las funciones aritm ticas solicitadas suma por m todo tradicional y producto por algoritmo de Karatsuba y algunas auxiliares necesarias por las primeras En esta secci n se explica y se referenc an algunos nombres de funciones del programa principal ubicado en el archivo main c el cual contiene toda la codificaci n Dicho archivo fue entregado en el tarball del programa 2 El tarball puede descargarse laqu lo bien desde mi sitio web 2 1 Enfoque de soluci n Debido a que en las computadoras actuales un compilador de lenguaje C representa com nmente a un entero en 32 bits usando 1 bit para el signo y los restantes 31 para el valor num rico es posible trabajar con n meros de hasta 2 x 10 aproximadamente es decir alrededor de 2 mil millones Sin embargo un requerimiento del problema es manejar n meros grandes de m s de 100 d gitos y representar a stos como listas de n meros raz n por la cual es imposible resolver el problema usando tipos de datos primitivos o librer as de precisi n grande que ofrece cada lenguaje de programaci n 2 1 1 Representaci n de n meros grandes Como se explic arriba es imposible almacenar n meros muy grandes en una variable de tipo de dato primitivo en C por lo que la representaci n de estos n meros se hizo mediante arreglos de enteros en base decimal los n meros son le dos por el programa en modo caracter y cada uno es almacenado en una posici n
10. aciones por potencias de la base 2 p 62 El producto z de x y y puede ser computado por el siguiente programa ut a 4 b c d v a c w bd z vx 2 F u v w x22 w el seudoc digo anterior requiere s lo 3 multiplicaciones de n meros de 5 bit y algunas sumas y multiplicaciones por la propia base corrimientos Adem s para evaluar el producto de las operaciones de u v y w se puede invocar recursivamente al procedimiento p 63 Debido a que es un procedimiento recursivo y las sumas y corrimientos requieren n entonces la complejidad computacional de multiplicar dos n meros de n bits est acotado por 2por simplicidad para esta explicaci n asumiremos que n es potencia de 2 es decir el sistema binario sin embargo el programa desarrollado trabaja con sistema decimal T n k para n 1 3 a 3T 5 kn paran gt 1 La soluci n de la recurrencia lalign3 est acotada por arriba por 3 Lp 1093 31 193 Se ha visto que el algoritmo de Karatsuba reduce el n mero de operaciones de cuatro a tres multiplicaciones lo cual reduce en 25 el tiempo computacional en cada nivel de ejecuci n que se invoca recursivamente p 64 La im gen muestra una comparaci n de tiempos del m todo tradicional y la multiplicaci n usando Karatsuba Standard Mi Karatsuba f n 1 Figure 3 Tiempos computacionales de multiplicaci n tradicional y Karatsuba Se codific la funci n int karatsuba int
11. jecuci n figura figure4 Yanis MacBook Air karatsubaNB yani main o 1 Num 1 123456789123456789123456789123456789123456789123456789123 Num 2 456456789123456789123456789123456789123456789123456789123 RESULTADO 579913578246913578246913578246913578246913578246913578246 Yanis MacBook Air karatsubaNB yani D Figure 4 Ejemplo de suma en el programa 4 Ejemplos ejecutados 4 1 Ejemplo 1 Suma Se ejecut una suma de n meros m s grandes que los soportados por los tipos de datos primitivos de C Yanis MacBook Air karatsubaNB yani main o 1 Num 1 123456789123456789123456789123456789123456789123456789123 Num 2 456456789123456789123456789123456789123456789123456789123 RESULTADO 579913578246913578246913578246913578246913578246913578246 Yanis MacBook Air karatsubaNB yani E Figure 5 Ejecuci n de suma del programa Se compara el resultado obtenido en Mathematica y es correcto In 10 2 Untitled 2 123 456 789 123 456 789 123 456789 123 456 789 123 456 789 123 456 789 123 456 456 789 123 456 789 123 456789 123 456 789 123 456 789 123 456 789 123 Out 10J 579913 578 246913578 246 913578 246 913 578246 913 578 246 913 578 246 prime factorization divisors scientific notation nextprime more m E Figure 6 Comparaci n con Mathematica 4 2 Ejemplo 2 Suma Se ejecut la suma con n meros grandes mayores de 100 d gitos Yanis MacBook Air karatsubaNB yani main o 1 Num 1 45678912345612345
12. recorrer los dos arreglos de entrada de n elementos es claro que nuestro algoritmo tiene una complejidad lineal es decir T n n 2 3 Codificaci n de Producto con algoritmo de Karatsuba La multiplicaci n mediante el m todo tradicional aprendido en la escuela b sica es quiz la forma m s conocida de multiplicaci n sin embargo la complejidad es cuadr tica V n debido a que hay que hacer dos recorridos sobre los n elementos de los arreglos de entrada uno para multiplicar cada elemento del arreglo A con cada elemento de B y otro para ir sumando los resultados de cada multiplicaci n tal como se muestra en la siguiente figura figures 1 1 01 x Lo 0 da 1 10 1 1101 times 1 1 10 1 1101 times 1 shifted once 000 0 1101 times 0 shifted twice 1 1 0 1 1101 times 1 shifted thrice 1000 1 1 1 1 binary 143 Figure 1 Multiplicaci n tradicional Existe otro algoritmo para multiplicaci n de dos n meros el cual es m s eficiente que la multi plicaci n tradicional algoritmo de Karatsuba el cual es del tipo de algoritmos Divide y Vencer s Se codific la funci n int karatsuba int numX int numY int result que realiza la multiplicaci n de numX y numY y coloca el resultado en result mediante el m todo de Karatsuba 2 3 1 Historia En oto o de 1960 Kolmogorov un brillante matem tico ruso organiz un seminario acerca de problemas matem ticos de cibern tica en la Universidad Estatal de Mosc
Download Pdf Manuals
Related Search