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

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

Это будет для сколь угодно больших целых чисел, даже для сотен цифр.

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

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

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

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

Ответ 1

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

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

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

Ответ 5

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

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

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

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

Ответ 6

Я бы сказал, массив ints.

Ответ 7

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

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

Значительно меньше служебных данных пространства, которые ссылаются на список ссылок

И все советы говорят "использовать вектор, если у вас нет веской причины не слишком"

Ответ 8

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

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

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

Ответ 9

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

Ответ 10

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

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

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

Убедитесь, что вы прочитали Knuth Art of Computer Programming, алгоритмы, относящиеся к произвольной арифметике точности, описаны там в значительной степени.