在我的受 Prolog 启发的语言 Brachylog 中,有可能标记具有潜在无限域的 CLP(FD) 等效变量。可以在 here 中找到执行此标记的代码(感谢 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 需要实例化列表,如果它的长度很大,这很糟糕。
我们如何改进这个谓词,使其即使对非常大的数字也有效,具有相同的行为?
最佳答案
已经发布了许多好的想法,并且它们在不同程度上起作用。
附加测试用例
@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
。主要特点
当然,这些点中哪一点最重要是很清楚的。
示例查询
创造 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 .
其他的建议
between/3
的特定于实现的异常:这些会破坏谓词的重要语义属性,并且不能移植到其他系统。 infinite
而不是 inf
。在 CLP(FD) 的上下文中,inf
表示整数集的 infimum ,它与正无穷大正好相反。 between/3
和其他不考虑约束的谓词。 非常感谢您对这个问题和已发布的解决方案感兴趣!我希望您发现上面的测试用例对您的变体有用,并找到在您的版本中考虑 CLP(FD) 约束的方法,以便它们运行得更快,我们都可以为它们点赞!
关于prolog - 适用于大数的 positive_integer/1 谓词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39253077/