Julia记下了Fuss-Catalan数字的代码

Question

从Fuss-Catalan系列C {4} _n(参见在线百科全书序列OEIS A002293),我想用memoization计算第n个术语.我在下面编写的代码可以工作,但在我的笔记本电脑上n = 200时需要大约43秒.有没有办法进一步提高速度？

numterms = 20
C4 = Array{BigInt}(numterms+1) # memoization dictionary
fill!(C4,-1) # -1 implies not yet computed
C4[1] = 1 # Base case for n=0, C[n+1] provides nth term

function catalan4(n,C)
    C[n+1] == -1 || return C[n+1]
    sum1 = convert(BigInt,0)
    for i in 1:n
       sum2 = convert(BigInt,0)
       for j in 1:(n-i+1)
            sum3 = convert(BigInt,0)
            for k in 1:(n-i-j+2)
                sum3+= catalan4(k-1,C)*catalan4(n-i-j-k+2,C)
            end
            sum2 +=  catalan4(j-1,C)*sum3          
       end
       sum1 +=  catalan4(i-1,C)*sum2 
    end
    C[n+1] = sum1    
    return sum1
end 

for i in 1:numterms
    println(i,"\t",catalan4(i,C4))
end    

这提供了预期:

1   1
2   4
3   22
4   140
5   969
6   7084
7   53820
8   420732
9   3362260
10  27343888
11  225568798
12  1882933364
13  15875338990
14  134993766600
15  1156393243320
16  9969937491420
17  86445222719724
18  753310723010608
19  6594154339031800
20  57956002331347120

谢谢!

Answer 1

我怀疑糟糕的BigInt表现是罪魁祸首.你可能想尝试Nemo,它使用Flint库来获得任意精度整数,我理解它效率更高.如果你想留在标准Julia(Nemo是基于Julia的,但在某些语言语义上不同于Julia,afaik - 它是计算机代数系统)并且你的数字限制为小于2 ^ 127,那么你可以尝试使用Int128相反 - 这些可以堆栈分配并保存在寄存器中,不像BigInts,它必须是堆分配的,哪个LLVM不知道如何推理(它不能将new的创建BigInts转换为现有的变异).创建使用两个/四个值来执行算术的自定义Int256和Int512类型可能并不太难Int128,特别是如果您只需要支持加法和乘法.