1

我必须乘以 2 个大整数，每个都是 80+ 位。

此类任务的一般方法是什么？

4

3 回答 3

3

您将不得不使用一个大型整数库。维基百科的任意精度算术页面上列出了一些开源算法

于 2012-06-21T10:50:32.250 回答
2

我们忘记了 CPU 可以将适合单个寄存器的数字相乘是多么了不起。一旦您尝试将两个大于寄存器的数字相乘，您就会意识到实际将数字相乘是多么痛苦。

不久前我不得不写一个大数类。这是我的乘法函数的代码。KxVector 只是一个带有计数的 32 位值的数组，并且非常不言自明，此处不包括在内。为简洁起见，我删除了所有其他数学函数。除了乘法和除法之外，所有的数学运算都很容易实现。

#define BIGNUM_NEGATIVE 0x80000000

class BigNum
{              
public:
   void mult( const BigNum& b );
   KxVector<u32> mData;
   s32           mFlags;
};


void BigNum::mult( const BigNum& b )
{
   // special handling for multiply by zero
   if ( b.isZero() )
   {
      mData.clear();
      mFlags = 0;
      return;
   }

   // apply sign
   mFlags ^= b.mFlags & BIGNUM_NEGATIVE;

   // multiply two numbers using a naive multiplication algorithm.
   // this would be faster with karatsuba or FFT based multiplication
   const BigNum* ppa;
   const BigNum* ppb;

   if ( mData.size() >= b.mData.size() )
   {
      ppa = this;
      ppb = &b;
   } else {
      ppa = &b;
      ppb = this;
   }
   assert( ppa->mData.size() >= ppb->mData.size() );

   u32 aSize = ppa->mData.size();
   u32 bSize = ppb->mData.size();

   BigNum tmp;
   for ( u32 i = 0; i < aSize + bSize; i++ )
      tmp.mData.insert( 0 );

   const u32* pb = ppb->mData.data();
   u32 carry = 0;
   for ( u32 i = 0; i < bSize; i++ )
   {
      u64 mult = *(pb++);
      if ( mult )
      {
         carry = 0;
         const u32* pa = ppa->mData.data();
         u32* pd = tmp.mData.data() + i;
         for ( u32 j = 0; j < aSize; j++ )
         {
            u64 prod = ( mult * *(pa++)) + *pd + carry;
            *(pd++) = u32(prod);
            carry = u32( prod >> 32 );
         }
         *pd = u32(carry);
      }
   }

   // remove leading zeroes
   while ( tmp.mData.size() && !tmp.mData.last() ) tmp.mData.pop();

   mData.swap( tmp.mData );
}
于 2012-06-21T17:16:37.270 回答
1

这取决于你想对这些数字做什么。您想使用更多的算术运算符还是只想将两个数字相乘然后将它们输出到文件中？如果是后者，将数字放入 int 或 char 数组中然后实现乘法函数就相当简单了，它的工作原理就像你学会了用手进行乘法一样。

如果您想在 C 中执行此操作，这是最简单的解决方案，但当然它的内存效率不是很高。我建议寻找 C++ 的 Biginteger 库，例如，如果你想做更多，或者只是自己实现它以满足你的需要。

于 2012-06-21T13:12:58.943 回答