計算大Catalan數模素

Question

是否有人知道計算加泰羅尼亞大數目的快速算法模素（這是1.000.000.007）約500.000

的輸入值已經花了相當長的一段時間就可以了但我無法修改普通公式來處理這麼高的數字，而且動態算法耗時過長。

我會任何幫助:)

Answer 1

使用開源和基於Python程序sage它需要在我的舊雙核心2.80GHz的筆記本電腦11秒計算剩餘類加泰羅尼亞數量非常感謝你要求：

huisman@thom:~$ sage 
┌────────────────────────────────────────────────────────────────────┐ 
│ SageMath Version 6.10, Release Date: 2015-12-18     │ 
│ Type "notebook()" for the browser-based notebook interface.  │ 
│ Type "help()" for help.           │ 
└────────────────────────────────────────────────────────────────────┘ 
sage: time catalan_number(5*10^5).mod(10^9+7) 
CPU times: user 11.3 s, sys: 0 ns, total: 11.3 s 
Wall time: 11.3 s 
213941567 

通過檢查代碼，你可以得到一個想法如何做到這麼快。