Что было бы эффективным способом вычисления отношения двух факториалов с произвольной точностью?

Question

В research paper, я прочитал следующее заявление

вычислений S (...) и C (...) включает вычислительные отношения факториалов , такие как (2n)!/(2k)! , где 0 ≤k ≤ n. Это можно сделать за время O (n^2 (logn)^2) простым алгоритмом.

Они не упомянули, о каком прямом алгоритме они говорят. Если речь идет о прямом умножении целых чисел, то согласно this link, общее время для n! Само по расчету будет O (n^2 log n), что оставляет нас вокруг O (log n) времени для деления, что, я думаю, невозможно.

Один из подходов, который я могу придумать, заключается в следующем: - 1.) Выбор быстрого факториального алгоритма от here. 2.) Разделение по алгоритму Шенхаге-Штрассена в сочетании с обратным методом Ньютона.

Это только начальная идея.

Есть ли более конкретный эффективный алгоритм для вычисления отношения двух факториалов с произвольной точностью?

Answer 1

Вам не нужно делиться, вы просто умножаете числа от (2k + 1) до (2n), это, очевидно, можно сделать в указанных пределах;).