performance - How can I speedup this Julia code? -


the code implements example of pollard rho() function finding factor of positive integer, n. i've examined of code in julia "primes" package runs rapidly in attempt speedup pollard_rho() function, no avail. code should execute n = 1524157897241274137 in approximately 100 msec 30 sec (erlang, haskell, mercury, swi prolog) takes 3 4 minutes on juliabox, ijulia, , julia repl. how can make go fast?

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 

there quite few problems type instability here.

  1. don't return either string "error" or result; instead explicitly call error().

  2. as chris mentioned, x , r ought annotated of type t, else unstable.

there seems potential problem overflow. solution widen in squaring step before truncating type 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 

after making these changes function run fast expect.

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

to find these problems type instability, use @code_warntype macro.


Comments