Вы делите число из n бит на кусочки по √n бит. Представляете кусочки как коэффициенты полинома степени √n. Перемножаете полиномы. Преобразование Фурье требует как минимум O(√n log n) сложений (если быстро на корни из единицы умножать), стоящих √n, и потом нужно ещё √n умножений чисел из ≈√n бит. Эти умножения обрабатываются рекурсивно тем же алгоритмом. Возникает рекуррентная формула для оценки сложности: C(n) = n log n + √n C(√n). Разворачивая рекурсию, получаем n log n log log n, где множитель log log n отвечает за количество рекурсивных шагов.
На самом деле оригинальная научная статья довольно неплохо разъясняет существующие алгоритмы (если вы не боитесь терминов «FFT» и «кольцо вычетов»).
Делят, по крайней мере вещественные числа, обычно методом Ньютона, а у него квадратичная сходимость, то есть требуется логарифмическое число шагов. А сложность шага пропорциональна сложности умножения.
Если в апи есть проблема, её надо обсуждать и находить пути решения. Главным образом этой статьёй я хотел узнать, один я ли вижу проблему или она действительно есть.
Ничего не поделать, дорогие хабровчане очень любят посты, в которых программисты самые умные, и очень не любят посты, в которых программисты не самые умные. Автор убедительно это доказывает нам уже целой серией своих постов (особенно предыдущим постом, ушедшим в минус). Автор, можно сказать, социальный экспериментатор.
Ну то есть насчёт скорости мы должны вам на слово поверить? Или самостоятельно для этого реализовать алгоритм, и ещё додуматься до упомянутых выше «интересных нюансов»?
В смысле очевидны? Сгенерируйте большой массив строк/чисел, отсортируйте их квиксортом и своим алгоритмом на одной и той же машине и покажите время выполнения в секундах.
Без сравнения секунд заверения про невероятную эффективность основаны ни на чём.
Зато сортировка слиянием даёт O(N log N). А если в квиксорте делать поиск медианы за O(N) для пивотирования, там тоже будет гарантированное O(N log N).
Если для вас элементарная архитектура, без которой даже design interview нельзя пройти, это сложно — я ничем не могу помочь. Я вроде бы обосновал необходимость всех компонент и даже ссылался на опыт крупных сервисов (в комментах).
На самом деле оригинальная научная статья довольно неплохо разъясняет существующие алгоритмы (если вы не боитесь терминов «FFT» и «кольцо вычетов»).
(мягкий знак, Карл!) так оно и есть. Только где-то ещё имело место text recognition.
> ни одной ссылки на исследования
Без сравнения секунд заверения про невероятную эффективность основаны ни на чём.
Ken Thompson — Reflections on Trusting Trust