CODEWITHSUNDEEP
objective-ciosc
TOP KEK
TOP KEK

Reputation: 2651

Multiply 2 very big numbers in IOS

I have to multiply 2 large integer numbers, every one is 80+ digits.

What is the general approach for such kind of tasks?

Upvotes: 1

Views: 1208

Answers (3)

Rafael Baptista
Rafael Baptista

Reputation: 11499

We forget how awesome it is that CPUs can multiply numbers that fit into a single register. Once you try to multiply two numbers that are bigger than a register you realize what a pain in the ass it is to actually multiply numbers.

I had to write a large number class awhile back. Here is the code for my multiply function. KxVector is just an array of 32 bit values with a count, and pretty self explanatory, and not included here. I removed all the other math functions for brevity. All the math operations are easy to implement except multiply and divide.

#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 );
}

Upvotes: 2

Gumeo
Gumeo

Reputation: 901

It depends on what you want to do with the numbers. Do you want to use more arithmetic operators or do you simply want to multiply two numbers and then output them to a file? If it's the latter it's fairly simple to put the digits in an int or char array and then implement a multiplication function which works just like you learned to do multiplication by hands.

This is the simplest solution if you want to do this in C, but of course it's not very memory efficient. I suggest looking for Biginteger libraries for C++, e.g. if you want to do more, or just implement it by yourself to suit your needs.

Upvotes: 1

borrrden
borrrden

Reputation: 33421

You will have to use a large integer library. There are some open source ones listed on Wikipedia's Arbitrary Precision arithmetic page here

Upvotes: 3

Related Questions