在IOS中相乘兩個非常大的數字

Question

我必須乘以2個大整數，每一個都是80+數字。

這種類型的任務的一般方法是什麼？

Answer 1

這取決於您想要對數字進行什麼操作。你想使用更多的算術運算符，還是隻是想將兩個數相乘，然後將它們輸出到文件中？如果是後者，將數字放入int或char數組非常簡單，然後實現一個乘法函數，該函數就像您學會了用手來乘法一樣工作。

這是最簡單的解決方案，如果你想在C中做到這一點，但它當然不是非常有效的內存。如果您想要做更多的事情，我建議您爲C++尋找Biginteger庫，或者只是自己實現它以滿足您的需求。

Answer 2

你將不得不使用一個大的整數庫。在維基百科的任意精度算術頁上列出了一些開源軟件頁面here

Answer 3

我們忘記了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); 
}