2

我正在开发一个在 C++ 中实现多精度算术的项目。我在第一个障碍中倒下了。我正在尝试将 c 字符串转换为整数的二进制表示，该整数可能包含比 int 可以容纳的更多位（理论上这可能是任意数量的位）。我本质上想创建一个长数组，它将保存字符串中包含的数字的二进制表示，索引 0 是数字的最不重要的“肢体”。我假设这个数字以十为底。

我已经研究过使用 GMP 中的代码，但它对于我的需求来说是不必要的复杂，并且有大量平台相关的代码。

任何帮助都会很棒！如果您需要更多详细信息，请告诉我。

4

2 回答 2

3

就像@SteveJessop 说的

class Number {
public:
    Number();
    void FromString( const char * );
    void operator *= ( int );
    void operator += ( int );
    void operator = ( int );
}

Number::FromString( const char * string )
{
    *this = 0;
    while( *string != '\0' ) {
        *this *= 10;
        *this += *string - '0';
        string++;
    }
}
于 2012-12-10T14:30:42.013 回答
2

您要做的第一件事是拥有一个工作的测试引擎。这是一个脑残、易于理解、任意精度的算术引擎。

这个引擎的目的有几个。首先，它将字符串转换为任意精度的整数非常容易。其次，它是一种测试您后来改进的引擎的方法。即使它真的很慢，您也会更加确信它是正确的（并且拥有两个独立的实现意味着一个极端案例错误可能会被另一个捕获，即使您对任何一个都没有信心）。

假设short至少为 16 位且char至少为 8 位（int_8如果您的编译器支持，请使用实际的样式类型）

short Add(unsigned char left, unsigned char right, unsigned char extra=0) { return unsigned short(left)+unsigned short(right)+unsigned short(extra); }
unsigned short Multiply(unsigned char left, unsigned char right) { return unsigned short(left)*unsigned short(right); }
std::pair<unsigned char,unsigned char> CarryCalc(unsigned short input) {
  std::pair<unsigned char,unsigned char> retval;
  retval.first = input & (1<<8-1);
  retval.second = input>>8;
  return retval;
}
struct BigNum {
  std::vector<char> base256;
  BigNum& operator+=( BigNum const& right ) {
    if (right.base256.size() > base256.size())
      base256.resize(right.base256.size());
    auto lhs = base256.begin();
    auto rhs = right.base256.begin();
    char carry = 0;
    for(; rhs != right.base256.end(); ++rhs, ++lhs) {
      auto result = CarryCalc( Add( *lhs, *rhs, carry ) );
      *lhs = result.first;
      carry = result.second;
    }
    while( carry && lhs != base256.end() ) {
      auto result = CarryCalc( Add( *lhs, 0, carry ) );
      *lhs = result.first;
      carry = result.second;
    }
    if (carry)
      base256.push_back(carry);
    return *this;
  }
  BigNum& scaleByChar( unsigned char right ) {
    char carry = 0;
    for(auto lhs = base256.begin(); lhs != base256.end(); ++lhs) {
      unsigned short product = Multiply( *lhs, right );
      product += carry;
      auto result = CarryCalc( product );
      *lhs = result.first;
      carry = result.second;
    }
    if (carry)
      base256.push_back(carry);        
    return *this;
  }
  BigNum& shiftRightBy8BitsTimes( unsigned int x ) {
    if (x > base256.size()) {
      base256.clear();
      return *this;
    }
    base256.erase( base256.begin(), base256.begin()+x) )
    return *this;
  }
  // very slow, O(x * n) -- should be O(n) at worst
  BigNum& shiftLeftBy8BitsTimes( unsigned int x ) {
    while( x != 0 ) {
      base256.insert( base256.begin(), 0 );
      --x;
    }
    return *this;
  }
  // very slow, like O(n^3) or worse (should be O(n^2) at worst, fix shiftLeft)
  BigNum& operator*=( BigNum const& right ) {
    unsigned int digit = 0;
    BigNum retval;
    while (digit < right.base256.size()) {
      BigNum tmp = *this;
      tmp.shiftLeftBy8BitsTimes( digit );
      tmp.scaleByChar( right.base256[digit] );
      retval += tmp;
      ++digit;
    }
    *this = retval;
    return *this;
  }
};

这是一种快速而肮脏的任意精度整数类型（甚至还没有编译），性能很差。测试类似上面的东西，说服自己它是可靠的，然后从那里建立起来。

您的大部分代码都可以将有问题的实际 BigNum 类作为模板参数，因此您可以使用两种不同的实现来执行相同的算法，并比较结果以进行测试。

哦，还有一条建议——编写一个模板类，通过 CRTP “改进”一个简单的任意精度库。目标是只需要编写*=, +=, unary -, and maybe /=and some shift_helperandcompare_helper函数，并让模板自动为您编写其余方法。通过将样板放在一个位置，可以更轻松地维护多个版本的BigNum类：并且拥有多个版本对于测试目的非常重要。

于 2012-12-10T15:03:43.437 回答