Какой самый быстрый алгоритм деления сумасшедших больших чисел?

Мне нужно разделить числа, представленные в виде цифр, в байтовых массивах с нестандартным количеством байтов. Это может быть 5 байтов или 1 ГБ или более. Деление должно выполняться с числами, представленными в виде байтовых массивов, без каких-либо преобразований в числа.

 Dukeling26 июн. 2013 г., 16:00
Что-то вродеДжава'с BigInteger?
 Tyler Durden26 июн. 2013 г., 16:00
Уменьшение Барретта вычисляет модуль, а не частное.
 Kosmos26 июн. 2013 г., 16:12
Может ли Java 's BigInteger обрабатывает гигабайты байтов?
 Tyler Durden26 июн. 2013 г., 16:28
 Hurkyl05 окт. 2015 г., 09:50
@Tyler: ... и он получает остаток, сначала вычисляя частное, а затем вычитая из соответствующего кратного делителя.
 Tyler Durden26 июн. 2013 г., 16:17
ОП не говорит, что он использует Java. Джава'Реализация математики произвольной точности относительно неэффективна, но может обрабатывать миллиарды цифр, если у вас достаточно памяти. Это займет много времени, чтобы вычислить частное.
 Kosmos26 июн. 2013 г., 16:32
Википедия неt ответить на вопросы, какой самый быстрый. Мне не нужны подразделения, которые должны работать в течение нескольких дней.
 tmyklebu26 июн. 2013 г., 17:34
BigInteger это довольно плохо, если вы хотите, чтобы ваши операции были быстрыми. Умножение и деление делаются по учебнику в каноническом исполнении.
 Regenschein26 июн. 2013 г., 14:23
 Tyler Durden26 июн. 2013 г., 16:18
Для подобных вопросов вы должны использовать Википедию и заходить сюда ПОСЛЕ того, как вы прочитали Википедию и попробовали что-то.
 Dukeling26 июн. 2013 г., 16:24
@Kosmos Он должен поддерживать такое большое число, которое уместится в памяти. Но я ссылался на это скорее как на отправную точку. Джава'API-код с открытым исходным кодом, так что вы можете посмотреть, как они это сделали.

Ответы на вопрос(2)

Решение Вопроса

чем метод школьных учебников для действительно больших целых чисел.

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

Вот это GMPалгоритмы деления " документация. Описания алгоритма немного лаконичны, но они, по крайней мере, дают вам кое-что для Google, когда вы хотите узнать больше.

Брент и ЦиммерманнСовременная компьютерная арифметика хорошая книга по теории и реализации арифметики больших чисел. Наверное, стоит прочитать, если вы хотите знать, чтоизвестно.

 tmyklebu26 июн. 2013 г., 19:43
@TylerDurden: Ну, он спросил о "сумасшедшие большие числа. "  Карацуба нетне плохо само по себе, так как вы нене сталкиваюсь с проблемами власти двух. Это начинает становиться большой работой, когда вы начинаете хотеть реализовывать Toom-Cook и различные методы, основанные на FFT, а затем выяснять точки пересечения. Вот почему вы используете GMP для этого :)
 tmyklebu26 июн. 2013 г., 19:45
@TylerDurden: И разделение «разделяй и властвуй» нене так уж плохо, если у вас есть быстрый черный ящик умножения. Возьмите верхнюю половину числителя и знаменателя, рекурсивно разделите, а затем выполните небольшую очистку. Опять же, настройка и нахождение точки пересечения между учебником и «разделяй и властвуй» - трудоемкая работа.
 Tyler Durden26 июн. 2013 г., 18:37
Да, но ... как я уже сказал, эти алгоритмы намного сложнее, чем Алгоритм D. Основная причина делить и завоевывать состоит в том, что вы можете использовать алгоритм Карацубы, и позвольте мне рассказать вам о написании всего этого плюс реализация Карацубы. будет много работы, и я имею в виду работу LOTTA LOTTA. Я неЯ не знаю, насколько хорош программист ОП, но даже очень хороший программист мог бы потратить МЕСЯЦЫ на написание правильной реализации, используя разделяй и властвуй.

который аналогичен длинному делению в начальной школеАлгоритм D описано в Кнуте 4.3.1. Кнут подробно обсуждает разделение в этом разделе своей книги. В результате этого существуют более быстрые методы, чем алгоритм D, но они не намного быстрее и намного сложнее, чем алгоритм D.

Если вы решили получить максимально быстрый алгоритм, вы можете прибегнуть к так называемому алгоритму SRT.

Все это и многое другое описано в ВикипедииАлгоритм деления.

 Python Cheese13 апр. 2017 г., 23:51
Из алгоритмов, перечисленных в ссылке на Википедию, вынаверное найдудлинное деление быть самым полезным. Будьте осторожны с обозначениями, хотя.D (0) указывает на наименее значимое значение числа, в то время как сдвиг влево указывает на то, что числа хранятся с прямым порядком байтов (что означает, что ЛСД должен быть вD (N-1)).

Ваш ответ на вопрос