このジュリアコードをスピードアップするにはどうすればよいですか？

Question

このコードは、正の整数nを求めるPollard rho（）関数の例を実装しています。私は、pollard_rho（）関数を高速化しようとして、急速に動作するJulia "Primes"パッケージのコードを調べました。コードは、約100mSec〜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 # module 

Answer 1

は、ここではタイプの不安定性とかなりの数の問題があります。

1. "error"または結果のいずれも返しません。代わりに明示的にerror()を呼び出します。

2. 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マクロを使用してください。