Пролог: расчет OEIS A031877 ("нетривиальные числа разворота") с использованием clp(FD)

Question

Просматривая удивительную онлайн -энциклопедию целочисленных последовательностей (см. En.wikipedia.org), я наткнулся на следующую целочисленную последовательность:

A031877: Нетривиальные числа обращения (числа, которые являются целыми числами, кратными их обращениям), исключая палиндромные числа и числа, кратные 10.

Повторно используя некоторый код, который я написал для ответа на соответствующий вопрос " Более быстрая реализация словесной арифметики в прологе ", я мог без труда записать решение - благодаря 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 это конкретное целое число. Посмотрите сами для первых 100 значений N_digit!

?- 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% успешно, как и ожидалось; ложный.? - a031877_ndigits_ (87912000000 9 87912,17, _).
ложный.                                % терпит неудачу, как и ожидалось

Далее, давайте найдем несколько нетривиальных чисел, состоящих ровно из четырех десятичных цифр:

?- 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)? Или разные методы согласованности / распространения? А точнее пролог в стиле сопроводения?

Есть идеи? Я хочу их всех! Заранее спасибо.

Answer 1

Пока... нет ответов:(

Я придумал следующее...

Как насчет использования различных переменных для labeling/2?

a031877_ndigitsNEW_ (Z_big, N_digits, / * [K, Z_small, Z_big] * /
                                      [K | D_big]): -
   K #> 1,
   Длина (D_big,N_digits),
   обратное (D_small,D_big),
   digits_number(D_big,Z_big),
   digits_number(D_small,Z_small),
   Z_big #= Z_small * K.

Давайте измерим время выполнения!

?- 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.

Конечно, есть еще много возможностей для совершенствования! Должно быть...

Answer 2

Мы можем добиться большего, переведя теоретико-числовые свойства на язык ограничений!

Все термины имеют вид 87...12 = 4*21...78 или 98...01 = 9*10...89.

Мы реализуем a031877_ndigitsNEWER_/3 основанный на a031877_ndigitsNEW_/3 и непосредственно добавьте указанное выше свойство как два ограничения конечной области:

a031877_ndigitsNEWER_ (Z_big, N_digits, [K | D_big]): -
   К в {4} \ / {9},% (новый)
   Длина (D_big, N_digits),
   D_big ins (0..2) \ / (7..9),% (новый)
   обратное (D_small,D_big),
   digits_number(D_big,Z_big),
   digits_number(D_small,Z_small),
   Z_big #= Z_small * K.

Давайте снова проведем тесты, которые мы использовали раньше!

?- time((a031877_ndigitsNEWER_(Z,5,Zs),labeling([ff],Zs),false)).
% 73,011 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 11602554 Lips)
false.

?- time((a031877_ndigitsNEWER_(Z,6,Zs),labeling([ff],Zs),false)).
% 179,424 inferences, 0.028 CPU in 0.028 seconds (100% CPU, 6399871 Lips)
false.

?- time((a031877_ndigitsNEWER_(Z,7,Zs),labeling([ff],Zs),false)).
% 348,525 inferences, 0.037 CPU in 0.037 seconds (100% CPU, 9490920 Lips)
false.

Резюме: по трем запросам мы постоянно наблюдали значительное сокращение требуемого поиска. Просто подумайте, насколько уменьшился логический вывод: 1.45M -> 73k, 5M -> 179k, 15.1M -> 348k.

Можем ли мы сделать еще лучше (при сохранении декларативности кода)? Я не знаю, я так думаю...