elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Método de multiplicación que desconozco 		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Método de multiplicación que desconozco  (Leído 2,504 veces)
kutcher

Desconectado Desconectado

Mensajes: 53


Ver Perfil
Método de multiplicación que desconozco
« en: 15 Octubre 2014, 01:41 am »
Buenas noches, estoy estudiando un algoritmo que realiza una multiplicación de dos enteros almacenados en respectivos arrays, el problema es que no consigo entender el método utilizado en tal caso, ya que existen varios :

Código
  1. void longmulti(const char *a, const char *b, char *c)
  2. {
  3.     int i = 0, j = 0, k = 0, n, carry;
  4.     int la, lb;
  5.  
  6.     la = strlen(a);
  7.     lb = strlen(b);
  8.  
  9.     memset(c, '0', la + lb);
  10.     c[la + lb] = '\0';
  11.  
  12.     for (i = la - 1; i >= 0; i--)
  13.     {
  14.         for (j = lb - 1, k = i + j + 1, carry = 0; j >= 0; j--, k--)
  15.         {
  16.             n = T(a[i]) * T(b[j]) + T(c[k]) + carry;
  17.             carry = n / 10;
  18.             c[k] = (n % 10) + '0';
  19.         }
  20.         c[k] += carry;
  21.     }
  22.     if (c[0] == '0')
  23.        memmove(c, c + 1, la + lb);
  24.  
  25.     return;
  26. }

Saludos
En línea
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Método de multiplicación que desconozco
« Respuesta #1 en: 15 Octubre 2014, 07:21 am »
Cita de: kutcher en 15 Octubre 2014, 01:41 am
Buenas noches, estoy estudiando un algoritmo que realiza una multiplicación de dos enteros almacenados en respectivos arrays, el problema es que no consigo entender el método utilizado en tal caso, ya que existen varios :
.....................................
Saludos

Este algoritmo es la clásica multiplicación:

Código
  1.  
  2.  
  3.     1 2 3      <== indice: j = 2 1 0
  4.     x 2 3      <== indice: i =   1 0
  5.    -------
  6.     3 6 9      <== i = 3 * j = 3 2 1
  7.   2 4 6    <== i = 2 * j = 3 2 1
  8.   ----------
  9.   2 7 12 9
  10.  -----------
  11. 0 2 8  2 9   <== indice: k = 0 1 2 3 4
  12.  
  13. De izquierda derecha:
  14.  
  15. "FALTA": carry = 0 ;
  16.  
  17. c[0] =  '0'
  18. c[4] =  9 % 10 +  + acarreo + '0' = '9' ===>  carry = acarreo =  9 / 10 = 0
  19. c[3] = 12 % 10 +  + acarreo + '0' = '2' ===>  carry = acarreo = 12 / 10 = 1
  20. c[2] =  7 % 10 +  + acarreo + '0' = '8' ===>  carry = acarreo =  8 / 10 = 0
  21. c[1] =  2 % 10 +  + acarreo + '0' = '2' ===>  carry = acarreo =  2 / 10 = 0
  22.  
  23. c[0] +=   acarreo + (  Esto falta  ) '0' = '0'
  24.  
  25. c[5] = c[ la + lb ] = '\0' <==  Esto esta al principio
  26.  
  27. c  = 02829
  28.  
  29. if ( acarreo == 0 o lo que es lo mismo, si c[0] == '0' )
  30.  
  31.   desplazo todos los caracteres del array "c" una posicion a la izquierda" :
  32.  
  33.    memmove ( c , c + 1 , la + lb ) ; ==> c = 2829
  34.  
  35.  Observacion; lo siguiente es para trabajar con enteros
  36.  
  37. n = T(a[i]) * T(b[j]) + T(c[k]) + carry = a[i] - '0' + b[j] - '0' + c[k] - '0'  + carry
  38.  

Más o menos así es el esquema que sigue un código simple de multiplicación.  ;)

¡¡¡¡ Saluditos! ..... !!!!



EDITADO con la observación de kutcher, no sé en que estaría pensando.  ;)
« Última modificación: 15 Octubre 2014, 21:15 pm por leosansan » En línea
kutcher

Desconectado Desconectado

Mensajes: 53


Ver Perfil
Re: Método de multiplicación que desconozco
« Respuesta #2 en: 15 Octubre 2014, 18:24 pm »
Cita de: leosansan en 15 Octubre 2014, 07:21 am
Este algoritmo es la clásica multiplicación:

Efectivamente al parecer se trata del método mencionado, pero en el esquema que has hecho, el resultado que obtienes creo es incorrecto debería ser 2829 en ves de 3936 todo esto debido a la alineación del segundo producto parcial a la derecha, he hecho un seguimiento minucioso al algoritmo y trabaja mas o menos asi :

Código
  1.   1 2 3
  2.   x 
  3.     2 3
  4. ----------
  5.    1// carry
  6.   +
  7.  2 4 6 9   //(4 = c[k]) (9 = 3 * 3) (6 = 2 * 3) (2 = 2 * 1)
  8.    --
  9.    5 6     //(5 = c[k]) (6 = 3 * 2) 
  10.   +
  11.    3       // (3 = 3 * 1)
  12. ----------
  13.  2 8 2 9

Saludos leosansan un gusto volverte a ver escribir
« Última modificación: 15 Octubre 2014, 18:30 pm por kutcher » En línea
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Método de multiplicación que desconozco
« Respuesta #3 en: 15 Octubre 2014, 21:14 pm »
Cita de: kutcher en 15 Octubre 2014, 18:24 pm
....................................................
Saludos leosansan un gusto volverte a ver escribir

Igualmente amigo kutcher.

Me permito hacerte una pequeña observación respecto a ese código para multiplicar y es que debido a los dos for recurrentes si los dos números son cada uno de 1000 cifras habría que realizar un millón (¡¡¡1.000.000¡¡¡ ni más ni menos) de operaciones "/" y "%".

Si lo analizas verás que con un array temporal ese número se reduce a la suma de cifras, es decir ¡¡¡¡2.000 tan sólo ¡¡¡¡¡.

No cuelgo código por razones que entenderás, pero si estas interesado me envías un mp.

Un fuerte saludo de León.
En línea
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Imposible desempackar armadillo... lleva algo mas que desconozco por completo « 1 2 3 »
Ingeniería Inversa 		Alpiskris 21 16,120 Último mensaje 23 Abril 2012, 21:37 pm
por Stakewinner00
Puertos que desconozco
Redes 		moikano→@ 4 7,642 Último mensaje 26 Noviembre 2010, 09:30 am
por moikano→@
Problema desconozco el chipset de la tarjeta de red, Aircrack
Dudas Generales 		alejam14 6 5,425 Último mensaje 30 Noviembre 2010, 19:47 pm
por alejam14
Virus USB desconozco como quitarlo
Seguridad 		ossecreto 3 3,698 Último mensaje 8 Junio 2013, 07:12 am
por MicroZeroX
Multiplicacion AES
Criptografía 		xv0 2 3,763 Último mensaje 23 Julio 2013, 22:23 pm
por xv0
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines