Autor
|
Tema: Método de multiplicación que desconozco (Leído 2,472 veces)
|
kutcher
Desconectado
Mensajes: 53
|
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 : void longmulti(const char *a, const char *b, char *c) { int i = 0, j = 0, k = 0, n, carry; int la, lb; c[la + lb] = '\0'; for (i = la - 1; i >= 0; i--) { for (j = lb - 1, k = i + j + 1, carry = 0; j >= 0; j--, k--) { n = T(a[i]) * T(b[j]) + T(c[k]) + carry; carry = n / 10; c[k] = (n % 10) + '0'; } c[k] += carry; } if (c[0] == '0') return; }
Saludos
|
|
|
En línea
|
|
|
|
leosansan
Desconectado
Mensajes: 1.314
|
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: 1 2 3 <== indice: j = 2 1 0 x 2 3 <== indice: i = 1 0 ------- 3 6 9 <== i = 3 * j = 3 2 1 2 4 6 <== i = 2 * j = 3 2 1 ---------- 2 7 12 9 ----------- 0 2 8 2 9 <== indice: k = 0 1 2 3 4 De izquierda derecha: "FALTA": carry = 0 ; c[0] = '0' c[4] = 9 % 10 + + acarreo + '0' = '9' ===> carry = acarreo = 9 / 10 = 0 c[3] = 12 % 10 + + acarreo + '0' = '2' ===> carry = acarreo = 12 / 10 = 1 c[2] = 7 % 10 + + acarreo + '0' = '8' ===> carry = acarreo = 8 / 10 = 0 c[1] = 2 % 10 + + acarreo + '0' = '2' ===> carry = acarreo = 2 / 10 = 0 c[0] += acarreo + ( Esto falta ) '0' = '0' c[5] = c[ la + lb ] = '\0' <== Esto esta al principio c = 02829 if ( acarreo == 0 o lo que es lo mismo, si c[0] == '0' ) desplazo todos los caracteres del array "c" una posicion a la izquierda" : memmove ( c , c + 1 , la + lb ) ; ==> c = 2829 Observacion; lo siguiente es para trabajar con enteros n = T(a[i]) * T(b[j]) + T(c[k]) + carry = a[i] - '0' + b[j] - '0' + c[k] - '0' + carry
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
Mensajes: 53
|
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 : 1 2 3 x 2 3 ---------- 1// carry + 2 4 6 9 //(4 = c[k]) (9 = 3 * 3) (6 = 2 * 3) (2 = 2 * 1) -- 5 6 //(5 = c[k]) (6 = 3 * 2) + 3 // (3 = 3 * 1) ---------- 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
Mensajes: 1.314
|
.................................................... 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
|
|
|
|
|
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,044
|
23 Abril 2012, 21:37 pm
por Stakewinner00
|
|
|
Puertos que desconozco
Redes
|
moikano→@
|
4
|
7,608
|
26 Noviembre 2010, 09:30 am
por moikano→@
|
|
|
Problema desconozco el chipset de la tarjeta de red, Aircrack
Dudas Generales
|
alejam14
|
6
|
5,378
|
30 Noviembre 2010, 19:47 pm
por alejam14
|
|
|
Virus USB desconozco como quitarlo
Seguridad
|
ossecreto
|
3
|
3,660
|
8 Junio 2013, 07:12 am
por MicroZeroX
|
|
|
Multiplicacion AES
Criptografía
|
xv0
|
2
|
3,747
|
23 Julio 2013, 22:23 pm
por xv0
|
|