Prolog: calcolo OEIS A031877 ("numeri inversione non banali") usando CLP (FD)

Question

navigazione attraverso il impressionanteOn-Line Encyclopedia of Integer Sequences (cfr en.wikipedia.org), sono incappato la seguente successione di interi:

A031877: numeri di inversione non banali (numeri che sono multipli interi di loro inversioni) esclusi numero palindromo e multipli di 10.

Grazie al riutilizzo del codice che ho scritto per la mia risposta in Oc e domanda correlata "Faster implementation of verbal arithmetic in Prolog" Potrei scrivere una soluzione senza alcuno sforzo, grazie a clpfd!

:- use_module(library(clpfd)). 

Definiamo la relazione nucleoa031877_ndigits_/3 basati su digits_number/2 (definito in precedenza):

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. 

Il rapporto nucleo è deterministico e termina universalmente ogniqualvolta N_digit è un numero intero cemento . Guarda tu stesso i primi 100 valori di 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 

Facciamo alcune domande!

 
?- a031877_ndigits_(87912000000087912,17,_). 
    true        % succeeds, as expected 
; false. 

?- a031877_ndigits_(87912000000987912,17,_). 
false.        % fails, as expected 

Avanti, troviamo alcuni numeri di inversione non banale che comprende esattamente quattro decimali-cifre:

?- a031877_ndigits_(Z,4,Zs), labeling([],Zs). 
    Z = 8712, Zs = [4,2178,8712] 
; Z = 9801, Zs = [9,1089,9801] 
; false. 

OK! Misuriamo il runtime necessario per dimostrare la chiusura universale della query precedente!

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

Ora, questo è così troppo lungo!

Cosa posso fare per velocizzare le cose? Utilizzare diversi e/o altri vincoli? Forse anche quelli ridondanti? O forse identificare ed eliminare le simmetrie che tagliano le dimensioni dello spazio di ricerca? Che dire dei diversi domini clp (*) (b, q, r, set)? O diverse tecniche di consistenza/propagazione? O piuttosto coroutining in stile Prolog?

Hai idee? Li voglio tutti! Grazie in anticipo.

Answer 1

finora ... nessuna risposta :(

mi si avvicinò con il seguente ...

ne dite di usare variabili differenti per 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. 

Misuriamo alcuni tempi di esecuzione!

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

Meglio! Ma possiamo andare oltre?

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

C'è ancora molto spazio per migliorare, di sicuro! Ci deve essere ...

Answer 2

Noi possiamo fare meglio traducendo le proprietà teoriche del numero nella lingua dei vincoli!

Tutti i termini sono nella forma 87 ... 12 = 4 * 21 ... 78 o 98 ... 01 = 9 * 10 ... 89.

Realizziamo a031877_ndigitsNEWER_/3 sulla base di a031877_ndigitsNEW_/3 e direttamente aggiungere sopra proprietà come due vincoli finiti dominio:

 
a031877_ndigitsNEWER_(Z_big,N_digits,[K|D_big]) :- 
    K in {4}\/{9},      % (new) 
    length(D_big,N_digits), 
    D_big ins (0..2)\/(7..9),    % (new) 
    reverse(D_small,D_big), 
    digits_number(D_big,Z_big), 
    digits_number(D_small,Z_small), 
    Z_big #= Z_small * K. 

Let eseguire nuovamente i parametri di riferimento che abbiamo usato prima d'ora!

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

Riepilogo: Per le tre query, abbiamo costantemente osservato una riduzione significativa della ricerca richiesta. Basta considerare quanto diminuisce il conteggio dell'inferenza: 1.45M -> 73k, 5M -> 179k, 15.1M -> 348k.

Possiamo fare ancora meglio (preservando la dichiaratività del codice)? Non lo so, immagino di sì ...