Multiplicación de dos enteros largos

Multiplicación de dos enteros largos

Uno de los problemas más frecuentes en teoría de algoritmos es el producto de dos números enteros largos. Cuando se excede el rango de memoria, es necesario subdividir el problema en otros más pequeños de forma que se pueda encontrar una solución.

Para esta cuestión particular, no sólo es importante la cuestión de memoria, también lo es el tiempo necesario para resolverlo. Existen varias técnicas para resolver el problema. Para contextualizar cuál será el algoritmos que vamos a emplear, te recomiendo que leas el artículo: divide y vencerás, multiplicación de enteros.

El algoritmo que dejo a continuación recurre a la técnica de divide y vencerás. Vamos a ver una solución escrita en C.

#include<stdio.h>
#include<string.h>

#define MAXN 1024L

void multiplica(char *,char *,int);

char sol[2*MAXN+5];

int main()
{
   int a,n,n1,n2;
   char f1[MAXN+5];
   char f2[MAXN+5];

/* Los números se guardan al revés, de derecha a izquierda, para que nos quepan las cifras que "nos llevamos". */

   memset(f1,'0',sizeof(f1));
   for(scanf(" %d",&amp;n1),a=n1-1;a>=0;a--) // Coger el primer factor
      scanf(" %c",&amp;f1[a]);
   memset(f2,'0',sizeof(f1));
   for(scanf(" %d",&amp;n2),a=n2-1;a>=0;a--) // Coger el segundo factor
      scanf(" %c",&amp;f2[a]);
   for(a=1;a<n1;a*=2);
   n1=a; // Múltiplo de 2 más cercano a n1.
   for(a=1;a<n2;a*=2);
   n2=a; // Múltiplo de 2 más cercano a n2.
   n=(n1>n2)?n1:n2; // Mayor múltiplo de 2.

   multiplica(f1,f2,n); // Hallar la multiplicación.

   for(a=2*n+2;a>=0 &amp;&amp; sol[a]=='0';a--); // Quitar los ceros a la izquierda
   for(;a>=0;a--) // Imprimir el número.
      printf("%c",sol[a]);
   printf("\n");
   return(0);
 }

void multiplica(char *f1,char *f2,int n)
{
   int a,b;
   char xiyi[2*MAXN+5];
   char xdyd[2*MAXN+5];
   char c1[MAXN+5];
   char c2[MAXN+5];
   char c1c2[2*MAXN+5];

   if(n==1)
   {
      memset(sol,'0',sizeof(sol));
      sol[0]=(f1[0]-'0')*(f2[0]-'0');
      sol[1]=(sol[0]/10)+'0';
      sol[0]=(sol[0]%10)+'0';
      return;
    }

   memset(xiyi,'0',sizeof(xiyi));
   multiplica(f1+n/2,f2+n/2,n/2); // Multiplicación 1
   strcpy((char *)xiyi,(char *)sol);
   memset(xdyd,'0',sizeof(xdyd));
   multiplica(f1,f2,n/2); // Multiplicación 2
   strcpy((char *)xdyd,(char *)sol);

   memset(c1,0,sizeof(c1));
   memset(c2,0,sizeof(c2));
   for(a=0,b=n/2;b<n;a++,b++)
   {
      c1[a]=f1[b]-f1[a]+'0';
      c2[a]=f2[a]-f2[b]+'0';
    }
   memset(c1c2,'0',sizeof(c1c2));
   multiplica(c1,c2,n/2); // Multiplicación 3
   strcpy((char *)c1c2,(char *)sol);

   memset(sol,'0',sizeof(sol));
   for(a=0;a<2*n+2;a++) // Sumar los 5 elementos
   {
      sol[a]-='0';
      sol[a]+=xdyd[a]-'0';
      sol[a+n/2]+=xdyd[a]-'0';
      sol[a+n/2]+=xiyi[a]-'0';
      sol[a+n/2]+=c1c2[a]-'0';
      sol[a+n]+=xiyi[a]-'0';

      sol[a+1]+=sol[a]/10;
      sol[a]=sol[a]%10;
      if(sol[a]<0)
      {
         sol[a]+=10;
         sol[a+1]--;
       }
      sol[a]+='0';
    }
 }

Como siempre, invito a mis lectores a que propongan versiones alternativas para resolver éste problema.

No Comments

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.