我怎样才能加速这个Julia代码？
我怎样才能加速这个Julia代码？
提问于 2017-04-06 01:06:18
该代码实现了Pollard rho()函数的一个示例，该函数用于查找正整数n的因子。我检查了Julia "Primes“包中的一些代码，这些程序包快速运行，试图加快pollard_rho()函数的速度，但都无济于事。代码应该在大约100秒到30秒(Erlang，Haskell，Mercury，SWI Prolog)内执行n= 1524157897241274137，但在JuliaBox，IJulia和Julia REPL上需要大约3到4分钟。我怎么才能让这一切变得更快呢？
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 # moduleStack Overflow用户
发布于 2017-04-06 02:14:13
这里有相当多的类型不稳定性问题。
Chris提到，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宏。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43237472
复制相关文章
相似问题
腾讯云开发者
