Алгоритм деления чисел с использованием обратной величины , Какова его сложность?

[piligrim1]

На многих форумах говорят, что когда нужно произвести много делений с одним делителем, выгоднее найти величину обратную делителю и умножать на нее. Я реализовал такой алгоритм и проверил скорость. Оказалось, что никакого преимущества нет, более того такой алгоритм проигрывает примерно в 1,1-1,4 раза по сравнению с делением по Кнуту(2т.). Стал разбираться. Оказалось, что при таком делении выполняется 2 умножения. И хотя каждое из них быстрее деления, в сумме они работают дольше. В связи с этим вопрос:

Деления чисел с использованием обратной величины всегда невыгодно?

Или я что-то непонимаю..

[AVA12]

У тебя ошибка в семнадцатой строке.

[piligrim1]

ты про Кнута? У меня работает все правильно.

[MBo]

>ты про Кнута?
Он про то, что никто не видел, что ты написал, откуда два умножения и т.д.

[piligrim1]

Я спрашиваю не про реализацию, а про сам алгоритм.

n = q * d + r

n - делимое
d - делитель
q - частное
r - остаток

Обычный алгоритм деления, приводить не буду (классический по Кнуту(т2)).

С обр. вел-ной. Есть делимое n, делитель d. Нужно получить q - частное r - остаток

Псевдокод (+упрощено) :

1. reciprocal = 1 / d ; // сначала находим обр. вел-ну
2. b = n * reciprocal ; // эквивалентно делению n на d, получаем приближение к q
3. m = b * d ; // получаем прибл. к n
4. q = n - m ;
5. while( q >= d )
{
q-=d ; // получаем остаток
}

[Pavia]

Получение остатка в изночальное условие не входит.

Добавлено 05.10.12, 12:58
Во вторых распиши класический алгоритм деления. Иначе непонятно что с чем сравниваете.

[piligrim1]

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

Добавлено 05.10.12, 13:08
Описывать классич. алгоритм слишком трудоемко, он большой. Можно посмотреть в гугле или в у Кнута(т2), здесь Алгоритм деления двух длинных чисел помоему Dethlord тоже его описал.

[AVA12]

Раз уж речь зашла об остатках от деления, то, наверное, используются целочисленные вычисления? Но что тогда представляет собой reciprocal = 1 / d? Число с плавающей точкой? И какого размера числа используются?

[piligrim1]

Простите меня ребята, но я думал, что я профан.. Не обижайтесь.
Используются только целые, никакой плавающей точки. 1/d это 2^x / d. x выбир. из условия 2^x >= d > 2^(x+1).

[AVA12]

Цитата

Простите меня ребята, но я думал, что я профан.. Не обижайтесь.

Дык, как же тут разберешься? Задачу корректно не ставишь, код не показываешь. Спрашиваешь про чистый алгоритм, однако утверждения вроде "два умножения выполняются дольше деления" относятся именно к реализации и к размеру чисел.

Цитата

2^x >= d > 2^(x+1)

Может, надо все-таки заменить "больше" на "меньше"? Или плюс на минус?

[piligrim1]

Цитата

Дык, как же тут разберешься? Задачу корректно не ставишь, код не показываешь. Спрашиваешь про чистый алгоритм, однако утверждения вроде "два умножения выполняются дольше деления" относятся именно к реализации и к размеру чисел.

Вопрос не по изобретенному мною алгоритму, а по существующем и известным. Какая разница, какой размер чисел? Есть делимое, есть делитель, нужно найти частное и остаток, используя упомянутые алгоритмы. Алгоритм с обратной величиной проигрывает на любых(до FFT) числах. Код можно взять из любой более менее вменяемой библиотеки(например ssl).
В формуле ошибся, согласен.

[Pavia]

piligrim1

Цитата piligrim1 @ 05.10.12, 11:24

Деления чисел с использованием обратной величины всегда невыгодно?

Правильный ответ такой. Скорость выполнения зависит от реализации.

Цитата piligrim1 @ 05.10.12, 12:07

Я спрашиваю не про реализацию, а про сам алгоритм.

Ну так и надо сравнивать алгоритмы. Иначе никак.
Если сравнивать алгоритмы. То их надо сравнивать экспоненциально. У Кнута про это сказано.

Умножение требует O(N*Log(N)).
Деление O(N*M)
Деление через умножение требует O(N*Log(N))

Так что при таком сравнение алгоритм деления будет быстрее при N стремящемся к бесконечности.

Теперь сравним в элементарных операциях умножения.
Возьмем алгоритм длинного умножения через БПФ. В качестве алгоритма БПФ возьмем алгоритм Кули-Тунуки.
Этот алгоритм требует чисел кратных 2^k.

БПФ требует 2*N*LOG2(N) вещественных умножений
Умножение через БПФ требует БПФ обратное БПФ один проход для умножения и один проход для нормировки.
2*N*LOG2(N)+2*N+2*N*LOG2(N)+2*N=
4*N*LOG2(N)+4*N=4*N*(LOG2(N)+1)

Теперь возьмем деление.
Для деления нам надо выполнить в лучшем N*M умножение.
Если M <8*(LOG2(N)+1) то деление и получение остатка через обычное деление будет быстрее.
А вот если больше то через умножение будет быстрее.

Сообщение отредактировано: Pavia - 05.10.12, 14:26

[AVA12]

Цитата

Какая разница, какой размер чисел? [...] Алгоритм с обратной величиной проигрывает на любых(до FFT) числах.

Дык, в чем тогда вопрос? Ты спрашиваешь, может ли алгоритм А работать быстрее алгоритма Б, но одновременно отрицаешь влияние реализации и входных данных на скорость работы алгоритма. Противоречие, однако!

[Pavia]

AVA12
Во-Во. О чём, и речь то говорит возьмите алгоритм, а потом сравнивает скорости в конкретной реализации.
Больно уж на тролля похож.

[piligrim1]

Отвечу по прядку:

Цитата

Правильный ответ такой. Скорость выполнения зависит от реализации.

Ничего нового не сообщающий ответ. Скорость выполнения любого алгоритма зависит от реализации.

Цитата

Умножение требует O(N*Log(N)).

Каким это образом? Умножение произвольных чисел требует O(N*N). И быстрее вы в до FFT диапазоне не умножите( не надо приводить Карацубу(он не поможет) или кл. особые числа ).

Цитата

Деление через умножение требует O(N*Log(N))

Абсолютно бредовая формула. В сложность не входит даже делимое.
БПФ вообще не интересует. Писал же до FFT диапазон.

Цитата

Цитата Какая разница, какой размер чисел? [...] Алгоритм с обратной величиной проигрывает на любых(до FFT) числах.

Дык, в чем тогда вопрос? Ты спрашиваешь, может ли алгоритм А работать быстрее алгоритма Б, но одновременно отрицаешь влияние реализации и входных данных на скорость работы алгоритма. Противоречие, однако!

Никакого противоречия. Еще раз повторяю, размер чисел неважен. Интересует оценка сложности выполнения от размера чисел, а размер может быть любой. Реализация тоже не важна. Я понимаю, что можно написать сложение 2 чисел так, что выполняться оно будет дольше умножения этих чисел, но если стоит цель написать максимально быстрые алгоритмы(возможно даже оптимальные), то сложение будет выполнено быстрее(также как и классическое деление выполнится быстрее). Неужели вы так глупы, что мне приходится об этом писать?

Я получил следующие оценки сложности
M*N
2(M-N)*N
для М=2N оценки должны совпадать, но в реальности алгоритм клас. деления почему-то быстрее.

Сообщение отредактировано: piligrim1 - 05.10.12, 17:18

[Pavia]

Цитата piligrim1 @ 05.10.12, 17:12

Еще раз повторяю, размер чисел неважен.

Цитата piligrim1 @ 05.10.12, 17:12

БПФ вообще не интересует. Писал же до FFT диапазон.

Вы уж определитесь. Вам длинные числи или 2 бита перемножить?

Цитата piligrim1 @ 05.10.12, 17:12

Абсолютно бредовая формула. В сложность не входит даже делимое.

Это вы формулу просто не умете читать. Идите почитайте про экспоненциальную оценку сложности алгоритма.

Добавлено 05.10.12, 18:51

Цитата piligrim1 @ 05.10.12, 17:12

Каким это образом? Умножение произвольных чисел требует O(N*N).

Читайте Кнута.

Сообщение отредактировано: Pavia - 05.10.12, 18:51

[piligrim1]

Цитата

Вы уж определитесь. Вам длинные числи или 2 бита перемножить?

Я писал про FFT диапазон, чтобы вы не предлагали Фурье. А так, размер чисел любой.

Цитата

Это вы формулу просто не умете читать. Идите почитайте про экспоненциальную оценку сложности алгоритма.

Взято из Wiki:

Цитата

Экспоненциальная сложность — или экспоненциальное время в теории сложности алгоритмов, время решения задачи, ограниченное экспонентой от размерности задачи. Другими словами, если размерность задачи возрастает линейно, время её решения возрастает экспоненциально.

В моем случае размерность задачи определяется параметрами M и N.

Цитата

Читайте Кнута.

Не надо приводить теоретическую возможность умножения. У меня практическая задача, которую нужно реализовать на существующих в реальном мире машинах, а не выдуманных Кнутом с целью оптимизации под ту или иную задачу. В подтверждение моих слов, факты: моя библиотека выполняет умножение O(N*N), SSL выполняет умножение O(N*N), и даже GМP выполняет умножение O(N*N).


Мне не хотелось бы здесь спорить, моя задача понять выгодно или нет. Я пришел к выводу, что не выгодно. В некоторых библиотеках деление с обр. вел. реализовано для академического интереса, без к.л. практической ценности.

[Pavia]

piligrim1

Цитата piligrim1 @ 06.10.12, 05:25

Не надо приводить теоретическую возможность умножения. У меня практическая задача, которую нужно реализовать на существующих в реальном мире машинах, а не выдуманных Кнутом с целью оптимизации под ту или иную задачу. В подтверждение моих слов, факты: моя библиотека выполняет умножение O(N*N), SSL выполняет умножение O(N*N), и даже GМP выполняет умножение O(N*N).

Вы бы справку хотя бы к GMP прочитали. Прежде чем позорится.
http://gmplib.org/manual/Multiplication-Al...tion-Algorithms

БПФ определен для любых чисел. Так что у меня реально за O(N*Log(N)) выполняется. Другое дело что для умножения это не лучший алгоритм.
Не хотите использовать быстрые алгоритмы ну не используйте. Тогда не понятно о чем спор.

Сообщение отредактировано: Pavia - 06.10.12, 05:54

[piligrim1]

Цитата

Вы бы справку хотя бы к GMP прочитали. Прежде чем позорится.
http://gmplib.org/manual/Multiplication-Al...tion-Algorithms

Боюсь, что опозорились вы. Вопервых я просил не использовать БПФ, а во вторых БПФ медленней для маленьких чисел(хотя применять его можно и для них).

[Pavia]

Если хотите сравнивать библиотеки так сравнивайте. Я этого не делал. Но не пишите тогда что вы сравниваете алгоритм.
Если вы запускаете тест на компьютере, то это уже идет сравнение реализаций.

Цитата piligrim1 @ 06.10.12, 05:25

Мне не хотелось бы здесь спорить, моя задача понять выгодно или нет. Я пришел к выводу, что не выгодно. В некоторых библиотеках деление с обр. вел. реализовано для академического интереса, без к.л. практической ценности.

Зависит от размера числа. В компьютере к примеру числа i32 умножение выполняется 3 такта а деление с остатком 30-40. Так тут через обратное ещё как выигрывает.
А вот с длинными числами всё наоборот есть алгоритмы деления и умножения за O(N*Log(N)) так что для длинных чисел делать через умножение не имеет смысла. Единственно что константы могут оказаться разными, но честно алгоритмы очень похожи так что константы будут очень близкими.

[piligrim1]

Опять мы уходим в сторону. Мне с самого начала не хотелось формализовать задачу, но похоже, что прийдется.

Дано:
1. множество делимых, каждое из диапазона 2^200 - 2^400
2. множество делителей, некие числа порядка 2^200
3. обратные величины делителей
4. машина с процессором x86 и памятью 4 Gb
Найти:
Самый быстрый способ получить остатки от деления.


PS: Кстати, на моей машине(i7) деление примерно в 2,5-3 раза дольше умножения(проверял). Тч. даже для малых чисел невыгодно.

Сообщение отредактировано: piligrim1 - 06.10.12, 07:16

[Pavia]

Цитата piligrim1 @ 06.10.12, 06:45

Найти:
Самый быстрый способ получить остатки от деления.

При таких условиях можно найти оптимальный метод. Если пойти через БПФ. Просто БПФ надо взять очень оптимизированный(к примеру FFTW).
Хотя не уверен насколько он хорош.
Теоретически нахождение остатка можно сделать через БПФ скорость будет около 756 тактов.
Прямой алгоритм даст порядка 350.

А вот Карцуба может и побыстрее будет.

Добавлено 06.10.12, 07:38
piligrim1
Какая скорость вас устроит?

Сообщение отредактировано: Pavia - 06.10.12, 07:55

[piligrim1]

Цитата

Какая скорость вас устроит?

Предельная.

Карацуба и FFT на таких числах работают медленее(проверял сам и смотрел тесты у других). Преимущество FFT примерно с 1000 бит, рекурсивный Карацуба еще больше.

[Pavia]

Тогда да быстрее прямого не получится. Вернее есть вариант через свёртку но там больше пары тактов не выиграть.

[piligrim1]

Как это через свертку? Умножнение полиномов и есть свертка. Те. через обр. вел-ну вы имеете ввиду?

Сообщение отредактировано: piligrim1 - 06.10.12, 08:18

[Pavia]

piligrim1
Как это ещё придумать надо.
2^n/d=a
a*b=c
c*d=e

o=a-e

Так как b и d константы, то два умножения можно заменить одним
a*k=e
А операция умножения можно заменить свёрткой.
a(*)k=e

Операция свёртка может быть выполнена в лучшем случае за T(N). В худшем оценка не известно, но она очень близка к O(N*Log(N))
Для чисел 2^400 будет около(ленюсь точно считать) 60 умножение 186 сложений

Есть куча приемов которые можно использовать.
Р. Блейхут Быстрые алгоритмы цифровой обработки сигналов

Сообщение отредактировано: Pavia - 06.10.12, 09:17

[amk]

В GMP реализовано по крайней мере три алгоритма: обычный, сложности O(N^2), Карацюбы-Оффмана O(N^1.58) и Тоома-Кука, думается близкий к O(N*(log N)^2).

Метод Карацюбы не так уж сильно уступает "школьному" умножению даже на коротких числах. По крайней мере для фиксированных N можно сделать очень быструю реализацию, поскольку не приходится следить за последовательностью операций. Особенно, если операция умножения медленная.

[ttiger]

piligrim1, можно я всю тему читать не буду, а отвечу кратко?
Итак, современные процессоры и современные компиляторы ОЧЕНЬ не любчт, когда ты считаешь себя умнее их.

ВО времена моей бабушки было модно писать х*х заместо х^2 теперь компилятор делает это за программиста. Во времена моей мамы поколение моей бабушки вещало, что это очень круто. В мои времена компилятор все делает так, как это удобно тому процессору, под который оно компилируется. Деление больше не сложная операция, взятие синуса - отдельная ассемблерная команда на х86, а специальные процессоры (по слухам) за один такт матрицы перемножают.

[amk]

Такая ручная оптимизация имеет смысл разве что при программировании контроллеров и сигнальных процессоров, в критичных по времени выполнения ситуациях. Замена целочисленного деления на константу умножением имеет смысл, когда деление раз в пять медленнее умножения, или когда деления вовсе нет (что бывает в сигнальниках).

[ttiger]

Цитата amk @ 19.10.12, 17:19

Такая ручная оптимизация имеет смысл разве что при программировании контроллеров и сигнальных процессоров

И то не факт. Скорее всего, компилятор все грамотно заменит за тебя, если это имеет смысл. Я же говорю: процессоры по-разному оптимизированы. Где-то прокатит, где-то нет.

Добавлено 19.10.12, 17:52
Раньше деление занимало больше тактов, чем теперь. Изменилось соотношение по количеству тактов между деленрием и умножением на константу. Плюс еще компилятор "старается"

Сообщение отредактировано: ttiger - 19.10.12, 17:52

[amk]

Смотрел я генерацию кода для сигнальников. Штатный компилятор (тот что фирмой предлагается) обычно для деления вызывает подпрограмму, а она выполняет деление чуть ли не школьным алгоритмом - 32 цикла в каждом из которых сравнение, условный переход, вычитание и сдвиг итого вычисление растягивается тактов на 200. А умножение процессор выполняет за один такт. Исключение - степени двойки и совсем малые константы (и то не всегда).