objective-c - IOSで2つの非常に大きな数を乗算します

Question

私は2つの大きな整数を掛ける必要があります。それぞれが80桁以上です。

そのような種類のタスクの一般的なアプローチは何ですか？

Answer 1

大きな整数ライブラリを使用する必要があります。ウィキペディアの任意精度演算ページにリストされているオープンソースのものがいくつかあります。

Answer 2

CPUが単一のレジスタに収まる数を乗算できることの素晴らしさを忘れています。レジスターよりも大きい2つの数値を乗算しようとすると、実際に数値を乗算するのがお尻の痛みであることがわかります。

しばらく前にたくさんのクラスを書かなければなりませんでした。これが私の乗算関数のコードです。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 );
}

Answer 3

それはあなたが数字で何をしたいかによります。より多くの算術演算子を使用したいですか、それとも単に2つの数値を乗算してから、それらをファイルに出力したいですか？後者の場合、intまたはchar配列に数字を入れてから、手動で乗算を行う方法を学んだのと同じように機能する乗算関数を実装するのは非常に簡単です。

これをCで実行する場合は、これが最も簡単なソリューションですが、もちろん、メモリ効率はそれほど高くありません。C ++用のBigintegerライブラリを探すことをお勧めします。たとえば、もっとやりたい場合や、ニーズに合わせて自分で実装する場合などです。