什麼是計算任意精度兩因子比率的有效方法？

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.）使用Schönhage-Strassen算法與牛頓的倒數方法相結合進行分割。

雖然這只是一個初始想法。

是否有更具體的高效算法來計算任意精度的兩個因子的比例？

Answer 1

你不需要分割，只需要從（2k + 1）到（2n）的數字相乘，這顯然可以在指定的範圍內完成;）。