IOS에서 두 개의 매우 큰 숫자를 곱하십시오

Question

두 개의 큰 정수를 곱해야합니다. 모두 하나씩 80 + 숫자입니다.

이러한 종류의 작업에 대한 일반적인 접근 방법은 무엇입니까?

Answer 1

숫자에 따라 원하는 결과에 따라 다릅니다. 더 많은 산술 연산자를 사용 하시겠습니까? 아니면 단순히 두 개의 숫자를 곱한 다음 파일로 출력하고 싶습니까? 후자의 경우 숫자를 int 또는 char 배열에 넣은 다음 손으로 곱하기를 배운 것처럼 작동하는 곱하기 함수를 구현하는 것이 매우 간단합니다.

C에서이 작업을 수행하려는 경우이 방법이 가장 간단한 방법이지만 메모리 효율이 좋지는 않습니다. Biginteger 라이브러리 (C++, e.g.)를 찾고 싶다면 더 많은 것을 원하거나 자신의 필요에 맞게 구현하십시오.

Answer 2

큰 정수 라이브러리를 사용해야합니다. Wikipedia의 임의 정밀도 산술 페이지에 나열된 오픈 소스 코드가 있습니다. 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); 
}