Pedir ayuda a un experto: algoritmo para la multiplicación de números enteros grandes
Es una multiplicación de alta precisión
Simulando el método de multiplicación vertical aprendido en la escuela primaria
Por ejemplo, 123*456
Primero use una matriz a Guardar 123
a[0]=1; a[1]=2; a[2]=3;
Utilice otra matriz b para guardar 456
b[0]=4; b[1]=5; b[2]=6;
Realice tres multiplicaciones de alta precisión por precisión simple, de la siguiente manera:
Multiplica a por b[0], la matriz c0 obtenida es
c0[0]=a[0]*b[0]=4
c0 [1]=a[1]*b [0]=8
c0[2]=a[2]*b[0]=12
A multiplicado por b[1 ], se obtiene la matriz c1
c1[0]=a[0]*b[1]=5
c1[1]=a[1]*b[1 ]=10
c1[2]=a[2]*b[1]=15
De manera similar, multiplica a por b[2] y se obtiene la matriz c2:
c2[0]= 6
c2[1]=12
c2[2]=18
El siguiente paso es las tres matrices c0 c1 c2, que se desplazan y agregan en secuencia, obtienen la matriz d de la siguiente manera:
c0[0] c0[1] c0[2]
______c1. [0] c1[1] c1[2]
____________c2[0] c2[1] c2[2]
------------- ---------------- ---
_d[0] d[1] d[2] d[3] d[4]
_4 13 28 27 18
Finalmente, el primer paso es ordenar la matriz d
Comience desde el dígito de las unidades, y para cada dígito, si es mayor que 9 , encuentra el módulo y lleva el dígito anterior
for (i=4; igt; 0; i--)
__if (d[i]gt; 9)
__{
____d[i-1] =d[ i]/10;
____d[i]=d[i]10;
__}
Después de ordenar, los elementos de la matriz d son los siguientes:
p>d[0] d[1] d[2] d[3] d[ 4]
5 6 0 8 8
Por lo tanto, al generar en secuencia, obtenemos 56088
123*456=56088
Esto también es cierto al multiplicar números grandes~