中文XML论坛--[讨论]用c实现大数类型

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

在java里有一个类BigInteger可以提供了对任意大（位数大）的整数的各种运算操作，现在想自己在c里实现一个有相同功能的类型以供喜欢用c的程序员使用。

我初想了一下：首先应该建立一个数据类型用来保存大数，然后再定义该大数类型上的各种运算。但是因为比如在乘方运算的时候如果算法设计的不好的话感觉一个乘方运算会很慢，所以想跟大家讨论下。
下面是我自己设想的数据结构和一些操作：
－－－－－－－－－－－－－－－－－－－－－－
typedef unsigned char elemType;

typedef struct BigInt{
      elemType num;             //存一位数字
      struct BigInt *next;       //指向下一位数字
}BigInt, *BigInteger;
－－－－－－－－－－－－－－－－－－－－－－
加法：
有四个变量，分别申明如下：
a            //被加数
b           //加数
sum       //和
ar          //进位
初值都为0；
1。从被加数和加数中分别取一位数字（0－9）出来赋值给a和b；
2。让a与b，ar相加，结果存放在sum中；
3。如果sum的值大于a或b中任何一个数（说明没进位），ar置0；否则有进位，ar置1；
4。如果被加数或加数中有一个的位数已经加完，则结束；否则继续1－3。

加法示例：
add("15", "16")
第一趟：a=5, b=6, sum=1, ar=1
第二趟：a=1, b=1, sum=3, ar=0
结果："31"。

－－－－－－－－－－－－－－－－－－－－
其他运算主要都是基于上述加法来实现的，因为各种运算都可以转化成“加”运算。
下面介绍下乘法：
n           //乘数
product  //乘积
初值都为0；
n ＝乘数
for i: 0 to n
    product = add(product, 被乘数);

乘法实例：
mul("15"," 2")
n=2
product=0
第一趟：add(0, "15") product="15"
第二趟：add("15", "15") product="30"
第三趟：add("30", "15") product="45"

－－－－－－－－－－－－－－－－－－－－－－
其他运算实现思路类似乘法。
问题：在乘法里遇到一个问题就是“for i: 0 to n”里n肯定只能是c里提供的整型数据类型，所以这里有限制，还请大家讨论下如何解决？

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

怎么看的人多，回的人少啊？？大家一起交流下嘛。。。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

你的数据结构一个空间存放一位数字，这样设计既浪费空间，时间效率也不高。可以考虑一个空间直接存放IntMAX的思路

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我还考虑过用数组来存，但是输入的数字长度是随机的，所以用数组每次输入一个数据位的时候还要判断是否已经溢出，溢出的话还要重新扩充数组空间，也是不很好。

顺便问下什么是IntMAX?

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

现在加法和减法已经实现了，因为忙所以过久在做乘法和除法。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

下面是我以前搞ACM时写过的大数类（希望对你有用）：
//大数类
#include<iostream>
#include<string>
#include<iomanip>
#include<algorithm>
using namespace std;

#define MAXN 9999
#define DLEN 4

class BigNum{
private:
   int a[300];//DLEN digs for a position
   int len;
public:
   BigNum(){len = 1;memset(a,0,sizeof(a));}
   BigNum(const int b);
   BigNum(const BigNum & T);

   bool     Bigger(const BigNum &) const;
   BigNum & operator=(const BigNum &);
   BigNum & Add(const BigNum &);
   BigNum & Sub(const BigNum &);
   BigNum operator+(const BigNum &) const;
   BigNum operator-(const BigNum &) const;
   BigNum operator*(const BigNum &) const;
   BigNum operator/(const int   &) const;
   void Print();
};
BigNum::BigNum(const int b)
{
   int c,d = b;

   len = 0;
   memset(a,0,sizeof(a));
   while(d > MAXN){
      c = d - d / (MAXN + 1) * (MAXN + 1);
      d = d / (MAXN + 1);
      a[len++] = c;
   }
   a[len++] = d;
}
BigNum::BigNum(const BigNum & T) : len(T.len)
{
   int i;
   memset(a,0,sizeof(a));
   for(i = 0 ; i < len ; i++)
      a[i] = T.a[i];
}
bool  BigNum::Bigger(const BigNum & T) const
{
   int ln;
   if(len > T.len) return true;
   else if(len == T.len){
      ln = len - 1;
      while(a[ln] == T.a[ln] && ln >= 0) ln--;
      if(ln >= 0 && a[ln] > T.a[ln]) return true;
      else return false;
   }
   else return false;
}
BigNum & BigNum::operator=(const BigNum & n)
{
   len = n.len;
   memset(a,0,sizeof(a));
   for(int i = 0 ; i < len ; i++)
      a[i] = n.a[i];
   return *this;
}
BigNum & BigNum::Add(const BigNum & T)
{
   int i,big;

   big = T.len > len ? T.len : len;
   for(i = 0 ; i < big ; i++)
   {
      a[i] = a[i] + T.a[i];
      if(a[i] > MAXN)
      {
         a[i + 1]++;
         a[i] = a[i] - MAXN - 1;
      }
   }
   if(a[big] != 0) len = big + 1;
   else len = big;

return *this;
}
BigNum & BigNum::Sub(const BigNum & T)
{
int i,j,big;

   big = T.len > len ? T.len : len;
   for(i = 0 ; i < big ; i++){
      if(a[i] < T.a[i]){
         j = i + 1;
         while(a[j] == 0) j++;
         a[j--]--;
         while(j > i) a[j--] += MAXN;
         a[i] = a[i] + MAXN + 1 - T.a[i];
      }
      else a[i] -= T.a[i];
   }
   len = big;
   while(a[len - 1] == 0 && len > 1) len--;
   return *this;
}
BigNum BigNum::operator+(const BigNum & n) const
{
   BigNum a = *this;

   a.Add(n);
   return a;
}
BigNum BigNum::operator-(const BigNum & T) const
{
   BigNum b = *this;

   b.Sub(T);
   return b;
}
BigNum BigNum::operator*(const BigNum & T) const
{
   BigNum ret;
   int i,j,up;
   int temp,temp1;

   for(i = 0 ; i < len ; i++){
      up = 0;
      for(j = 0 ; j < T.len ; j++){
         temp = a[i] * T.a[j] + ret.a[i + j] + up;
         if(temp > MAXN){
            temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
            up = temp / (MAXN + 1);
            ret.a[i + j] = temp1;
         }
         else {
            up = 0;
            ret.a[i + j] = temp;
         }
      }
      if(up != 0)
         ret.a[i + j] = up;
   }
   ret.len = i + j;
   while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
   return ret;
}
BigNum BigNum::operator/(const int & b) const
{
   BigNum ret;
   int i,down = 0;

   for(i = len - 1 ; i >= 0 ; i--){
      ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
      down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
   }
   ret.len = len;
   while(ret.a[ret.len - 1] == 0) ret.len--;
   return ret;
}
void BigNum::Print()
{
   int i;

   cout << a[len - 1];
   for(i = len - 2 ; i >= 0 ; i--){
      cout.width(DLEN);
      cout.fill('0');
      cout << a[i];
   }
   cout << endl;
}

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

你的这种做法效率太低,很不合适

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用yinbodotcc在2006-3-19 11:46:00的发言：
你的这种做法效率太低,很不合适

能说出你的想法吗？？
请不要说这种让人莫名的话。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我自己的＋－* / 函数全编好啦，工作的很完美。下一步想编开方函数。

不过我不在乎执行的速度，只是玩玩。


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	117.188ms