Inverse factorial in Prolog

Question

Can someone helping me to find a way to get the inverse factorial in Prolog...

For example inverse_factorial(6,X) ===> X = 3.

I have been working on it a lot of time.

I currently have the factorial, but i have to make it reversible. Please help me.

Optics

I've added the example. – Spice

Answer 1

Prolog's predicates are relations, so once you have defined factorial, you have implicitly defined the inverse too. However, regular arithmetics is moded in Prolog, that is, the entire expression in (is)/2 or (>)/2 has to be known at runtime, and if it is not, an error occurs. Constraints overcome this shortcoming:

:- use_module(library(clpfd)).

n_factorial(0, 1).
n_factorial(N, F) :-
   N #> 0, N1 #= N - 1, F #= N * F1,
   n_factorial(N1, F1).

This definition now works in both directions.

?- n_factorial(N,6).
   N = 3
;  false.
?- n_factorial(3,F).
   F = 6
;  false.

Since SICStus 4.3.4 and SWI 7.1.25 also the following terminates:

?- n_factorial(N,N).
   N = 1
;  N = 2
;  false.

See the manual for more.

Principal

@false. With clpfd in SWI, the query does terminate. How come? – Feigned

@false. I copy that, but with ?- n_factorial(N,N). I get N = 1 ; N = 2 ; false. As a matter of fact, I did get non-termination with some other variant of n_fac I coded elsewhere when running the query ?- n_fac(N,N), false. ... but here? No. – Feigned

@false. Good to know! Of course, I didn't doubt that your observation was valid when you made it. I simply couldn't reproduce it. So thank you for the extra effort of investigating several versions. – Feigned

This definition works in both directions, and is the most natural and readable way to implement it, but it is extremely slow when searching for the inverse factorial, e.g. n_factorial(Y, 1000000000) takes about 20 seconds to answer false on my machine. – Guesswarp

@Fatalize: Agreed! There are many ways to improve CLP(FD) programs! The point is just: Should we start from a broken incorrect definition or from a declarative but slow one? – Principal

n_factorial(N,N). should terminate in SICStus Prolog 4.3.4 that was released yesterday. – Heartsick

Thanks false, very informative. Could you provide or point me to a non-clpfd version using successor arithmetics? I can open a separate question if necessary. – Barabarabarabas

Separate question here. – Barabarabarabas

Answer 2

For reference, here is the best implementation of a declarative factorial predicate I could come up with.

Two main points are different from @false's answer:

• It uses an accumulator argument, and recursive calls increment the factor we multiply the factorial with, instead of a standard recursive implementation where the base case is 0. This makes the predicate much faster when the factorial is known and the initial number is not.

• It uses if_/3 and (=)/3 extensively, from module reif, to get rid of unnecessary choice points when possible. It also uses (#>)/3 and the reified (===)/6 which is a variation of (=)/3 for cases where we have two couples that can be used for the if -> then part of if_.

factorial/2

factorial(N, F) :-
    factorial(N, 0, 1, F).

factorial(N, I, N0, F) :-
    F #> 0,
    N #>= 0,
    I #>= 0,
    I #=< N,
    N0 #> 0,
    N0 #=< F,
    if_(I #> 2,
        (   F #> N,
            if_(===(N, I, N0, F, T1),
                if_(T1 = true,
                    N0 = F,
                    N = I
                ),
                (   J #= I + 1,
                    N1 #= N0*J,
                    factorial(N, J, N1, F)
                )
            )
        ),
        if_(N = I,
            N0 = F,
            (   J #= I + 1,
                N1 #= N0*J,
                factorial(N, J, N1, F)
            )
        )
    ).

(#>)/3

#>(X, Y, T) :-
    zcompare(C, X, Y),
    greater_true(C, T).

greater_true(>, true).
greater_true(<, false).
greater_true(=, false).

(===)/6

===(X1, Y1, X2, Y2, T1, T) :-
    (   T1 == true -> =(X1, Y1, T)
    ;   T1 == false -> =(X2, Y2, T)    
    ;   X1 == Y1 -> T1 = true, T = true
    ;   X1 \= Y1 -> T1 = true, T = false
    ;   X2 == Y2 -> T1 = false, T = true
    ;   X2 \= Y2 -> T1 = false, T = false
    ;   T1 = true, T = true, X1 = Y1
    ;   T1 = true, T = false, dif(X1, Y1)
    ).

Some queries

?- factorial(N, N).
N = 1 ;
N = 2 ;
false.          % One could probably get rid of the choice point at the cost of readability


?- factorial(N, 1).
N = 0 ;
N = 1 ;
false.          % Same


?- factorial(10, N).
N = 3628800.    % No choice point


?- time(factorial(N, 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000)).
% 79,283 inferences, 0.031 CPU in 0.027 seconds (116% CPU, 2541106 Lips)
N = 100.        % No choice point


?- time(factorial(N, 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518284253697920827223758251185210916864000000000000000000000000)).
% 78,907 inferences, 0.031 CPU in 0.025 seconds (125% CPU, 2529054 Lips)
false.


?- F #> 10^100, factorial(N, F).
F = 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000,
N = 70 ;
F = 850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000,
N = 71 ;
F = 61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000,
N = 72 ;
...

Guesswarp

So far, you find the optimization for "simple iterative variables" (in lack of a better name) on SO only for simpler cases like list_length/2. I wonder if this somehow could be automated! – Principal

@Principal What do you mean by "the mixing of arithmetic and syntactic equality"? No I do not know about (#)/1. – Guesswarp

While X= 1+0, X#=1 succeeds, X#=1, X= 1+0 fails. It seems that you have managed to eliminate all such related problems which is surprising indeed. At least the definition I gave had this flaw: N = 1+1, n_factorial(N,2). succeeds, but n_factorial(N,2),N = 1+1. fails. There is a functor # /1 to overcome this: #(X)#=1, X=0+1 fails while X=0+1, #(X)#=1 is an error. See the manual of clpfd/clpz. This is still somehow tentative, ideally # would be a prefix operator of very low priority, one could then write: #X + #Y #= #Z – Principal

@Principal When N is ground and F is free, or when both are free, then it's ok to use (=)/3and do N0 = F in the then part. But when F is ground and N is not, then using (=)/3 on N will leave a choice point that is not necessary (the last part of (=)/3 with dif) that we wouldn't get if F = N0 was the if part. So (===)/6 allows to fuse both cases, while still having the correct behavior if both N and F are free. Adding the = and dif parts for X2, Y2 is not needed and would actually create redundant results. – Guesswarp

All in all this is a if_ = or = situation, that is not completely symmetric (the first = being also the situation where both sides are free). The name === is not very descriptive I agree, I would have called it =;= but this isn't possible. – Guesswarp

X1=2,===(X1,3,1,1,false,true) fails, yet ===(X1,3,1,1,false,true), X1=2. succeeds. Therefore, === /6 is not a relation. – Principal

Maybe you need when((?=(X1,X2) ; ?=(Y1,Y2)), ... ) – Principal

@Principal Correct. This can be fixed by adding additional cases for T1 == true and T1 == false because in that case we fall back to the implementation of (=)/3. Since I didn't think of a situation where we would call (===)/6 with T1 ground, I didn't implement it. – Guesswarp

You need to produce declarative building blocks. Otherwise you are by no means better than purely procedural solutions. – Principal

@Principal Ideally (===)/6 shouldn't even exist and a modified version of if_/3 would be used in that case, so that we don't have to use that if_/3 in the then part. – Guesswarp

I assume you mean (;)/3 not if_/3. But the general problem is even more fundamental than that – Principal

Don't you want to purify your solution? The cheapest way is by using instantiation errors! – Principal

@Principal I have improved (===)/6 implementation to fix the type of problem you mentioned. – Guesswarp

X1 = 1, ===(X1,3,1,1,T,true),T=false. fails, yet ===(X1,3,1,1,T,true),T=false, X1=1. succeeds. Non-relational. – Principal

@Principal This is because (===)/6 is supposed to be followed by a if_(T1 = true, X2 = Y2, X1 = Y1), in which case it fails correctly in both cases. As I said before, ideally (===)/6 shouldn't exist and an extension of if_/3 should be proposed to directly include that second part, which is not in (===)/6. Something like ifeq_or_ifeq(X1, Y1, X2, Y2, (then) X2 = Y2, (or then) X1 = Y1, (else)). – Guesswarp

You can catch things also with an uninstantiation_error if you like. But your assumptions are easily broken. The point of if_/3 is that it provides a 100% pure building block and not one that only works in highly specific situations. – Principal

Impressive indeed! – Feigned

Answer 3

a simple 'low tech' way: enumerate integers until

• you find the sought factorial, then 'get back' the number
• the factorial being built is greater than the target. Then you can fail...

Practically, you can just add 2 arguments to your existing factorial implementation, the target and the found inverse.

Rah

what you think about my solution? – Spice

@SergeiLodyagin: will loop if XFact isn't a factorial. Add a test before the recursive call. – Rah

Answer 4

Just implement factorial(X, XFact) and then swap arguments

factorial(X, XFact) :- f(X, 1, 1, XFact).

f(N, N, F, F) :- !.
f(N, N0, F0, F) :- succ(N0, N1), F1 is F0 * N1, f(N, N1, F1, F).

Spice

this doesn't work for X=0, it does not calculate the factorial of number 0. this is because there's no sucessor of 1 being 0 so it runs out of memory. Any way to correct it being reversible ? – Presumptuous