两个大数相乘、精度很高的小数相乘（小数点后位数没有限制，请写一个高精度算法）

【转】http://www.cppblog.com/dotaqop/articles/148190.html

算法提示：

          输入 string a, string b； 计算string c=a*b; 返回 c;

1，    纪录小数点在a,b中的位置l1,l2， 则需要小数点后移动位置数为l=length(a)+length(b)-l1-l2-2;

2，    去掉a,b中的小数点，（a,b小数点后移，使a,b变为整数）

3，    计算c=a*b; （同整数的大数相乘算法）

4，    输出c,（注意在输出倒数第l个数时，输出一个小数点。若是输出的数少于l个，就补0）

du51(郁郁思扬)的答案：

下面是两个大数的相乘的算法：

原理：

大数A：A1A2A3A4...An 转换为n项多项式PolyA 大数B：B1B2B3B4...Bm 转换为m项多项式PolyB 这样将大数乘法转换为多项式PolyA * PolyB ,然后将多项式计算结果转换为大数表示。

# include<stdio.h>

# include<string.h>

# include<malloc.h>

void

multiply(

char

* a,

char

* b,

char

* c)

{

int

i,j,ca,cb,* s;

ca=

strlen

(a);

cb=

strlen

(b);

s=(

int

*)

malloc

(

sizeof

(

int

)*(ca+cb)); // strlen(a)的数a * strlen(b)的数b一定少于strlen(a)+strlen(b)的数

// 初始化数组

for

(i=0;i<ca+cb;i++)

{

s[i]=0;

} // 各个位上的数分别相乘，并存入相应位的数组成员中（原理类似于小学的两个数相乘的方式）

for

(i=0;i<ca;i++)

for

(j=0;j<cb;j++)

s[i+j+1]+=(a[i]-

'0'

)*(b[j]-

'0'

); //这里为什么不是s[i+j]?而是s[i+j+1] ------为了统一操作,s[0]是用来存放最高位的进位,否则需要分开进行判断

// 处理有进位的数位

for

(i=ca+cb-1;i>=0;i--)

{

if

(s[i]>=10)

{

s[i-1]+=s[i]/10;

s[i]%=10;

}

}

// 清除高位的0

i=0;

while

(s[i]==0)

i++;

for

(j=0;i<ca+cb;i++,j++)

c[j]=s[i]+

'0'

;

c[j]=

'\0'

;

free

(s);

}