Большой Целочисленный класс в C ++. Как вставить цифры в массив длинных целых без знака? - PullRequest
Новая
       4

Большой Целочисленный класс в C ++. Как вставить цифры в массив длинных целых без знака?

1 голос
/ 29 марта 2011

Я пишу простую большую целочисленную библиотеку для упражнений.Я хотел бы использовать его в простой реализации RSA.Я прочитал все предыдущие темы, но я не нашел ответа на свой вопрос.Я только в начале проекта, и я прочитал, что лучший вариант для представления всех цифр большого целого числа должен представлять их с помощью массива длинных чисел без знака, поэтому это должно быть что-то вроде этого: 

class BigInteger
{
   public:
      BigInteger(const std::string &digits);

   private:
      std::vector <unsigned long> _digits;
};

Проблема в том, что я не знаю, как реализовать конструктор класса.Я думаю, что я должен преобразовать каждый символ строки и сохранить его в массиве таким образом, чтобы минимизировать общую память, используемую массивом, потому что каждый символ имеет длину 1 байт, а длина без знака составляет не менее 4 байтов.Должен ли я нажимать группу из 4 символов за раз, чтобы не тратить впустую всю беззнаковую длинную память?Не могли бы вы дать мне пример или несколько предложений?

Спасибо.

Ответы [ 2 ]

3 голосов
/ 29 марта 2011

Прежде чем думать о том, как нажимать цифры, подумайте о том, как реализовать четыре основных операции.То, что вы хотите сделать в конструкторе из строки, это преобразовать строку во внутреннее представление, что бы это ни было, и для этого вы должны иметь возможность умножить на 10 (предположим, десятичное число) и добавить.

0 голосов
/ 29 марта 2011

Как правильно заметил @James Kanze, преобразования в и из строки не являются главной проблемой дизайна, и вы должны оставить их до конца. Если вы сосредоточитесь на упрощении интерфейса с внешним миром, у вас может получиться дизайн, который легко сериализовать, но работать с ним - кошмар.

Что касается конкретной проблемы, то общий подход к эффективной работе с bignumbers заключается в использовании половины битов в каждой единице хранения (если ваш unsigned long равен 32 битам, используйте только младшие 16 бит). Наличие свободного пространства во всех единицах позволяет вам работать отдельно в каждом элементе, не имея дело с переполнением, а затем normalize результатом, перемещая вынос (старшие битовые числа). Упрощенный подход псевдо-кода для суммирования (игнорирование размеров и, в основном, всего остального будет: 

bignumber& bignumber::operator+=( bignumber const & rhs ) {
   // ensure that there is enough space
   for ( int i = 0; i < size(); ++i ) {
      data[ i ] += rhs.data[ i ];       // might break invariant but won't overflow
   }
   normalize();                         // fix the invariant
}
// Common idiom: implement operator+ in terms of operator+= on the first argument 
//     (copied by value)
bignumber operator+( bignumber lhs, bignumber const & rhs ) {
   lhs += rhs;
   return lhs;
}
...