positive_integer / 1谓词适用于大数字 [英] A positive_integer/1 predicate that works for big numbers
问题描述
在我的Prolog风格语言 Brachylog 中，有可能标记CLP（FD） - 等效具有潜在无限域的变量。可以在此处找到执行此标注的代码（感谢Markus Triska @mat）。
In my Prolog-inspired language Brachylog, there is the possibility to label CLP(FD)-equivalent variables that have potentially infinite domains. The code that does this labelization can be found here (thanks to Markus Triska @mat).
这个谓词需要存在谓词 positive_integer / 1 ，这必须有以下行为：
This predicate requires the existence of a predicate positive_integer/1, which must have the following behavior:
?- positive_integer(X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
…
这是在我们当前的解决方案中实现的：
This is implemented as such in our current solution:
positive_integer(N) :- length([_|_], N).
这有两个问题我可以看到：
This has two problems that I can see:
-
这会很快变慢：
This becomes slow fairly quickly:
?- 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需要实例化列表，如果它的长度很大就很糟糕。
This is obviously due to the fact that Prolog needs to instantiate the list, which is bad if its length is big.
我们如何改进这个谓词，这样就可以了即使对于非常大的数字，具有相同的行为？
How can we improve this predicate such that this works even for very big numbers, with the same behavior?
推荐答案
已经发布了很多好主意，并且它们在不同程度上发挥作用。
There are already many good ideas posted, and they work to various degrees.
@vmg有正确的直觉：介于/ 3之间与约束不能很好地混合。为了看到这一点，我想使用以下查询作为额外的基准：
@vmg has the right intuition: between/3 does not mix well with constraints. To see this, I would like to use the following query as an additional benchmark:
?- 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 。
The key idea is to use the CLP(FD) reflection predicate fd_inf/2 to reason about the smallest element in the domain of a variable. This is the only predicate you will need to change when you port the solution to further Prolog systems. For example, in SICStus Prolog, the predicate is called fd_min/2.
- 轻便到几个Prolog系统，只需更改
- 快速在显示的情况下
- 工作也在上面的测试用例中
- 广告并使用CLP（FD）限制的全部功能。
- portable to several Prolog systems with minimal changes
- fast in the shown cases
- works also in the test case above
- advertises and uses the full power of CLP(FD) constraints.
当然很清楚以下哪一点是最重要的。
It is of course very clear which of these points is most important.
creatio ex nihilo ：
creatio 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 .
其他评论
Other comments
-
首先，请务必查看 Brachylog 和Code Golf上最新的 Brachylog解决方案。感谢Julien的努力，受Prolog启发的语言现在越来越多地主持一些最简洁优雅的程序。令人敬畏的工作Julien！
First, make sure to check out Brachylog and the latest Brachylog solutions on Code Golf. Thanks to Julien's efforts, a language inspired by Prolog is now increasingly often hosting some of the most concise and elegant programs that are posted there. Awesome work Julien!
请不要在/ 3 之间使用的特定于实现的异常：这些毁灭谓词的重要语义属性，不能移植到其他系统。
Please refrain from using implementation-specific anomalies of between/3: These destroy important semantic properties of the predicate and are not portable to other systems.
如果忽略（2），请使用 infinite 而不是 inf 。在CLP（FD）的上下文中， inf 表示整数集的 infimum ，这是相反的 >正无穷大。
If you ignore (2), please use infinite instead of inf. In the context of CLP(FD), inf denotes the infimum of the set of integers, which is the exact opposite of positive infinity.
在CLP（FD）的上下文中，我建议使用CLP（FD）约束而不是 介于/ 3 和不将约束纳入帐户的其他谓词。
In the context of CLP(FD), I recommend to use CLP(FD) constraints instead of between/3 and other predicates that don't take constraints into account.
事实上，我建议使用CLP（FD）约束代替 所有低级谓词来推理整数。这最多使您的程序更通用，从不更具体。
In fact, I recommend to use CLP(FD) constraints instead of all low-level predicates that reason over integers. This can at most make your programs more general, never more specific.
非常感谢您对这个问题和发布的解决方案感兴趣！我希望您发现以上测试用例对您的变体有用，并找到在您的版本中考虑CLP（FD）约束的方法，以便它们运行得更快，我们都可以对它们进行投票！
Many thanks for your interest in this question and the posted solutions! I hope you find the test case above useful for your variants, and find ways to take CLP(FD) constraints into account in your versions so that they run faster and we can all upvote them!
这篇关于positive_integer / 1谓词适用于大数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
