이 줄리아 코드의 속도를 높이려면 어떻게해야합니까?

이 코드는 양의 정수 n을 찾기 위해 Pollard rho() 함수의 예제를 구현합니다. 필자는 Julia "Primes"패키지에서 pollard_rho() 함수의 속도를 높이기 위해 빠르게 실행되는 코드를 검토했습니다. 코드는 약 100 mSec ~ 30 Sec (Erlang, Haskell, Mercury, SWI Prolog)에서 n = 1524157897241274137을 실행해야하지만 JuliaBox, IJulia 및 Julia REPL에서는 약 3 ~ 4 분이 걸립니다. 어떻게하면 빨리 할 수 있을까요?이 줄리아 코드의 속도를 높이려면 어떻게해야합니까?

pollard_rho (1524157897241274137) = 1,234,567,891

__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'는 약간의 작업이 필요합니다. 다른 언어가 사용하는 알고리즘을 알고 있습니까? Julia 's : https://github.com/JuliaLang/julia/blob/master/base/intfuncs.jl#L3 –

여기 유형 불안정 꽤 몇 가지 문제가 있습니다.

는 문자열 "error" 또는 결과 중 하나를 반환하지 마십시오 대신 error()을 명시 적으로 호출하십시오.
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 매크로를 사용합니다.

출처

2017-04-05 18:14:12

아, 정말 고마워요. – dogwood

나는 반환이 사용되지 않았기 때문에 반환의 불안정성이 여기서 중요하지 않다고 생각했다. –

예, 최종 사용자가 REPL에서 직접 사용하는 경우 중요하지 않습니다. 그러나 다른 상위 함수들이'pollard_rho'를 호출하는 것이 중요합니다. –

이 줄리아 코드의 속도를 높이려면 어떻게해야합니까?

답변

관련 문제