大数乘法优化方案,更优算法陆续更新.

#include "stdio.h"
#include "stdlib.h"
#include "time.h"

#define SIZE 1000000
#define TWOSIZE SIZE * 2

void initxy (const int xLength,char *x,const int yLength,char *y); //初始化X Y 测试数据
void display (const int xLength,const char *x,const int yLength, const char *y,const char *z); //显示X * Y = Z 的结果
void mul (const int xLength,const char *x,const int yLength,char *y,char *z);//计算X * Y = Z
void scanArray(const int n,char *array,char (*ptr)[SIZE+1]); //扫描 X * Y 全部可能
void OutFile(const int xLength,const char *x,const int yLength, const char *y,const char *z);

int main()
{
 static char x[SIZE] = {0};
 static char y[SIZE] = {0};
 static char z[TWOSIZE] = {0};
 int xLength,yLength;
 clock_t begin, duration;
 time_t t; 
 FILE *fp;

 xLength = SIZE - 100000; //设定x 的位数为1000
 yLength = SIZE - 100000; //设定y 的位数为1000

 //初始化数据X * Y
 initxy(xLength,x,yLength,y);
 //display(xLength,x,yLength,y,z);

 //计算X * Y = Z
 begin = clock();
 time(&t); 
 fp = fopen("时间查看.txt","w+");
    printf("计算MUL()开始时间: %s",ctime(&t)); 
 fprintf(fp,"计算MUL()开始时间: %s\n",ctime(&t)); 
 mul(xLength,x,yLength,y,z);
 duration = clock() - begin;
 printf( "函数mul()计算%d位 * %d位的运行时间大约为：%dms\n", SIZE - xLength,SIZE - yLength,duration*1000/CLOCKS_PER_SEC );
 fprintf(fp, "函数mul()计算%d位 * %d位的运行时间大约为：%dms\n", SIZE - xLength,SIZE - yLength,duration*1000/CLOCKS_PER_SEC );
 time(&t); 
    printf("计算MUL()结束时间: %s",ctime(&t)); 
 fprintf(fp,"计算MUL()结束时间: %s",ctime(&t)); 
 fclose(fp);
 //输出X * Y = Z
 //display(xLength,x,yLength,y,z);
 OutFile(xLength,x,yLength,y,z);
 return 0;
}

void mul (const int xLength,char *x,const int yLength,char *y,char *z) //计算X * Y = Z
{
 static char xItem[10][SIZE + 1] = {0}; //X * (0--9) 的10种可能
 static unsigned long zColTotal[TWOSIZE] = {0}; //Y 列数统计
 int yRowIndex;
 int yColIndex;
 int yHeight; //Y的高度
 int yWidth;  //Y的宽度
 int yFoot;  //Y的脚
 int yMovie; //Y移动的坐标

 int zIndex;
 int zHead;   //Z的头
 int zFoot;   //Z的脚
 int zMovie; //Z向左移动
 
 unsigned long LeftVal,RightVal;
 //扫描 X * Y 全部可能
 scanArray(xLength,x,xItem);
 //Y的宽度
 yWidth = SIZE - (SIZE - xLength);
 //初始化yFoot
 yFoot = yLength;
 //初始化zHead
 zHead = TWOSIZE - 1;
 //初始化zFoot
 zFoot = TWOSIZE - (SIZE - yLength) * 2;
 //初始化Z移动数
 zMovie = 0;
 //遍历Y数组
 for (yRowIndex = SIZE - 1; yRowIndex  >= yLength; yRowIndex--)
 {
  //printf("%d:\t",y[yRowIndex]);
  yHeight = 0;  //Y的高度
  yMovie = zMovie; //Y向右移动
  LeftVal = 0;
  RightVal = 0;
  for (yColIndex = yRowIndex; yColIndex < SIZE ; yColIndex++) //遍历Y数组2维空间内容
  {
   //printf("%d ",y[yColIndex]); //Y的头
   LeftVal += xItem[y[yColIndex]][SIZE - yHeight];  //printf("%d ",xItem[y[yColIndex]][SIZE - yHeight]);
   //printf("%d- ",y[yFoot + yHeight]); //Y的脚
   RightVal += xItem[y[yFoot + yHeight]][yWidth+yMovie]; //printf("%d ",xItem[y[yFoot + yHeight]][yWidth+yMovie]);
   yHeight++; //Y的高度上升
   yMovie--;
  }
  zColTotal[zHead - zMovie] = LeftVal;
  zColTotal[zFoot + zMovie] = RightVal;
  zMovie++; //Z移动
 }

 for (zIndex = TWOSIZE - 1; zIndex >= zFoot; zIndex--)
 {
  //printf("%d\t",zColTotal[zIndex]); if (zColTotal[zIndex] % 10000 == 0)getchar();
  if (zColTotal[zIndex] > 9)
  {
   z[zIndex] = zColTotal[zIndex] % 10;
  // printf("%d \t",zColTotal[zIndex-1]);
   zColTotal[zIndex - 1] = zColTotal[zIndex - 1] + zColTotal[zIndex] / 10;
   //printf("%d\t ",zColTotal[zIndex-1]);
  }
  else
   z[zIndex] = zColTotal[zIndex];
 }
 //getchar();
}

void scanArray(const int Length,char *array,char (*ptr)[SIZE + 1]) //扫描 X * Y 全部可能
{
 int i,j,k;
 int val,cf; //array 取余 进位

 for (i = 1; i < 10; i++) //X * Y [Y 位数的全部可能1---9]
 {
  k = SIZE;
  val = 0;
  for (j = SIZE - 1; j >= Length; j--) //遍历X
  {
   val += i * array[j];
   cf = 0;
   if (val > 9) {
    cf = val / 10;
    val %= 10;
   }
   ptr[i][k] = val; //保持结果
   if (cf > 0)
    val = cf;
   else
    val = 0;
   k--;
  }
  ptr[i][k] = val;
 }
}

void initxy (const int xLength,char *x,const int yLength,char *y) //初始化X Y 测试数据
{
 FILE *fp;
 char ch;
 int i;

 i = xLength;
 fp = fopen("x.txt","r");
 while ((ch = getc(fp)) != EOF)
 {
  x[i] = ch - 0x30;
  i++;
 }
 fclose(fp);

 i = xLength;
 fp = fopen("y.txt","r");
 while ((ch = getc(fp)) != EOF)
 {
  y[i] = ch - 0x30;
  i++;
 }
 fclose(fp);
 /*
 int i;
 char val;

 val = 1;
 for (i = xLength; i < SIZE; i++,val++)
 {
  if (val == 10)
   val = 0;
  x[i] = 9;
 }

 val = 9;
 for (i = yLength; i < SIZE; i++,val--)
 {
  if (val == -1)
   val = 9;
  y[i] = 1;
 }
*/
}

void display (const int xLength,const char *x,const int yLength, const char *y,const char *z) //显示X * Y = Z 的结果
{
 int i;

 for (i = xLength; i < SIZE; i++)
  printf("%d",x[i]);
 printf(" * ");
 
 for (i = yLength; i < SIZE; i++)
  printf("%d",y[i]);
 printf(" = ");

 for (i = 0; i < TWOSIZE && z[i] == 0; i++);
 for(; i < TWOSIZE; i++)
  printf("%d",z[i]);
 printf("\n");
}
void OutFile (const int xLength,const char *x,const int yLength, const char *y,const char *z) //显示X * Y = Z 的结果
{
 FILE *fp;
 int i;

 fp = fopen("万位X.txt","w+");
 for (i = xLength; i < SIZE; i++)
  fprintf(fp,"%d",x[i]);
 fclose(fp);
 
 fp = fopen("万位Y.txt","w+");
 for (i = yLength; i < SIZE; i++)
  fprintf(fp,"%d",y[i]);
 fclose(fp);
 
 fp = fopen("万位Z.txt","w+");
 for (i = 0; i < TWOSIZE && z[i] == 0; i++);
 for(; i < TWOSIZE; i++)
  fprintf(fp,"%d",z[i]);
 fclose(fp);
}

1