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.
don't return either string
"error"
or result; instead explicitly callerror()
.as chris mentioned,
x
,r
ought annotated of typet
, 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
Post a Comment