primes - APL 中的 Pollard Rho 实现

Question

最近，我尝试使用 APL，但很难将其概念化。例如，假设我想编写一个程序 g<-pollard x，其中函数通过 Pollard-Rho 方法计算数字 x 是素数还是可因式分解。

我知道方法本身，但我不知道从哪里开始将它实际集成到 APL 中。我应该首先创建一个全新的函数 f(x) 以供此函数使用，还是应该在代码中包含所有内容？我将如何保存上一次运行的 x 以用于下一次运行？请注意，我不是要一个完整的程序，只是一些让我开始的建议。

Answer 1

首先，这对于尝试一门你不知道的语言来说有点微不足道。尽管如此，我发现这个问题很有趣，并为您提供了一些解决方案。这些是使用 Dyalog APL 完成的。对于 APL 新手，他们需要一些学习。

第一个解决方案是 Pollard Rho 的一个简单函数（由 Wikipedia 定义），将 f(x) 直接嵌入到主函数中：

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 会话中尝试一下：

     PollardRho 8051
97

第二种方法是从主函数中提取函数f(x)，作为参数提供，方便f(x)使用不同的函数。在 APL 中，将函数作为参数的函数称为运算符：

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) 并将其作为左操作数在会话中运行它：

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

请注意，这两种解决方案都使用尾递归。

希望这个对你有帮助。