Умножение связанных списков в C++

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

Предположим, что существует 2 номера, 1000 и 2000 | 0000 (представляет собой разрыв между различными узлами, из которых состоит число). Если вы умножаете числа, вы получите 200 | 0000 | 0000. Я мог бы сделать функцию, которая сначала умножает 2 узла, а затем делит их на меньшие узлы. После этого он будет умножать следующие узлы, проверяет размер последнего узла и, если есть свободное место, добавьте часть к этому узлу и поместите остатки в следующий. Однако, что, если одно число меньше другого? Затем вы умножаете его на неопределенное число. Имеет ли этот метод какое-либо «будущее»? Или я должен искать другой (я провел некоторое исследование, но пока не нашел ничего полезного)

источник

2012-12-31 user1939088

Вопрос: _С помощью связанного списка для представления больших целых чисел есть будущее_, правильно? Это будет трудно предотвратить, чтобы это закрылось как неконструктивное, но также, это не имеет ничего общего с C++, теперь это делает? – jogojapan

Честно говоря, ваш лучший шанс на будущее - использование надежной, проверенной и проверенной библиотеки BigNum, которой есть несколько. Один из [OpenSSL] (http://www.openssl.org/docs/crypto/bn.html) (я честно забыл название, но я считаю, что это BIGNUM) имеет довольно сильную историю. Есть и другие, некоторые для C++, другие подобные BIGNUM для C/C++. Если это для работы, я бы пошел альтернативным путем. – WhozCraig

Даже если бы вы сделали свою собственную версию BigNum для удовольствия, я бы предложил использовать std :: vector вместо двусвязного списка, поскольку у первого есть намного лучшее распределение памяти, так что это быстрее. –

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

123 x 456 = 
     738 
+  615 
     492 
______________ 
     56088

Реализация этого со связанными списками не должна быть сложной задачей.

источник

2012-12-31 07:42:32

Не использовать метод highschool начинает считать только очень-очень-очень большие числа. (десятки тысяч цифр) http://en.wikipedia.org/wiki/Schönhage-Strassen_algorithm –

Спасибо за ответ. Я думаю, иногда старомодный способ работает лучше всего. – user1939088

Умножение связанных списков в C++

ответ

Смежные вопросы