c++ - 试图理解简单的大数计算

Question

我正在努力更好地理解“大数字”库的工作原理(例如 GMP)。

我想将自己的函数写入 Add()/Subtract()/Multiply()/Divide()

类传统上定义...

std::vector<unsigned char> _numbers; // all the numbers
bool _neg; // positive or negative number
long _decimalPos; // where the decimal point is located
                  // so 10.5 would be 1
                  //    10.25 would be 2
                  //    10 would be 0 for example

首先我需要对数字进行归一化处理

使用 2 个数字 10(x) + 10.25(y) = 20.25

为了简单起见，我会让它们的长度相同，

对于 x: _numbers = (1,0,0,0) 小数 = 2

对于 y: _numbers = (1,0,2,5) 小数 = 2

然后我可以在循环中将 x 反向添加到 y

...
// where x is 10.00 and y is 10.25
...
unsigned char carryOver = 0;
int totalLen = x._numbers.size();
for (size_t i = totalLen; i > 1 ; --i )
{
    unsigned char sum = x._numbers[i-1] + y._numbers[i-1] + carryOver;
    carryOver = 0;
    if (sum > _base)
    {
     sum -= _base;
     carryOver = 1;
    }
    numbers.insert( number.begin(), sum);
}

// any left over?
if (carryOver > 0)
{
  numbers.insert( number.begin(), 1 );
}

// decimal pos is the same for this number as x and y

...

上面的示例适用于将两个正数相加，但一旦我需要将一个负数与一个正数相加，它很快就会失败。

当涉及到减法时，这会变得更加复杂，而对于乘法和除法则更糟。

有人可以向 Add()/Subtract()/Multiply()/Divide() 推荐一些简单的函数吗

我不是要重写/改进库，我只是想了解它们如何处理数字。

Answer 1

加法和减法非常简单

您需要检查操作数的符号和大小，并在需要时将操作转换为 +/- 或将其转换为 geq。我的典型 C++ 实现是这样的:

//---------------------------------------------------------------------------
arbnum arbnum::operator + (const arbnum &x)
    {
    arbnum c;
    // you can skip this if you do not have NaN or Inf support
    // this just handles cases like adding inf or NaN or zero
    if (  isnan() ) return *this;
    if (x.isnan() ) { c.nan(); return c; }
    if (  iszero()) { c=x; return c; }
    if (x.iszero()) return *this;
    if (  isinf() ) { if (x.isinf()) { if (sig==x.sig) return *this;
                    c.nan(); return c; } return *this; }
    if (x.isinf()) { c.inf(); return c; }
    // this compares the sign bits if both signs are the same it is addition
    if (sig*x.sig>0) { c.add(x,this[0]); c.sig=sig; }
    // if not
    else{
        // compare absolute values (magnitudes)
        if (c.geq(this[0],x)) // |this| >= |x| ... return (this-x)
                {
                c.sub(this[0],x); 
                c.sig=sig;    // use sign of the abs greater operand
                }
        else    {             // else return (x-this)
                c.sub(x,this[0]);
                c.sig=x.sig;
                } 
        }
    return c;
    }
//---------------------------------------------------------------------------
arbnum arbnum::operator - (const arbnum &x)
    {
    arbnum c;
    if (  isnan() ) return *this;
    if (x.isnan() ) { c.nan(); return c; }
    if (  iszero()) { c=x; c.sig=-x.sig; return c; }
    if (x.iszero()) return *this;
    if (  isinf() ) { if (x.isinf()) { if (sig!=x.sig) return *this;
                    c.nan(); return c; } return *this; }
    if (x.isinf()) { c.inf(); c.sig=-x.sig;  return c; }
    if (x.sig*sig<0) { c.add(x,this[0]); c.sig=sig; }
    else{
        if (c.geq(this[0],x))
                {
                c.sub(this[0],x);
                c.sig=sig;
                }
        else    {
                c.sub(x,this[0]);
                c.sig=-x.sig;
                }
        }
    return c;
    }
//---------------------------------------------------------------------------

哪里:

• add 是无符号比较大于或等于
• + 是未签名的 sub
• - 是未签名的 +,-,*,<<,>>

除法有点复杂

见:

• bignum divisions

• approximational bignum divider

  对于部门，你需要已经实现像 +/- 这样的东西，对于一些更高级的方法，你甚至需要这样的东西:绝对比较(无论如何你需要它们用于 BASE=10^n)，sqr，使用的位数通常分开小数部分和整数部分。

  最重要的是乘法，请参阅 Fast bignum square computation，因为它是大多数除法算法的核心。

性能

一些提示见 BigInteger numbers implementation and performance

文本转换

如果您的数字是 ASCII 或 BASE=2^n 数字那么这很容易但是如果您出于性能原因使用 dec 而不是那么您需要具有能够在 hex 和 ojit_code 字符串之间转换的快速函数以便您可以实际加载和打印一些数字到/从你的类(class)。见:

• How do I convert a very long binary number to decimal?
• How to convert a gi-normous integer (in string format) to hex format?