如何加快這個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代碼？

回答

相關問題