大數相乘的演算法

㈠ 大數相乘 快速演算法

給你一個吧
速度還可以
自己讀下代碼
/**************************************
演算法復雜度為：O(longhta*longthb）
longtha為乘數的位數
longhtb為被乘數的位數
***************************************/

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define LEN 1000
void mult(char [],char [],char []);
main()
{
char op1[LEN],op2[LEN],op3[LEN*2-1];
scanf("%s%s",op1,op2);
mult(op1,op2,op3);
printf("%s\n",op3);
getch();
return 0;
}
void reverse(char a[])
{
int longth=strlen(a);
int i;
for(i=0;i<longth/2;i++){
char t;
t=a[i];
a[i]=a[longth-i-1];
a[longth-i-1]=t;
}
}
void mult(char op1[LEN],char op2[LEN],char ans[LEN*2-1])
{
char top1[LEN];
char top2[LEN];
strcpy(top1,op1);
strcpy(top2,op2);
reverse(top1);
reverse(top2);
int k;
int top1s=strlen(top1);
int top2s=strlen(top2);
for(k=0;k<top1s+top2s;k++){
ans[k]='0';
}
int i,j;
int jw,ys;
int longth;
for(j=0;j<top2s;j++){
jw=0;
for(i=0;i<top1s;i++){
ys=((top1[i]-'0')*(top2[j]-'0')+jw+ans[i+j]-'0')%10;
jw=((top1[i]-'0')*(top2[j]-'0')+jw+ans[i+j]-'0')/10;
ans[i+j]=ys+'0';
}
if(jw>0){
ans[i+j]=jw+'0';
}
}
longth=i+j-1;
if(jw>0)
ans[longth++]=jw+'0';
ans[longth]='\0';
reverse(ans);
}

㈡ 關於大數階乘 （相乘） 高手指點

基本不可行
怎麼輸出結果
直接用數組，數組的每個元素表示一位

㈢ 實現大整數的乘法是利用什麼演算法

就是高精度乘
模擬小學時學乘法豎式的方法
比如123*456
首先用一個數組a保存123
a[0]=1;
a[1]=2;
a[2]=3;
再用另外一個數組b保存456
b[0]=4;
b[1]=5;
b[2]=6;
做三次高精乘單精，如下：
a乘以b[0]，得到c0數組為
c0[0]=a[0]*b[0]=4
c0[1]=a[1]*b[0]=8
c0[2]=a[2]*b[0]=12
a乘以b[1]，得到c1數組為
c1[0]=a[0]*b[1]=5
c1[1]=a[1]*b[1]=10
c1[2]=a[2]*b[1]=15
同理，a乘以b[2]，得到c2數組為
c2[0]=6
c2[1]=12
c2[2]=18
下一步，是c0
c1
c2三個數組，依次移位相加，得到數組d，如下：
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
最後一步，是對d數組的整理啦
從個位開始，每一位，如果大於9，則求模，前一位進位
for
(i=4;
i>0;
i--)
__if
(d[i]>9)
__{
____d[i-1]+=d[i]/10;
____d[i]=d[i]%10;
__}
經過整理，數組d各元素如下：
d[0]
d[1]
d[2]
d[3]
d[4]
5
6
0
8
8
因此，依次輸出，得到56088
123*456=56088
大數相乘亦此道理也~

㈣ 一個大整數相乘的問題 c語言

代碼沒問題，只是a,b,c三個數組用之前沒有清零，C語言系統自動分配內存是不會將內存清零
因此c的初始值是有可能有非零數據的

㈤ 大數乘法的幾種演算法分析及比較

1、分治乘法（最簡單的是Karatsuba乘法，一般化以後有Toom-Cook乘法）；
2、快速傅里葉變換FFT(為了避免精度問題，可以改用快速數論變換FNTT)，時間復雜度O(NlgNlglgN)；
3、中國剩餘定理（把每個數分解到一些互素的模上，然後每個同餘方程對應乘起來就行）；
4、剛看到一個比FFT還快的演算法Furer's algorithm，不過好像不太實用。下面的reference[3]給出了

㈥ 大數階乘演算法思想

我的初步想法是：取對數，將乘法轉化為加法……這個應該可以稍微快些吧。

㈦ C語言大整數相乘

我用C語言寫了一個，在VC2005下測試通過。

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

typedef unsigned char CHAR;
typedef unsigned int UINT;

/*十進制形式的a與b，注意低位在前高位在後*/
CHAR a[10000];/*被乘數*/
CHAR c[20000];/*乘積和乘數*/
UINT temp1,temp2;/*用來存放中間結果*/

UINT da, db; /*記錄a和b的位數*/

/*清零*/
void Zero( CHAR* x, UINT n )
{
UINT i;
for ( i = 0; i < n; i ++ )
x[i] = '0';
}

CHAR CharToNum( CHAR c )
{
return c - 0x30;
}

CHAR NumToChar( CHAR c )
{
return c + 0x30;
}

/*這個函數模擬大整數的左移*/
void LShift( CHAR* x, int digits )
{
UINT i;
for ( i = 0; i < digits - 1; i ++ ) {
x[i] = x[i+1];
}
x[digits] = 0;
}

/*這個乘法函數計算大整數a與給定的y的乘積，乘積加入c右半部*/
void OneDigitMultiply( UINT y )
{
UINT i;
UINT cm = 0; /*乘法進位*/
UINT ca = 0; /*加法進位*/
if ( y != 0 ) {
for ( i = 0; i < da; i ++ ) {
/*乘*/
temp1 = ((UINT)a[i]) * y + cm;
cm = temp1 / 10;
temp1 %= 10;

/*加*/
temp2 = ((UINT)c[i+10000]) + temp1 + ca;
if ( temp2 > 9 ) {
ca = 1;
temp2 -= 10;
} else {
ca = 0;
}
c[i+10000] = temp2;
}
c[da+10000] += cm + ca;
}
else {
/*如果被乘數本位是0就直接返回*/
return;
}
}

/*這個函數用來輸出*/
void OutputResult()
{
CHAR* p = c + 20000;
while( *p == 0 ) {
p --;
}
printf("乘積是：\n");
while( *p != 'x' ) {
printf("%d", *p);
p --;
}
}

void main()
{
Zero( a, 10000 );
Zero( c, 10000 );
printf("輸入被乘數：");
scanf("%s",a);
printf("輸入乘數：");
scanf("%s",c);

/*記錄位數*/
da = strlen( (const char*)a );
db = strlen( (const char*)c );
/*反轉以使低位在前*/
strrev( (char*)a );
strrev( (char*)c );

UINT i;

/*a與b存儲的是char字元，減去0x30就能直接當數字使用了*/
for ( i = 0; i < 10000; i ++ ) {
if ( a[i] != '\0' ) {
a[i] = CharToNum( a[i] );
}
}
for ( i = 0; i < 20000; i ++ ) {
if ( c[i] != '\0' ) {
c[i] = CharToNum( c[i] );
}
}

/*這個乘法演算法可以參看二進制乘法器的原理*/
for ( i = 0; i < db; i ++ ) {
OneDigitMultiply( c[0] );
LShift(c, 20000);
}
c[10000-db-1] = 'x'; /*給數字尾部作個標記*/

OutputResult();

getchar();
getchar();
}

第二題：
#include <stdio.h>

void main()
{
float a;
scanf("%f",&a);
if ( a - (int)a == 0 ) {
printf("是整數\n");
}
else {
printf("不是整數\n");
}
getchar();
getchar();
}

㈧ 如何用棧寫大數相乘的演算法

大數乘的最快演算法是快速傅立葉變換法，這有一個，但不是我本人寫的。
#include <iostream>
#include <cmath>
#include <complex>
#include <cstring>
using namespace std;

const double PI = acos(-1);
typedef complex<double> cp;
typedef long long int64;

const int N = 1 << 16;
int64 a[N], b[N], c[N << 1];

void bit_reverse_(cp a[], int n, cp b[])
{
int i, j, k, u, m;
for (u = 1, m = 0; u < n; u <<= 1, ++m)甫長顛短郯的奠痊訂花;
for (i = 0; i < n; ++i)
{
j = i; k = 0;
for (u = 0; u < m; ++u, j >>= 1)
k = (k << 1) | (j & 1);
b[k] = a[i];
}
}

void FFT(cp _x[], int n, bool flag)
{
static cp x[N << 1];
bit_reverse_(_x, n, x);
int i, j, k, kk, p, m;
for (i = 1, m = 0; i < n; i <<= 1, ++m);
double alpha = 2 * PI;
if (flag) alpha = -alpha;
for (i = 0, k = 2; i < m; ++i, k <<= 1)
{
cp wn = cp(cos(alpha / k), sin(alpha / k));
for (j = 0; j < n; j += k)
{
cp w = 1, u, t;
kk = k >> 1;
for (p = 0; p < kk; ++p)
{
t = w * x[j + p + kk];
u = x[j + p];
x[j + p] = u + t;
x[j + p + kk] = u - t;
w *= wn;
}
}
}
memcpy(_x, x, sizeof(cp) * n);
}

㈨ 用分治法怎麼寫大整數乘法的演算法（用c語言寫)

//大數的乘法，以前寫的
#include<iostream>
#include<string>
usingnamespacestd;
voidtoInt(char*s,int*in)
{
	inti;
	strrev(s);
	for(i=0;i<strlen(s);i++)
	{
		in[i]=s[i]-'0';
	}
}
voidrevint(int*in,intn)
{
	inti,temp;
	for(i=0;i<n/2;i++)
	{
		temp=in[i];
		in[i]=in[n-i-1];
		in[n-i-1]=temp;
	}
}
intmain()
{
	charc1[200],c2[200];
	inta1[200]={0};	//大數1
	inta2[200]={0};	//大數2
	intr2[300]={0};	//保存大結果
	intf=0;			//保存進位
	inti,j;
	cin>>c1>>c2;
	if(strcmp(c1,"0")!=0&&strcmp(c2,"0")!=0)
	{
	intlen1=strlen(c1);
	intlen2=strlen(c2);
	intmaxlen=len1+len2;		//結果的最大位數
	toInt(c1,a1);
	toInt(c2,a2);
	for(j=0;j<len2;j++)
	{
		intr1[200]={0};	//保存小結果
		for(i=0;i<=len1;i++)
		{
			r1[i]=a2[j]*a1[i]+f;
			if(r1[i]>9)
			{
				f=r1[i]/10;
				r1[i]%=10;
			}
			else
			{
				f=0;
			}
		}
		for(i=0;i<=len1;i++)
		{
			r2[j+i]+=r1[i];
			if(r2[i+j]>9)
			{
				r2[i+j+1]+=r2[i+j]/10;
				r2[i+j]%=10;
			}
		}
		f=0;
	}
	revint(r2,maxlen);
	if(r2[0]!=0)
		cout<<r2[0];
	for(i=1;i<maxlen;i++)
	cout<<r2[i];
	}
	else
	cout<<"0";
	cout<<endl;
	return0;
}

㈩ 帶小數的大數相乘的演算法

把小數看作大數，隨後算出來後把小數點後的小數個數相加到幾位，就在哪位上點小數點