研究論文で、私は次の声明を読みました
S (...) と C (...) の計算には、(2n)!/(2k)! のような階乗の比率の計算が含まれます。ここで、0 ≤k ≤ n です。これは、単純なアルゴリズムによって時間 O(n^2(logn)^2) で実行できます。
彼らは、どの単純なアルゴリズムについて話しているのかについては言及していません。彼らが整数の直接乗算について話している場合、このリンクによると、n! 計算だけでは O(n^2 log n) になるため、除算に約 O(log n) の時間がかかりますが、これは不可能だと思います。
私が考えることができる1つのアプローチは次のとおりです:- 1.)ここから高速階乗アルゴリズムを選択します。2.) ニュートンの逆数法と組み合わせた Schönhage-Strassen アルゴリズムを使用した除算。
ただ、それは最初のアイデアにすぎません。
任意の精度で 2 つの階乗の比を計算するためのより具体的な効率的なアルゴリズムはありますか?