highmul_m.cpp

N的阶乘计算-高精度乘法,每个数据单元存4位,每次计算4位而非一位,比一般一位为单元的高精度算法约快4倍

#include "stdafx.h"
#include <stdlib.h>
#include <iostream.h>
#include <string.h>
#include <math.h>

const int MaxRst=250000, 
		  el=4,
		  Cel=(int)pow(10,4);

int main(int argc, char* argv[])
{
	void HighMul(int n, int * rst, int & BitsOfRst, int & BitBgn);
	int mul;
	cout<<"Please input n: ";
	cin>>mul;
	int rst[MaxRst]={1};
	int BitsOfRst=1;
	int BitBgn=0;
	for (int i=2; i<=mul; i++) 
		HighMul(i,rst,BitsOfRst,BitBgn);
	cout<<mul<<"! have "<<(int)log10(rst[(BitsOfRst-1)%MaxRst])+1+(BitsOfRst-1)*el<<" bits."<<endl;
	cout<<mul<<"!= ";

	for (i=BitsOfRst-1; i>=0; i--) {
		if (i!=BitsOfRst-1) 
			for (int j=1; j<=el-((int)log10(rst[i]))-1; j++ ) 
				cout<<'0';
		cout<<rst[i];
	}
	cout<<endl;
	return 0;
}

void HighMul(int n, int * rst, int & BitsOfRst, int & BitBgn ) {
	int tmp=0;
	for (int i=BitBgn; i<BitsOfRst; i++) {
		tmp+=rst[i]*n;
		rst[i]=tmp%Cel;
		tmp/=Cel;
	}
	while (tmp)
		if (BitsOfRst>=MaxRst) 
			exit(1);
		else {
			rst[BitsOfRst++]=tmp%Cel;
			tmp/=Cel;
		}
	while (!rst[BitBgn])
		BitBgn++;
}