大数相乘-整型数(二)

//  $Id: multi.cpp 8 2006-11-03 05:54:04Z JiangMiao $ 
//  JiangMiao's Blog  http://blog.csdn.net/antter
#include  " stdafx.h "
#include  < iostream >
#include  < string >
#include  < list >
using   namespace  std;

#define  SAFE_DELETE(p) if((p)!=NULL){delete p;p=NULL;}
#define  SAFE_DELETE_ARRAY(p) if((p)!=NULL){delete[] p;p=NULL;}
typedef unsigned  long  DWORD;
#define  OK 0
#define  FAIL (DWORD)-1
#define  BLOCK 4  // 块位数
#define  BLOCKS 10000  // 1e+4 即10000进制
#define  BLOCKNUM(size) size/BLOCK+(size%BLOCK>0) // 由size得到最大块数

class  bignumFunc
    {
    
     public :
     ///  转换字符串为
    inline  static  DWORD strToInt( const   string &  inold,DWORD *&  rt,size_t &  length,size_t &  point) 
        {
         string   in ;
        size_t insize = inold.size();
         in .reserve(insize);
         // point=insize;
        point = FAIL;
         for (size_t i = 0 ;i < insize;i ++ )
            {
             if (inold[insize - i - 1 ] == ' . ' ) 
                {
                point = i;
                 continue ;
                }
             in .append( 1 ,inold[insize - i - 1 ]);
            }
        SAFE_DELETE_ARRAY(rt);
        size_t size = in .size();
        size_t num = BLOCKNUM(size);
        rt = new  DWORD[num];
         for (size_t i = 0 ;i < num;i ++ ) 
            {
            DWORD s = 0 ;
            size_t pos = 0 ;
             for (size_t j = 0 ;j < BLOCK;j ++ )
                {
                pos = i * BLOCK + BLOCK - 1 - j;
                 if (pos >= in .size())
                    {
                     continue ;
                    }
                s = s * 10 + in [pos] - ' 0 ' ;

                }
            rt[i] = s;
             if (pos >= in .size())
                 break ;
            }
         if (point == FAIL)
            {
            length = BLOCKNUM(size);
            point = size;
            }
         else
            {
            length = BLOCKNUM(size - 1 );
            }
         return  OK;
        }

    };
class  bignum
    {

    DWORD *  str;
    size_t length;
    size_t point;

     public :
    bignum():str(NULL),length( 0 ),point( 0 )
        {
        }
     ~ bignum()
        {
        }
    bignum( const  bignum &  b)
        {
        init(b.length);
        length = b.length;
        point = b.point;
        memcpy(str,b.str,length);
        }
    size_t size()
        {
         return  length;
        }
    DWORD reset()
        {        
        SAFE_DELETE_ARRAY(str);
        length  =   0 ;
        point  =   0 ;
         return  OK;
        }

     //  分配空间
    DWORD init(size_t length)
        {
        reset();
        str = new  DWORD[length];
        memset(str, 0 ,length * sizeof (DWORD));
         return  OK;
        }

     //  读入string
    DWORD read( const   string &   in )
        {
         return  bignumFunc::strToInt( in ,str,length,point);
        }
    DWORD read( const  DWORD *   in ,size_t length)
        {
         return  OK;
        }

     // 输出到string
     string  toString()
        {
         string  rt;
        rt.reserve(length * sizeof (DWORD));
        size_t i;
         for (i = 0 ;i < length;i ++ )  // 进位
            {
            DWORD num = str[i];
            DWORD o = num % BLOCKS;
            DWORD c = num / BLOCKS;
            str[i + 1 ] += c;
            str[i] = o;
            }
         for (i = length - 1 ;i >= 0 ;i -- )  // 去头零
            {
             if (str[i] != 0 )
                 break ;

            }

         for (;i != FAIL;i -- ) 
            {
             char  buf[ 16 ];
            _ultoa_s(str[i],buf, 16 , 10 );
             for (size_t k = 0 ;k < 4 - strlen(buf);k ++ ) 
                {
                 if (rt.size() == 0 )  // 补足4位
                     break ;
                rt += ' 0 ' ;
                }
            rt += buf;
            }
         return  rt;
        }

    
     /* *
     * 大数相乘,任意位数
      */
     static  bignum *  mul(bignum *  rt,bignum *  sa,bignum *  sb)
        {
        size_t la = sa -> length;
        size_t lb = sb -> length;
        size_t xs = sa -> point + sb -> point; // 小数位数
        size_t lr = la + lb;  // 最大可能位数
        DWORD *  a = sa -> str;
        DWORD *  b = sb -> str;
        rt -> init(lr);
        DWORD *  r = rt -> str;
        size_t ia,ib,ir;
        size_t k = 1 ;
         for (ia = 0 ;ia < la;ia ++ )  // 相乘
            {
             for (ib = 0 ;ib < lb;ib ++ )
                {
                k ++ ;
                ir = ib + ia;
                r[ir] += a[ia] * b[ib];
                 if (r[ir] >= BLOCKS)  // 进位
                    {
                    
                    DWORD num = r[ir];
                    DWORD o = num % BLOCKS;
                    DWORD c = num / BLOCKS;
                    r[ir + 1 ] += c;
                    r[ir] = o;
                    }
                }
            }
         if (r[lr - 1 ] == 0 )
            lr -- ;

        rt -> length = lr;
        rt -> point = xs;
         return  rt;
        }
    };

class  bignumBuilder
    {
     public :
         static  bignum *  build( const   string &  str)
            {
            bignum *  bn = new  bignum();
            bn -> read(str);
             return  bn;
            }
    };

/*

Revision: 6
2006-11-2 5:30
提升性能的改进设想:
1. 使用char* 代替string
2. 多数相乘返回非string,最后由intToStr进行字串输出,可极大地节省预处理和生成的时间

实现以上两点性能提升至少45%,乱猜的 :)
-------------------------------------------

Revision: 6.1
2006-11-3
修改
1. 不再以单个字符为单位
2. 位数不在受到限制

提升性能的改进设想:
使用16进制.对取余和进位采取位操作


性能提升 1300%
-------------------------------------------
*/


///  以下为测试文件
#include  " windows.h "
int  main( int  argc, char **  argv)
    {
     string  rt;
    bignum *  an = new  bignum();
    bignum *  bn = new  bignum();
    bignum *  cn = new  bignum();
    LARGE_INTEGER fre,begin,end;
    QueryPerformanceFrequency( & fre);
    QueryPerformanceCounter( & begin);

//     100000阶乘测试
    cn -> read( " 1 " );
     for ( int  i = 1 ;i <= 10000 ;i ++ )
        {
        bignum *  tmp = an;
        an = cn;
        cn = tmp;
         char  b[ 6 ];
        _itoa_s(i,b, 10 );
        bn -> read(b);
        bignum::mul(cn,an,bn);
        }

    QueryPerformanceCounter( & end);
    cout << " Spend  " << (end.QuadPart - begin.QuadPart) * 1000000 / fre.QuadPart << " ns " << endl;
    cout << cn -> toString().size() << endl;
     return   0 ;
    }


/*  测试10000!的结果
 * C4 2.66MHZ

revision: 6
Spend 16911238ns //17s
35660.

------------------------
revision: 7
10000阶乘
Spend 8441291ns (8.5秒)提升100%
35660

//1000位大浮点数相乘
Spend 3147ns
2001
------------------------
revision: 8
Spend 593560ns (0.6秒)提升1300%
35660
请按任意键继续. . .
  */