大数相乘算法

//////////////////////////////////////////////////////////////// 
//作者：涂远东 
//时间：2010 01 23 
//高精度的乘法,乘数的位数没有限制，小数点后面的位数也没有限制 
//输入参数：乘数 str1，str2 
//输出参数：str = str1*str2 
//返回值类型：string& 
//////////////////////////////////////////////////////////////// 
string& large_mult(string str1,string str2,string& str/*输出参数*/)  
{  
    str = "0";  
 int pos1 = str1.find('.');  
 int pos2 = str2.find('.');  
 //小数点在字符串的位置 
 int offset = str1.length() + str2.length()  
        - ((pos1 >0)? (pos1+1):0 )  
        - ((pos2 >0) ? (pos2+1):0 );  
 //去除字符串str1和str2中的小数点 
 if(pos1 != -1)  
        str1.erase(pos1,1);  
 if(pos2 != -1)  
        str2.erase(pos2,1);  
    unsigned char single = 0;   //个位数 
    unsigned char tens = 0; //十位数 
    unsigned char ret = 0;  //乘积 
 //计算规则，假设str1和str2字符串长度分别为len1和len2 
 //乘积str的字符串长度len应该不大于len1+len2 
 //乘数str1[len1-i]和str2[len2-j]相乘只会乘积中str中str[len-i-j]和str[len-i-j-1]的值 
 int i = 0;  
 for(string::iterator iter = str1.end()-1; iter >= str1.begin(); iter--,i++)  
    {  
 int index = 0;  
 int offset = 0;  
 int j=0;  
 for(string::iterator iter2=str2.end()-1; iter2 >= str2.begin(); iter2--,j++)  
        {  
            offset = i+j +1;  
 //字符‘0’的ASCII编码值为48 
            ret = (*iter2 -'0') * (*iter -'0'); //乘积 
            single = ret % 10;      //乘积的个位数 
            tens = ret / 10;        //乘积的十位数 
 //位数不够左边补0 
            index = str.length() - offset;  
 while(index < 1)  
            {  
                str.insert(str.begin(), '0');  
                index = str.length() - offset;  
            }  
            assert(str.length() > offset);  
            index = str.length() - offset;  
            add(str,index,single);      //个位数相加 
            add(str,index-1,tens);      //十位数相加 
        }  
    }  
 if(str[0] == '0')  
    {  
        str.erase(str.begin());  
    }  
 if(offset < str.length())  
    {  
        string::iterator itr = str.end()-offset;  
        str.insert(itr,'.');  
    }  
 return str;  
}  
//////////////////////////////////////////////////////////////// 
//在大数str的index位处加于num 即 str+= num 
//////////////////////////////////////////////////////////////// 
inline bool add(string& str, int index, int num)  
{     
    assert(index >=0);  
 int  p = str[index] + num - '0';      
    str[index] = p%10 + '0';  
 if(p >9)  
        add(str,index-1,1);  
 return true;  
}  

#include "stdafx.h" 
#include <iostream> 
#include <string> 
#include <cassert> 
using namespace std;  
string& large_mult(string str1,string str2,string& str/*输出参数*/);  
bool add(string& str, int index, int num);  
int main(int argc, char* argv[])  
{  
    printf("Please input two large number!/n");  
    string str1;  
    string str2;  
    std::cout<<"Please input the first large number:/nstr1=";  
    std::cin>> str1;  
    std::cout<<"Please input the second large number::/nstr2=";  
    std::cin>>str2;  
    string str; //str = str1 * str2 
    large_mult(str1,str2,str);  
    std::cout<<"str=str1*str2/nstr=";  
    std::cout<<str<<std::endl;  
 return 0;  
}