浏览真棒 On-Line Encyclopedia of Integer Sequences (参见 en.wikipedia.org ),我偶然发现了以下整数序列:
A031877: Nontrivial reversal numbers (numbers which are integer multiples of their reversals), excluding palindromic numbers and multiples of 10.
通过重新使用我为回答相关问题“Faster implementation of verbal arithmetic in Prolog”而编写的一些代码,我可以
毫不费力地写下解决方案——感谢 clpfd !
:- use_module(library(clpfd)).
我们定义核心关系
a031877_ndigits_/3
基于digits_number/2
(之前定义):a031877_ndigits_(Z_big,N_digits,[K,Z_small,Z_big]) :-
K #> 1,
length(D_big,N_digits),
reverse(D_small,D_big),
digits_number(D_big,Z_big),
digits_number(D_small,Z_small),
Z_big #= Z_small * K.
核心关系是确定性的,并且在以下情况下普遍终止
N_digit
是一个具体的整数。亲自查看 N_digit
的前 100 个值!?- time((N in 0..99,indomain(N),a031877_ndigits_(Z,N,Zs),false)).
% 3,888,222 inferences, 0.563 CPU in 0.563 seconds (100% CPU, 6903708 Lips)
false
让我们运行一些查询!
?- a031877_ndigits_(87912000000087912,17,_). true % succeeds, as expected ; false. ?- a031877_ndigits_(87912000000987912,17,_). false. % fails, as expected
Next, let's find some non-trivial reversal numbers comprising exactly four decimal-digits:
?- a031877_ndigits_(Z,4,Zs), labeling([],Zs).
Z = 8712, Zs = [4,2178,8712]
; Z = 9801, Zs = [9,1089,9801]
; false.
好的!让我们测量证明上述查询的通用终止所需的运行时间!
?- time((a031877_ndigits_(Z,4,Zs),labeling([],Zs),false)).
% 11,611,502 inferences, 3.642 CPU in 3.641 seconds (100% CPU, 3188193 Lips)
false. % terminates universally
现在,就是这样 太长!
我可以做些什么来加快速度?使用不同的和/或其他约束?甚至可能是多余的?或者,也许可以识别并消除会削减搜索空间大小的对称性?不同的 clp(*) 域 (b,q,r,set) 怎么样?或者不同的一致性/传播技术?或者更确切地说是 Prolog 风格的协程?
有想法吗?我都想要!提前致谢。
最佳答案
到目前为止......没有答案:(
我想出了以下...
为 labeling/2
使用不同的变量如何? ?
a031877_ndigitsNEW_(Z_big,N_digits,/*[K,Z_small,Z_big]*/ [K|D_big]) :- K #> 1, length(D_big,N_digits), reverse(D_small,D_big), digits_number(D_big,Z_big), digits_number(D_small,Z_small), Z_big #= Z_small * K.
Let's measure some runtimes!
?- time((a031877_ndigits_(Z,4,Zs),labeling([ff],Zs),false)).
% 14,849,250 inferences, 4.545 CPU in 4.543 seconds (100% CPU, 3267070 Lips)
false.
?- time((a031877_ndigitsNEW_(Z,4,Zs),labeling([ff],Zs),false)).
% 464,917 inferences, 0.052 CPU in 0.052 seconds (100% CPU, 8962485 Lips)
false.
更好的! 但我们能走得更远吗?
?- time((a031877_ndigitsNEW_(Z,5,Zs),labeling([ff],Zs),false)).
% 1,455,670 inferences, 0.174 CPU in 0.174 seconds (100% CPU, 8347374 Lips)
false.
?- time((a031877_ndigitsNEW_(Z,6,Zs),labeling([ff],Zs),false)).
% 5,020,125 inferences, 0.614 CPU in 0.613 seconds (100% CPU, 8181572 Lips)
false.
?- time((a031877_ndigitsNEW_(Z,7,Zs),labeling([ff],Zs),false)).
% 15,169,630 inferences, 1.752 CPU in 1.751 seconds (100% CPU, 8657015 Lips)
false.
当然还有很多需要改进的地方!必须有...
关于performance - Prolog:使用 clp(FD) 计算 OEIS A031877 ("nontrivial reversal numbers"),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32608228/