代码之家 › 专栏 › 技术社区 › Gregory Higley

如何在j中以惯用方式生成rowland素数序列?

j tacit-programming

1

Gregory Higley · 技术社区 · 14 年前

如果你不熟悉罗兰素数序列,你可以了解它。 here . 我在j中创建了一个难看的程序性单态动词来生成第一个 n 按以下顺序排列的术语:

rowland =: monad define
    result =. 0 $ 0
    t =. 1 $ 7
    while. (# result) < y do.
        a =. {: t
        n =. 1 + # t
        t =. t , a + n +. a
        d =. | -/ _2 {. t
        if. d > 1 do.
            result =. ~. result , d
        end.
    end.
    result
)

这是完美的,它确实产生了第一个 n 顺序中的术语。(由 n 术语,我是说第一个 n 不同的 素数)

这是的输出 rowland 20 :

5 3 11 23 47 101 7 13 233 467 941 1889 3779 7559 15131 53 30323 60647 121403 242807

我的问题是, 我怎么能用更习惯的J来写这个呢? 我没有线索,尽管我编写了下面的函数来找出数字列表中每个连续数字之间的差异,这是必需的步骤之一。在这里,虽然它也可能被比我更有经验的J程序员重构:

diffs =: monad : '}: (|@-/@(2&{.) , $:@}.) ^: (1 < #) y'

2 回复 | 直到 12 年前

1

2

estanford 14 年前

我还没有完整的答案,但是 this essay 由罗杰辉有一个默契的结构,你可以使用替换显式while循环。另一个(相关的)方法是将块的内部逻辑转换成这样一种默契的表达:

FUNWITHTACIT =: ] , {: + {: +. 1 + #
rowland =: monad define
    result =. >a:
    t =. 7x
    while. (# result) < y do.
      t =. FUNWITHTACIT t
      d =.  | -/ _2 {. t
      result =. ~.result,((d>1)#d)
    end.
    result
)

(不过,为了提高效率,您可能希望保留if块,因为我编写代码的方式 result 无论是否满足条件,都会修改——如果不满足条件,则修改无效。这个 if 甚至可以使用议程运算符将逻辑写回默认表达式。)

完整的解决方案包括找出如何将while循环中的所有逻辑表示为单个函数,然后使用roger的技巧将while逻辑实现为一个默契表达式。我来看看能不能出现。

作为旁白,我让J来建造 FUNWITHTACIT 对于我来说,通过使用代码的前几行,手动替换您声明的变量值函数(我可以这样做,因为它们都以不同的方式对单个参数进行操作),替换 t 具有 y 并让J建立结果表达式的隐性等价物:

]FUNWITHTACIT =: 13 : 'y,({:y)+(1+#y)+.({:y)'
   ] , {: + {: +. 1 + #

使用13来声明monad是J知道如何获取monad(否则显式声明为 3 : 0 或 monad define 正如您在程序中所写),并将显式表达式转换为隐式表达式。

编辑:

以下是我在评论中提到的为Avenue(2)编写的函数:

candfun =: 3 : '(] , {: + {: +. 1 + #)^:(y) 7'
firstdiff =: [: | 2 -/\ ]
triage =: [: /:~ [: ~. 1&~: # ]
rowland2 =: triage @firstdiff @candfun

此函数使用rowland递推关系生成前n个多候选数,评估它们的第一个差异,丢弃所有等于1的第一个差异,丢弃所有重复项,并按升序对它们进行排序。我认为这还不完全令人满意,因为争论设定了要尝试的候选人数量,而不是结果数量。但是,它仍然在进步。

例子:

   rowland2 1000
3 5 7 11 13 23 47 101 233 467 941

这里是我发布的第一个函数的版本,将每个参数的大小保持在最小:

NB. rowrec takes y=(n,an) where n is the index and a(n) is the
NB. nth member of the rowland candidate sequence. The base case
NB. is rowrec 1 7. The output is (n+1,a(n+1)).
rowrec =: (1 + {.) , }. + [: +./ 1 0 + ]

rowland3 =: 3 : 0
 result =. >a:
 t =. 1 7
 while. y > #result do.
  ts =. (<"1)2 2 $ t,rowrec t
  fdiff =. |2-/\,>(}.&.>) ts
  if. 1~:fdiff do.
   result =. ~. result,fdiff
  end.
  t =. ,>}.ts
 end.
 /:~ result
)

它找到第一个y-许多不同的罗兰素数,并按升序呈现:

   rowland3 20
3 5 7 11 13 23 47 53 101 233 467 941 1889 3779 7559 15131 30323 60647 121403 242807

这个函数的大部分复杂性来自于我对装箱数组的处理。这不是很好的代码,但它只保留 4+#result 在计算期间内存中有许多数据元素(以对数刻度增长)。原功能 rowland 保持 (#t)+(#result) 内存中的元素(以线性比例增长)。 rowland2 y 生成一个数组 Y -许多元素,使其内存配置文件几乎与 罗兰 即使它永远不会超过一个特定的界限。我喜欢 rowland2 因为它的紧凑性,但没有一个公式来预测 Y 需要生成n个不同的素数,该任务需要在试错的基础上完成,因此可能需要比 罗兰 或 rowland3 关于冗余计算。 罗兰3 可能比我的版本更有效率 罗兰 ,因为 富兰克林 重新计算 #t 每次循环迭代-- 罗兰3 只需增加一个计数器,它的计算量较小。

不过,我还是不满意 罗兰3 的显式控制结构。似乎应该有一种方法可以使用递归或其他方法来完成这种行为。

2

3

Gregory Higley 12 年前

虽然我已经将Estanford的答案标记为正确答案,但自从我问这个问题以来,我与J的合作已经有很长的路要走了。下面是一个更为惯用的方法来生成j中的rowland prime序列:

~. (#~ 1&<) | 2 -/\ (, ({: + ({: +. >:@#)))^:(1000 - #) 7

表达式 (, ({: + ({: +. >:@#)))^:(1000 - #) 7 生成所谓的 原始序列 最多1000名成员。这个序列的第一个差异可以由 | 2 -/\ 即每两个元素差异的绝对值。(把这个和我原来的长篇大论相比较 diffs 来自原始问题的动词。)

最后,我们去掉了那些素数和复素数。 ~. (#~ 1&<) 得到素数序列。

这比我以前做的要高得多。它可以很容易地转换成动词来生成 n 略带递归的素数。