关于超长整数除法的算法

lionels

这两天忽然想起很久以前没解决的一个问题，放到这里请大伙帮帮忙
关于超长数的四则运算
加，减，乘法我都实现了（在整理代码，完后放上来），

除法我还没想通， 比如一个20位长的整数除以一个18位长的整数

这里牛人多，给我支个招

libin1983

最简单的方法是用 减法+递归 实现除法啊，这样做效率可能低一点了。
算法是：
（求a/b，       f( 10, 7 ) => 1）
Type f( Type a , Type b)
{
    if ( a > b)   
             return( f(a-b, b) + 1) ;
    else  
              return 0;
}
-----------------------------------------
-----------------------------------------
(求a%b，       g(10,7) => 3 )
Type g( Type a, Type b)
{
    if(a>b)
                  return ( g( a - b, b ) );
   else
                return a
}

------------------------------------------
见笑！

win_hate

参考这本书，里面有比较详细的介绍。

应用密码学手册
http://www.china-pub.com/computers/common/info.asp?id=22903

lionels

花时间实现了一个，用的方法比较笨，还有一点点毛病，除法比较慢，各位帮我优化一下

/*
超长整数的四则运算
author: lingp
email: pingerlin@163.com
*/

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

class CBigNumber
{
public:
        CBigNumber();
        CBigNumber(const char*);
        ~CBigNumber();

        void Printf();

        bool operator>= (CBigNumber&);
        bool operator== (CBigNumber&);
        bool operator!= (CBigNumber&);

        CBigNumber& operator= (CBigNumber&);
        CBigNumber& operator+ (CBigNumber&);
        CBigNumber& operator- (CBigNumber&);
        CBigNumber& operator* (CBigNumber&);
        CBigNumber& operator/ (CBigNumber&);

        char* pVal;
        long  len;
};

CBigNumber::CBigNumber()
{
        pVal = NULL;
        len = 0;
}

CBigNumber::CBigNumber(const char* p)
{
        if(p == NULL)
        {
                pVal = NULL;
                len = 0;
        }
        else
        {
                len = strlen(p)+1;
                pVal = new char[len];
                memset(pVal, 0, len);
                strcpy(pVal, p);
        }
}

CBigNumber::~CBigNumber()
{
        delete pVal;
}

void CBigNumber::Printf()
{
        printf("\t%s\n", pVal);
}

bool CBigNumber::operator>= (CBigNumber& big)
{
        if(pVal[0] != '-' && big.pVal[0] == '-')
                return true;

        if(pVal[0] == '-' && big.pVal[0] != '-')
                return false;

        if(pVal[0] != '-' && big.pVal[0] != '-')
        {
                if(len > big.len)
                        return true;
                if(len < big.len)
                        return false;
                if(len == big.len)
                {
                        if(strcmp(pVal, big.pVal) >=0)
                                return true;
                }
                return false;
        }

        if(pVal[0] == '-' && big.pVal[0] == '-')
        {
                if(len > big.len)
                        return false;
                if(len < big.len)
                        return true;
                if(len == big.len)
                {
                        if(strcmp(pVal, big.pVal) <=0)
                                return true;
                }
                return false;
        }

        return false;
}

bool CBigNumber::operator == (CBigNumber& big)
{
        if(strcmp(pVal, big.pVal) == 0)
                return true;
        return false;
}

bool CBigNumber::operator != (CBigNumber& big)
{
        if(strcmp(pVal, big.pVal) == 0)
                return false;
        return true;
}

CBigNumber& CBigNumber::operator = (CBigNumber& big)
{
        if(pVal != NULL)
                delete pVal;

        len = big.len;
        pVal = new char[len];
        memcpy(pVal, big.pVal, len);
        return *this;
}

//实现加法
CBigNumber& CBigNumber::operator+(CBigNumber& big)
{
        long newLen;
        char* newVal;

        if(len >= big.len)
                newLen = len;
        else
                newLen = big.len;

        newLen++; //为最高位进位预留
        newVal = new char[newLen];
        memset(newVal, 0, newLen);               
       
        long pos = newLen-2; //从结束符前一个位置开始
        int carry = 0;

        for(long n=len-2, k=big.len-2; n>=0 && k>=0; n--, k--)
        {
                char t1[1], t2[1];
               
                t1[0] = pVal[n];
                int a = atoi(t1);

                t2[0] =  big.pVal[k];
                int b = atoi(t2);

                int c = a+b+carry;

                int d = c%10;
                carry = c/10;

                char val[1];
                itoa(d, val, 10);

                newVal[pos] = val[0];

                pos --;
        }

        if(len > big.len)
        {
                for(int j=n; j>=0; j--)
                {
                        char t[1];
                        t[0] = pVal[j];
                        int a = atoi(t);
                        int c = a+carry;
                       
                        carry = c/10;
                        int d = c%10;
                        char val[1];
                        itoa(d, val, 10);

                        newVal[pos] = val[0];

                        pos --;
                }
        }
        else
        {
                for(int j=k; j>=0; j--)
                {
                        char t[1];
                        t[0] = big.pVal[j];
                        int b = atoi(t);
                        int c = b+carry;
                       
                        carry = c/10;
                        int d = c%10;
                        char val[1];
                        itoa(d, val, 10);

                        newVal[pos] = val[0];
                        pos --;
                }
        }

        if(carry>0)
        {
                char val[1];
                itoa(carry, val, 10);

                newVal[pos] = val[0];

                pos --;
        }

        if(pos < 0)
                pos = 0;
        else
                pos++;
         
        CBigNumber *bigSum = new CBigNumber(newVal+pos);
        delete newVal;
        return *bigSum;
}

//实现减法
CBigNumber& CBigNumber::operator-(CBigNumber& big)
{
        char *sub, *minu;
        long subLen, minuLen;
        bool reversal = false;

        if(len < big.len)
                reversal = true;
        else if(len == big.len)
        {
                if(strcmp(pVal, big.pVal) < 0)
                        reversal = true;
        }

        if(reversal)
        {
                sub = big.pVal;
                minu = pVal;

                subLen = big.len;
                minuLen = len;
        }
        else
        {
                sub = pVal;
                minu = big.pVal;
               
                subLen = len;
                minuLen = big.len;
        }

        //保存差的字符串
        long difLen = subLen+1; //预留表示负数的符号
        char *diff = new char[difLen];
        memset(diff, 0, difLen);

        //去掉结束符
        subLen--;
        minuLen--;
        difLen--;
       
        int carry = 0;//进位
        long pos = difLen-1;

        for(long i=subLen-1, n=minuLen-1; i>=0 && n>=0; i--, n--)
        {
                char s[1], m[1];
                s[0] = sub;
                m[0] = minu[n];
               
                int a = atoi(s);
                int b = atoi(m);

                int c = a-b + carry;
                if(c < 0)
                {
                        carry = -1;
                        c += 10;
                }
                else
                        carry = 0;

                char d[1];
                itoa(c, d, 10);

                diff[pos] = d[0];
                pos--;
        }

        while(i>=0)
        {
                char s[1];
                s[0] = sub;
                int a = atoi(s);
                int c = a + carry;

                if(c < 0)
                {
                        carry = -1;
                        c += 10;
                }
                else
                        carry = 0;

                char d[1];
                itoa(c, d, 10);

                diff[pos] = d[0];

                pos--;
                i--;
        }

        pos++;

        //将首位的0去掉
        while(diff[pos] != 0)
        {
                if(diff[pos] != '0')
                        break;

                if(diff[pos] == '0')
                        pos++;
        }
        if(diff[pos] == 0)
        {
                pos--;
        }

        if(reversal) //将差置为负数
        {       
                pos--;
                diff[pos] = '-';
        }

        CBigNumber *bigDiff = new CBigNumber(diff+pos);

        delete diff;

        return *bigDiff;
}

//实现乘法
CBigNumber& CBigNumber::operator*(CBigNumber& big)
{
        long mulLen = len-1;                //乘数的长度，去掉结束符
        long facLen = big.len-1;        //被乘数的长度，去掉结束符
        long mulbegin = mulLen - 1;
        long facbegin = facLen - 1;
       
        CBigNumber* bigMul = new CBigNumber("0"); //建立存储乘积的大数

        for(long n=facbegin; n>=0; n--)
        {
                char fac[1];
                fac[0] = big.pVal[n];
                int ifac = atoi(fac);

                long len0 = facbegin - n; //乘积中，末尾0的长度
                long tmpLen = mulLen + len0 + 1 + 1;
                char *tmp = new char[tmpLen];        //存储每一位乘积的字符数组
                memset(tmp, 0, tmpLen);

                int carry = 0; //进位值
               
                //填充乘积末尾的0
                long pos = tmpLen-1-1;
                for(long k=0; k<len0; k++)
                {
                        tmp[pos] = '0';
                        pos--;
                }

                for(long i=mulbegin; i>=0; i--)
                {
                        char mul[1];
                        mul[0] = pVal;
                        int imul = atoi(mul);
                        int acc = ifac * imul;
                        acc += carry;

                        int d = acc % 10;
                        carry = acc / 10;
                       
                        char val[1];
                        itoa(d, val, 10);

                        tmp[pos] = val[0];
                        pos --;
                }

                if(carry > 0)
                {
                        char val[1];
                        itoa(carry, val, 10);
                        tmp[pos] = val[0];
                        pos --;
                }

                if(pos < 0)
                        pos = 0;
                else
                        pos++;
         
                CBigNumber bignum(tmp+pos);
                delete tmp;

                *bigMul = *bigMul + bignum;
        }

        return *bigMul;
}

//实现除法
CBigNumber& CBigNumber::operator/(CBigNumber &big)
{
        bool divflag = true;

        if(len < big.len)
        {
                divflag = false;
        }
        else if(len == big.len)
        {
                if(strcmp(pVal, big.pVal) < 0)
                        divflag = false;
        }

        if(!divflag)
        {       
                CBigNumber *bigDiv = new CBigNumber("0");
                return *bigDiv;
        }

        char *aDiv = pVal;        //被除数       
        char *bDiv = big.pVal; //除数
       
        CBigNumber a(aDiv);
        CBigNumber b(bDiv);
        CBigNumber c("0");
        CBigNumber carry("1");
       
        while(a >= b)
        {
                a = a-b;
                c = c+carry;
        }
       
        CBigNumber *bigDiv = new CBigNumber(c.pVal);
        return *bigDiv;
}


//测试函数
int main(int argc, char* argv[])
{

        CBigNumber a("361100");
        CBigNumber b("40");
       
        CBigNumber c = a/b;

        c.Printf();


        return 0;
}

[ 本帖最后由 lionels 于 2006-3-28 17:44 编辑 ]

linuxcici

可以把除数和被除数都先放在空的内存单元里面. 先把各自高16位拿出来除.用带借位的除法指令.再把余下的再取出来除...这样最快......呵呵....8086的汇编方法.....          win32汇编来写肯定比我快....别骂喔