APL의 Pollard Rho 구현

Question

최근 APL을 사용하여 작업하려했지만 개념화가 어려웠습니다. 예를 들어, 프로그램을 < -pollard x로 만들고 싶다고 가정 해 봅시다. Pollard-Rho 메서드를 통해 숫자 x가 소수인지 팩터 블인지 계산합니다.

나는 방법 자체를 알고 있지만 APL에 실제로 통합하기 시작 해야할지 모르겠다. 이 함수에서 사용할 완전히 새로운 함수 f (x)를 작성해야합니까? 아니면 코드에 모든 것을 포함해야합니까? 이전 실행에서 x를 저장하여 다음 실행에 사용하려면 어떻게해야합니까? 저는 전체 프로그램을 요구하지 않고, 저를 시작하기위한 몇 가지 권고 사항을 요구합니다.

Answer 1

처음에는 모르는 언어를 사용해 보았을 때 약간 사소한 것입니다. 있을 수있는대로, 나는 문제를 흥미롭게 발견하고 당신을 위해 몇 가지 해결책을 채찍질했다. Dyalog APL을 사용하여 수행됩니다. APL 초보자는 약간의 학습이 필요합니다.

PollardRho←{ 
    n←⍵ 
    ⍺←2 2 1 
    x y d←⍺ 
    f←{n|1+⍵*2} 
    x←f x 
    y←f f y 
    d←n∨|x-y 
    d=n:'Failure' 
    d≠1:d 
    x y d ∇ n 
} 

우리는 APL 세션에서 이것을 시도 할 수 있습니다 :

첫 번째 솔루션은 주요 기능에 직접 포함 된 F (X)와, (위키 백과에 의해 정의 된대로) 폴라드의 Rho에 대한 간단한 기능입니다 :

 PollardRho 8051 
97 

번째 방법은 주요 기능의 함수 f (X)를 추출하고, F (x)에 대한 다양한 기능을 사용하여 편리 인수로 그것을 제공한다.

PollardRho2←{ 
    n←⍵ 
    ⍺←2 2 1 
    x y d←⍺ 
    x←n ⍺⍺ x 
    y←n ⍺⍺ n ⍺⍺ y 
    d←n∨|x-y 
    d=n:'Failure' 
    d≠1:d 
    x y d ⍺⍺ ∇∇ n 
} 

우리는 우선 함수 f (X)를 형성하고, 왼쪽 피연산자로서 제공함으로써 세션이 실행 :

APL, 인수는 운영자라고로서의 기능을 취하는 함수

 f←{⍺|1+⍵*2} 
     f PollardRho2 8051 
97 

두 솔루션 모두 꼬리 재귀를 사용합니다.

당신이 유용하다고 생각합니다.