2013-11-10 13 views
0

Я пишу класс для моделирования больших целых чисел. Я сохраняю свои данные как unsigned ints в векторном указателе, называемом данными. Что делает эта функция, она добавляет n к текущему большому целому числу. Кажется, что замедление моей работы связано с использованием длинных значений. Кто-нибудь из вас знает об этом. В настоящее время я должен сделать сумму долгое время, иначе она переполнится.Добавление целых чисел без longs

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

Также просто интересно, есть ли какая-либо польза от использования ссылок на указатели только с помощью самих указателей? Я хотел бы использовать tRef [i] или (* data) [i] для доступа к данным.

+0

Вы уверены, что '% БАЗА 'оптимизируется компилятором? Почему бы просто не использовать 'unsigned long long sum' и сделать тип, отлитый от' unsigned int', или скрыть лишние биты поразрядным и (&)? –

+0

Почему указатель на 'vector'? Это редко бывает подходящим; простой «вектор» должен работать нормально, и вам не придется иметь дело с «новым» и «удалять» его. –

ответ

1

Вместо того, чтобы использовать основание 2^32, используйте основание 2^30. Затем, когда вы добавляете два значения, наибольшая сумма будет 2^31-1, которая вписывается в обычный long (подписанный или неподписанный).

Или еще лучше использовать базу 10^9 (примерно равную 2^30), тогда вам не нужно много усилий печатать большие числа в десятичном формате.


Если вам действительно нужно работать в базе 2^32, вы можете попробовать кладж, как в следующем, при условии unsigned int s не бросать исключения переполнения:

sum = term1 + term2 
carry = 0 
if (sum < term1 || sum < term2) 
    carry = 1 
+0

Бывает ли 'x & 0x7FFFFFFF' и' x & 0x80000000' быстрее, чем 'x> 1000000000? 0: 1' и' x- = k * 1000000000'? Я подозреваю, что это возможно. Как правило, вывод содержимого на экран или файл будет медленным, потому что IO медленный: я бы не стал рассматривать «преобразование в формат ввода-вывода», чтобы быть важным. То, что вы можете сделать, это иметь аргумент шаблона «radix», который обрабатывает добавление/перенос/остаток, поэтому вы можете сделать эту часть модульной, и проверите несколько вариантов выбора, чтобы увидеть, что более эффективно ... – Yakk

Смежные вопросы