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