CODEWITHSUNDEEP
prologclpfdinstantiation-error
user3389669
user3389669

Reputation: 809

Prolog: Predicate that tells if given integer is a power of two and is usable as a generator

I would like to have a predicate isPowTwo/1 which holds for every power of two. Here is my approach:

isPowTwo(N) :- N > 0, N is N /\ (-N).

It works good, if I give integers to it:

?- isPowTwo(2).
true.

?- isPowTwo(4).
true.

?- isPowTwo(6).
false.

But it does not work when I want it to use as a generator:

?- isPowTwo(N).
ERROR: >/2: Arguments are not sufficiently instantiated

How can I write a predicate that generates powers of two, in ascending order?

Edit: It is important to use normal integers and not Peano numbers.

Upvotes: 2

Views: 294

Answers (2)

user3389669
user3389669

Reputation: 809

I have found another approach which works good as generator (faster than the CLP(FD) version using length(_, N) as goal), does not use clpfd, but tends to end in an infinite-loop if used as verifier:

isPowTwo(1).
isPowTwo(N) :- isPowTwo(N1), N is N1 * 2.

See its behavior:

?- isPowTwo(N).
N = 1 ;
N = 2 ;
N = 4 ;
N = 8 ;
N = 16 ;
N = 32 ;
N = 64 ;
N = 128 ;
N = 256 ;
N = 512 ;
N = 1024 ;
...

?- isPowTwo(4).
true ;
... (infinite loop)

?- isPowTwo(3).
... (infinite loop)

Upvotes: 0

mat
mat

Reputation: 40768

Rule of thumb

Are you reasoning over integers? → Use your Prolog system's CLP(FD) constraints.

Example solution

power_of_two(N) :-
    N #> 0,
    N #= 2^_.

Sample queries and answers

Concrete integers

?- power_of_two(2).
true.

?- power_of_two(4).
true.

?- power_of_two(6).
false.

Most general query

?- power_of_two(N).
N in 1..sup,
2^_G844#=N.

Enumeration

?- power_of_two(N), length(_, N).
N = 1 ;
N = 2 ;
N = 4 ;
N = 8 ;
N = 16 ;
N = 32 ;
etc.

Conclusion

Normal integers, no Peano numbers, are used.

Constraints allow us to state the solution in a pure, general and concise way.

Upvotes: 2

Related Questions