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

Question

В качестве необязательного назначения я думаю о том, чтобы написать собственную реализацию класса BigInteger, где я предоставлю свои собственные методы сложения, вычитания, умножения и т. Д.

Это будет произвольно длинное целое число, даже сотни цифр.

Выполняя математические расчеты для этих чисел, цифра за цифрой не сложно, как вы думаете, какой будет лучшая структура данных для представления моего "BigInteger"?

Сначала я подумывал об использовании массива, но потом подумал, что я могу все еще потенциально переполниться (исчерпать слоты массива) после большого добавления или умножения. Было бы хорошо использовать связанный список, так как я могу использовать цифры с O (1) сложностью по времени?

Есть ли какая-то другая структура данных, которая была бы даже лучше, чем связанный список? Должен ли тип, который содержит моя структура данных, быть наименьшим возможным целочисленным типом, который у меня есть?

Кроме того, должен ли я быть осторожным с тем, как хранить свою переменную "carry"? Должен ли он сам относиться к моему типу "BigInteger"?

Answer 1

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

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

Answer 2

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

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

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

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

Answer 3

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

---

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

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

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

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

Answer 7

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

Answer 8

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

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

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

Answer 9

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

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

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

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

Answer 10

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