大数相乘的算法
㈠ 大数相乘 快速算法
给你一个吧
速度还可以
自己读下代码
/**************************************
算法复杂度为：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;
}
㈩ 带小数的大数相乘的算法
把小数看作大数，随后算出来后把小数点后的小数个数相加到几位，就在哪位上点小数点