Geek Answers Handbook

Prolog: OEIS calculation A031877 ("nontrivial reversal numbers") using clp (FD)

Looking through the awesome On-Line Encyclopedia of Integer Sequences (see en.wikipedia.org ), I came across the following whole sequence:

A031877 : Non-trivial spread numbers (numbers that are integer multiples of their spreads), excluding the palindrome of numbers and multiples of 10.

Reusing some code, I wrote for my answer to the corresponding question “ Faster implementation of verbal arithmetic in Prolog ” I could write down the solution quite easily - thanks to clpfd !

:- use_module(library(clpfd)).

Define the main ratio a031877_ndigits_/3 based on digits_number/2 (previously defined):

 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.

The main relation is deterministic and ends universally with N_digit - a specific integer. See for yourself for the first 100 N_digit values!

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

Run some queries!

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

 ? - a031877_ndigits_ (87912000000 9 87912.17, _).
 false  % fails, as expected

Next, we find some non-trivial reversal numbers containing exactly four decimal places:

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

OK! Let the runtime necessary to confirm the universal completion of the above request be measured!

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

Now, this way too long!

What can I do to speed up the process? Use different and / or other restrictions? Maybe even redundant? Or perhaps identify and eliminate symmetries that reduce the size of the search space? What about the different clp (*) domains (b, q, r, set)? Or different consistency / spread methods? Or rather, the Prologue companion style?

Any ideas? I want them all! Thanks in advance.

+5
source share
2 answers

So far ... no answers: (

I came up with the following ...

How to use different variables for labeling/2 ?

  a031877_ndigits NEW _ (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 some work time be measured!

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

It is better! But can we go further?

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

There is still plenty of room for improvement! It must be ...

+1
source

We can do better by translating number-theoretic properties into a language of constraints!

All members have the form 87 ... 12 = 4 * 21 ... 78 or 98 ... 01 = 9 * 10 ... 89.

We implement a031877_ndigitsNEWER_/3 based on a031877_ndigitsNEW_/3 and directly add the property above as two restrictions of the final domain:

  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.

Re-run the tests we used before!

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

Summary. For the three queries, we have consistently observed a significant reduction in the required search. Just consider how the number of conclusions is reduced: 1.45M → 73k, 5M → 179k, 15.1M → 348k.

Can we do even better (while preserving the declarative code)? I don’t know, I think so ...

+1
source

More articles:


All Articles