positive_integer/1谓词适用于大数字

Question

在我的Prolog启发语言Brachylog中,有可能标记具有潜在无限域的CLP(FD)等价变量.可以在此处找到执行此标注的代码(感谢Markus Triska @mat).

此谓词需要存在谓词positive_integer/1,该谓词必须具有以下行为:

?- positive_integer(X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
…

这在我们当前的解决方案中实现:

positive_integer(N) :- length([_|_], N).

这有两个我可以看到的问题:

• 这会很快变慢:

  ?- time(positive_integer(100000)).
  % 5 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
  
  ?- time(positive_integer(1000000)).
  % 5 inferences, 0.000 CPU in 0.008 seconds (0% CPU, Infinite Lips)
  
  ?- time(positive_integer(10000000)).
  % 5 inferences, 0.062 CPU in 0.075 seconds (83% CPU, 80 Lips)
  

• 这最终Out of global stack会为有点太大的数字返回错误:

  ?- positive_integer(100000000).
  ERROR: Out of global stack
  

这显然是因为Prolog需要实例化列表,如果它的长度很大则这很糟糕.

我们如何才能改进这个谓词,这样即使对于非常大的数字,它也会有相同的行为？

Answer 1

已经发布了许多好的想法,并且它们在不同程度上发挥作用.

附加测试用例

@vmg有正确的直觉:between/3不能与约束混合得很好.为了看到这个,我想使用以下查询作为额外的基准:

?- X #> 10^30, positive_integer(X).

解

考虑到测试用例,我建议采用以下解决方案:

positive_integer(I) :-
        I #> 0,
        (   var(I) ->
            fd_inf(I, Inf),
            (   I #= Inf
            ;   I #\= Inf,
                positive_integer(I)
            )
        ;   true
        ).

关键思想是使用CLP(FD)反射谓词 fd_inf/2来推断变量域中的最小元素.当您将解决方案移植到其他Prolog系统时,这是您需要更改的唯一谓词.例如,在SICStus Prolog中,谓词被调用fd_min/2.

主要特点

• 可移植到几个Prolog系统,只需极少的更改
• 在所示的情况下快速
• 工作也按以上测试案例
• 广告并使用CLP(FD)约束的全部功能.

当然,非常清楚哪一点是最重要的.

示例查询

crehtio ex nihilo:

?- positive_integer(X).
X = 1 ;
X = 2 ;
X = 3 .

固定整数:

?- X #= 12^42, time(positive_integer(X)).
% 4 inferences, 0.000 CPU in 0.000 seconds (68% CPU, 363636 Lips)
X = 2116471057875484488839167999221661362284396544.

约束整数:

?- X #> 10^30, time(positive_integer(X)).
% 124 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 3647059 Lips)
X = 1000000000000000000000000000001 ;
% 206 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 2367816 Lips)
X = 1000000000000000000000000000002 ;
% 204 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 2428571 Lips)
X = 1000000000000000000000000000003 .

其他的建议

1. 首先,请务必查看Brachylog和Code Golf上最新的Brachylog解决方案.感谢Julien的努力,一种受Prolog启发的语言现在越来越多地主持一些最简洁优雅的程序.朱利安真棒!

2. 请避免使用特定于实现的异常between/3:这些异常会破坏谓词的重要语义属性,并且不能移植到其他系统.

3. 如果你忽略(2),请使用infinite而不是inf.在CLP(FD)的上下文中,inf表示整数集的下确界,这与正无穷大完全相反.

4. 在CLP(FD)的情况下,我建议使用CLP(FD)的约束,而不是中between/3和其他谓词不采取约束考虑在内.

5. 事实上,我建议使用CLP(FD)的约束,而不是的所有低级别的谓词理智战胜了整数.这可以最多使程序更普遍的,从来没有更具体.

非常感谢您对这个问题和发布的解决方案的兴趣!我希望您发现以上测试用例对您的变体有用,并找到在您的版本中考虑CLP(FD)约束的方法,以便它们运行得更快,我们都可以对它们进行投资!