Какую структуру данных следует использовать для создания собственного класса BigInteger?

Прочтите книгу Дэвида Р. Хэнсона Интерфейсы и реализации C. В нем есть 2 главы по этому вопросу, посвященные векторной структуре, размеру слова и многим другим вопросам, с которыми вы, вероятно, столкнетесь.

Он написан для C, но большая его часть применима к C++ и/или Java. И если вы используете C++, это будет немного проще, потому что вы можете использовать что-то вроде std::vector для управления распределением массива для вас.

Всегда используйте наименьший тип int, который будет выполнять нужную вам работу (в байтах). Связанный список должен работать хорошо, так как вам не придется беспокоиться о переполнении.

Если вы используете бинарные деревья (чьи листья — целые числа), вы получаете все преимущества связанного списка (неограниченное количество цифр и т. д.) с более простыми алгоритмами «разделяй и властвуй». В этом случае у вас не одна база, а множество, в зависимости от уровня, на котором вы работаете.

Если вы сделаете это, вам нужно использовать BigInteger для переноса. Вы можете считать преимуществом подхода «связанный список целых чисел» то, что перенос всегда может быть представлен как целое число (и это верно для любой базы, а не только для базы 10, поскольку в большинстве ответов предполагается, что вы должны использовать. ..В любой базе перенос всегда однозначный)

С тем же успехом я мог бы сказать: было бы ужасной тратой времени использовать основание 10, когда можно использовать 2^30 или 2^31.

Доступ к элементам связанных списков происходит медленно. Я думаю, что массивы - это путь, с большим количеством проверок привязок и изменением размера массива во время выполнения по мере необходимости.

Пояснение. Обход связанного списка и обход массива — это операции O(n). Но обход связанного списка требует отложенного указателя на каждом шаге. Тот факт, что два алгоритма имеют одинаковую сложность, не означает, что они оба выполняются одинаково. Накладные расходы на выделение и освобождение n узлов в связанном списке также будут намного больше, чем на управление памятью одного массива размером n, даже если размер массива необходимо изменить. несколько раз.

Вау, здесь есть несколько… интересных ответов. Я бы рекомендовал прочитать книгу, а не пытаться разобраться во всех этих противоречивых советах.

Тем не менее, C/C++ также плохо подходит для этой задачи. Большое целое число — это своего рода математика повышенной точности. Большинство ЦП предоставляют инструкции для обработки математических операций с повышенной точностью на сравнимой или такой же скорости (бит на инструкцию), как и при обычной математике. Когда вы добавляете 2 ^ 32 + 2 ^ 32, ответ равен 0 ... но есть также специальный вывод переноса из ALU процессора, который программа может прочитать и использовать.

C++ не может получить доступ к этому флагу, как и в C. Вы должны использовать ассемблер.

Просто чтобы удовлетворить любопытство, вы можете использовать стандартную логическую арифметику для восстановления битов переноса и т. Д. Но вам будет гораздо лучше загрузить существующую библиотеку.

Я бы сказал, массив целых чисел.

Массив действительно подходит естественным образом. Я думаю, допустимо бросать OverflowException, когда у вас не хватает места в памяти. Учитель увидит внимание к деталям.

Умножение примерно удваивает числовые числа, сложение увеличивает их не более чем на 1. Легко создать достаточно большой массив для хранения результата вашей операции.

Перенос — это не более чем однозначное длинное число при умножении (9*9 = 1, перенос 8). Один int будет делать.

std::vector<bool> или std::vector<unsigned int>, вероятно, то, что вам нужно. Вам придется push_back() или resize() на них, так как вам нужно больше места для умножения и т. д. Кроме того, не забудьте отодвинуть назад правильные биты знака, если вы используете два комплимента.

я бы сказал std::vector of char (поскольку он должен содержать только 0-9) (если вы планируете работать в BCD)

Если не BCD, используйте вектор int (вы не дали понять)

Гораздо меньше места над списком ссылок

И все советы говорят: «Используйте вектор, если у вас нет веских причин».

Как правило, используйте std::vector вместо std::list, если только вам не нужно очень часто вставлять элементы в середину последовательности. Векторы, как правило, работают быстрее, поскольку они хранятся непрерывно и, таким образом, выигрывают от лучшей пространственной локализации (основной фактор производительности на современных платформах).

Убедитесь, что вы используете элементы, которые естественны для платформы. Если вы хотите быть независимым от платформы, используйте long. Помните, что если у вас нет каких-либо специальных встроенных функций компилятора, вам потребуется тип как минимум в два раза больше для выполнения умножения.

Я не понимаю, почему вы хотите, чтобы перенос был большим целым числом. Перенос — это один бит для сложения и размер элемента для умножения.

Убедитесь, что вы прочитали Искусство компьютерного программирования Кнута, алгоритмы, относящиеся к арифметике произвольной точности, описаны там в значительной степени.