С++ Big Integer

Я пытаюсь реализовать класс BigInteger на С++. Но, во-первых, у меня есть базовый вопрос, как можно представить "базовые данные"? Например, самым глупым способом является наличие фиксированного (или динамического) массива char и сохранение каждого отдельного числа целого числа в char. Но, хорошо, это очень глупо, и я здесь для ваших предложений.

Ответ 1

Здесь есть множество предложений для существующих реализаций: С++ обработка очень больших целых чисел

Если вам нужно реализовать свои собственные (например, для домашней работы), тогда вам нужно решить наилучший способ и как "большой" вам нужно справиться. Вы можете использовать массив DWORD и обрабатывать переполнение от одного к другому.

Хотя для некоторых элементов Project Euler я фактически реализовал класс BigNumber, построенный на строке. Он оказался самым простым в реализации для + - */и масштабировался до значительно более длинных чисел, чем я мог бы получить с несколькими unsigned long long s. И производительность была вполне адекватной для решения этих головоломок.

Таким образом, вы сталкиваетесь с компромиссом между простотой внедрения и оптимальной производительностью. Удачи, -)

Ответ 2

Вы можете создать большое целое число точно так, как вы описываете. Фактически, в первый раз я реализовал такой класс, именно так, как я это сделал. Это помогло мне выполнить арифметические операции (+, - и т.д.), Так как в базе (10) я был использован.

Естественное улучшение вашего "массива символов" заключается в том, чтобы сохранить его в базе 10, но использовать 4 бита для цифры, а не всего байта. Таким образом, число 123,456 может быть представлено байтами 12 34 56 вместо строки 123456. (Три байта, а не шесть).

Оттуда вы можете сделать память для номера в базе два. Основные арифметические операции, такие как сложение, работают точно так же в базе 2, как и в базе 10. Таким образом, число 65565 можно сохранить с помощью байтов FF FF. (Например, в векторе unsigned char s.) В некоторых реализациях BigInts для повышения эффективности используются более крупные куски, такие как short или long.

Base-10 big ints может быть полезна, если вы много показываете и/или сериализуете на base-10, и хотите избежать преобразования в base-2.