Мне нужно разделить числа, представленные в виде цифр в массивах байтов, с нестандартным количеством байтов. Это может быть 5 байт или 1 ГБ или больше. Деление должно выполняться с числами, представленными в виде байтовых массивов, без каких-либо преобразований в числа.
Какой самый быстрый алгоритм деления сумасшедших больших целых чисел?
Ответы (2)
Деление по принципу «разделяй и властвуй» оказывается намного быстрее, чем метод школьных учебников для действительно больших целых чисел.
GMP — это современная библиотека больших чисел. Почти для всего у него есть несколько реализаций различных алгоритмов, каждая из которых настроена на определенные размеры операндов.
Здесь представлена документация GMP по "алгоритмам деления". Описания алгоритмов немного кратки, но они, по крайней мере, дают вам что-то для поиска в Google, когда вы хотите узнать больше.
Брент и Циммерманн "Современная компьютерная арифметика" — хорошая книга по теория и реализация арифметики больших чисел. Вероятно, стоит прочитать, если вы хотите знать, что известно.
person
tmyklebu
schedule
26.06.2013
Да, но... как я уже сказал, эти алгоритмы НАМНОГО сложнее, чем алгоритм D. Основная причина использования "разделяй и властвуй" заключается в том, что вы можете использовать алгоритм Карацубы, и позвольте мне рассказать вам, как написать все это плюс реализацию Карацубы. будет МНОГО работы, и я имею в виду МНОГО МНОГО работы. Я не знаю, насколько хорошим программистом является OP, но даже очень хороший программист может потратить МЕСЯЦЫ на написание правильной реализации, используя разделяй и властвуй.
- person Tyler Durden; 26.06.2013
@TylerDurden: Ну, он спросил о безумно больших числах. Карацуба сама по себе неплоха, так как вы не сталкиваетесь с проблемами степени двойки. Это становится большой работой, когда вы начинаете хотеть реализовать Toom-Cook и различные методы на основе БПФ, а затем выяснять точки пересечения. Вот почему вы используете GMP для этого :)
- person tmyklebu; 26.06.2013
@TylerDurden: И деление по принципу «разделяй и властвуй» совсем не так уж плохо, если у вас есть черный ящик быстрого умножения. Возьмите старшую половину числителя и знаменателя, рекурсивно разделите, а затем выполните небольшую очистку. Опять же, настройка и поиск точки пересечения между учебником и принципом «разделяй и властвуй» — немалая работа.
- person tmyklebu; 26.06.2013
Стандартный алгоритм деления в длину, аналогичный алгоритму деления в длину в начальной школе, представляет собой алгоритм D, описанный в Кнуте 4.3.1. Кнут подробно обсуждает деление в этом разделе своей книги. В результате есть более быстрые методы, чем алгоритм D, но они ненамного быстрее и намного сложнее, чем алгоритм D.
Если вы решили получить максимально быстрый алгоритм, вы можете прибегнуть к тому, что известно как алгоритм SRT.
Все это и многое другое описано в Алгоритме деления в Википедии.
person
Tyler Durden
schedule
26.06.2013
Из алгоритмов, перечисленных по ссылке в Википедии, вы, вероятно, обнаружите, что должное деление является наиболее полезным. Однако будьте осторожны с обозначениями. D(0) указывает на наименее значащее значение в числе, а сдвиг влево предполагает, что числа хранятся с обратным порядком байтов (что означает, что LSD должен быть в D(n-1) ).
- person Python Cheese; 14.04.2017
BigInteger- довольно плохая вещь, если вы хотите, чтобы ваши операции были быстрыми. Умножение и деление выполнены по школьной программе в канонической реализации. - person tmyklebu schedule 26.06.2013