Требуется алгоритм быстрого деления одного длинного числа на другое. Быстрее, чем за O(n^2) (деление в столбик). Числа целые, основание системы счисления - 10^4.
Исходник не обязателен, но если есть только он, то выкладывайте (желательно на C/C++/Pascal).

деление можно заменить на умножение на обратное число, а быстрых умножений - хоть отбавляй

а как же бесконечность рациональных дробей? потребовалось мне разделить чего-нибудь на 7^100: считаю обратное - до фига нулей, что-то страшное и какой-то левый период. И как мне прикажете это умножать на, к примеру, 15*(7^101) ? 

а даже если с этим и разобраться, то как быстро делить единицу на число (т.е. получить предпериод и период)?

p.s.быстрым умножением у меня выступает Карацуба.

http://informatics.mccme.ru/moodle/file.ph...-arifmetika.doc

хотя предполагаю что тут не самые оптимальные решения. Но может чем-то поможет.

Это сообщение отредактировал(а) azesmcar - 22.4.2009, 13:08

к сожалению, там только алгоритм деления длинного на короткое. а алгоритм умножения реализован за квадрат.
:-(


Это сообщение отредактировал(а) yeputons - 22.4.2009, 13:24

yeputons

Посмотрите во второй книге Дональда Кнута - Целочисленные вычисления. Там должен быть алгоритм. Лучше этого вряд ли найдете или придумаете 

можно попробовать покрутить в сторону Фурье - попробовать провести рассуждения, похожие на умножение длинных чисел... хотя не уверен, что получится...

Кнут советует найти сначала число 1/b, потом умножить его на a. А нахождение обратного числа (как раз самое интересное) предлагается модифицированными итерациями Ньютона. В итоге, как утверждается, это обратное число может быть найдено за время O(N)+T(8N), где T(x) - это время, необходимое для перемножения двух чисел длины x.

Таким образом, если для умножения мы используем что-нибудь более умное, чем столбик (Шенхаге-Штрассена за N log N (описано в Кормене) или Карацубу за N^1.73), то и деление мы можем выполнить асимптотически за то же время.

гм. то есть все-таки писать плавающую точку?

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

Это сообщение отредактировал(а) maxdiver - 23.4.2009, 23:32

я вот тоже так думаю... хотя, если подумать, то и плавающая точка не так уж страшно - можно хранить не один массив цифер, а два...
хотя я думаю, что просто заюзаю OpenSSL (изначальная цель была написать то ли Elgamal, то ли RSA)