0

I am writing a class to model big integers. I am storing my data as unsigned ints in a vector pointer called data. What this function does is it adds n to the current big integer. What seems to be slowing down my performance is having to use long long values. Do any of you know a way around this. I currently have to make sum a long long or else it will overflow.

void Integer::u_add(const Integer & n)
{
    std::vector<unsigned int> & tRef = *data;
    std::vector<unsigned int> & nRef = *n.data;
    const int thisSize = tRef.size();
    const int nSize = nRef.size();
    int carry = 0;
    for(int i = 0; i < nSize || carry; ++i)
    {
        bool readThis = i < thisSize;
        long long sum = (readThis ? (long long)tRef[i] + carry : (long long)carry) + (i < nSize ? nRef[i] : 0);
        if(readThis)
            tRef[i] = sum % BASE; //Base is 2^32
        else
            tRef.push_back(sum % BASE);
        carry = (sum >= BASE ? 1 : 0);
    }
}

Also just wondering if there is any benefit to using references to the pointers over just using the pointers themselves? I mean should I use tRef[i] or (*data)[i] to access the data.

4

1 回答 1

1

不要使用基数 2^32，而是使用基数 2^30。然后，当您添加两个值时，最大和将为 2^31-1，它适合普通long（有符号或无符号）。

或者更好的是，使用基数 10^9（大约等于 2^30），那么您就不需要花费很多精力来打印十进制格式的大数。

如果你真的需要以 2^32 为基数工作，你可以尝试像下面这样的 kludge，前提unsigned int是 s 不要抛出溢出异常：

sum = term1 + term2
carry = 0
if (sum < term1 || sum < term2)
    carry = 1
于 2013-11-10T23:32:15.550 回答