如何加快这个Julia代码？

该代码实现了用于查找正整数n的因子的Pollard rho（）函数的示例。我已经检查了Julia“Primes”包中的一些代码，它试图加快pollard_rho（）函数的速度，但都无济于事。代码应该在大约100毫秒到30秒（Erlang，Haskell，Mercury，SWI Prolog）中执行n = 1524157897241274137，但在JuliaBox，IJulia和Julia REPL上需要大约3到4分钟。我怎样才能让这个过程更快？如何加快这个Julia代码？

pollard_rho（1524157897241274137）= 1234567891

__precompile__() 
module Pollard 

export pollard_rho 

function pollard_rho{T<:Integer}(n::T) 
    f(x::T, r::T, n) = rem(((x^T(2)) + r), n) 
    r::T = 7; x::T = 2; y::T = 11; y1::T = 11; z::T = 1 
    while z == 1 
     x = f(x, r, n) 
     y1 = f(y, r, n) 
     y = f(y1, r, n) 
     z = gcd(n, abs(x - y)) 
    end 
    z >= n ? "error" : z 
end 

end # module

来源

2017-04-05 dogwood

你可以在不同的线程上调用'x = f（x，r，n）'和'y1 = f（y，r，n）'。另外，为什么'r'和'x'不是'T'类型的原因是什么？ –

谢谢。我在定义f时声明了r和x的类型，并在重复键入局部变量时收到警告。至少，这是我对警告报告的理解。 – dogwood

它看起来都很好。分析完全是由于'gcd'功能导致的问题：它占用了我大约85％的时间。也许朱莉娅在基地的'gcd'需要一些工作。你知道其他语言使用什么算法吗？这里是朱莉娅的：https：//github.com/JuliaLang/julia/blob/master/base/intfuncs.jl#L3 –

没有与此类型的不稳定不少问题。

不要返回字符串"error"或结果;而是明确地呼吁error()。
正如克里斯提到的，x和r应该注释为T类型，否则它们将会不稳定。

这似乎也有溢出的潜在问题。解决方法是在平方回归到T之前加宽。

function pollard_rho{T<:Integer}(n::T) 
    f(x::T, r::T, n) = rem(Base.widemul(x, x) + r, n) % T 
    r::T = 7; x::T = 2; y::T = 11; y1::T = 11; z::T = 1 
    while z == 1 
     x = f(x, r, n) 
     y1 = f(y, r, n) 
     y = f(y1, r, n) 
     z = gcd(n, abs(x - y)) 
    end 
    z >= n ? error() : z 
end

进行这些更改后，函数将运行得如您所期望的那样快。

julia> @btime pollard_rho(1524157897241274137) 
    4.128 ms (0 allocations: 0 bytes) 
1234567891

要找到这些类型不稳定的问题，请使用@code_warntype宏。

来源

2017-04-05 18:14:12

啊，非常感谢。 – dogwood

因为没有使用回报，我认为这里回报不稳定并不重要？ –

是的，如果这是最终用户直接从REPL使用的话，这并不重要。但是，如果其他更高级别的函数调用“pollard_rho”，这一点很重要。 –

如何加快这个Julia代码？

回答

相关问题