Prolog, check if term is power of 2

Question

i have written following code, which should work with my logic, but it does not.

I should check if given term is power of two. For example s(s(s(nul))) should return false, s(s(s(s(nul))) should return true.

substractWhileY(X,0,rezult).
substractWhileY(s(X),Y,rezult):-
   Y > 0, number is 1,  substractWhileY(X,Y - number, rezult).

degreeOftwo(X):-
   substractWhileY(X,2,rezult),
   pagalba(X, 2, rezult).
calculateAnswer(X, currentCounter, currentValue):-
   currentCounter is currentCounter * 2,
   substractWhileY(currentValue, currentCounter , rezult),
   rezult\= null,
   calculateAnswer(X, currentCounter , rezult).

My idea was to check if given therm is degree of any two and if it is not than it is not the degree of two.

With numbers it should work like this. For example i give number 8.

First time it checks if 8 - 2 = 0.
second time if 8 - 4 = 0.
third time if 8 - 8 = 0.

so the 8 id power of two.

Maybe other solution would work better, so thanks for any help.

yes, it is these numbers that you have written down. I don't know how to call it correctly in English — kuldarim, Oct 30 '13 at 07:48
So what is the formula for it? 2^n sort of makes sense, but 2^0 is 1, not 0.... — , Oct 30 '13 at 08:29
@Riku, that would be a "power of 2". And by "therm" you probably mean "term". :) — lurker, Oct 30 '13 at 10:07
possible duplicate of [Prolog predicate - infinite loop](http://stackoverflow.com/questions/9740271/prolog-predicate-infinite-loop) — false, Oct 30 '13 at 15:47

score 2 · Accepted Answer · 2013-10-30T15:50:49.110

2

Assuming that you are looking for numbers 1, 2, 4, 8..., or in other words, 2^0, 2^1, 2^2, 2^3, ..., then a solution that is deterministic could be:

two_power_n(s(X)) :-
    two_power_n_minus_one(X). 

two_power_n_minus_one(0).
two_power_n_minus_one(s(X)) :-
    half(s(s(X)), s(Y)),
    two_power_n_minus_one(Y).

half(0, 0).
half(s(s(X)), s(Y)) :-
    half(X, Y).

I don't think this solution is optimal.

edited Oct 30 '13 at 15:50

answered Oct 30 '13 at 09:52

@Riku So the names are not obvious enough? What is it that you don't understand, in particular, so that I can explain it better? – Oct 30 '13 at 12:00
1

The common convention for zero in successor arithmetics is `0` not `nul`. Apart from that, is there a reason not to use `sum/3` or `add/3`? – false Oct 30 '13 at 15:43
@false I guess there is absolutely no reason not to use `sum/3` or `add/3`, apart from me not knowing that they exist. How will the solution look with `sum/3` and `add/3`? – Oct 30 '13 at 15:50
Maybe i don't understand something, but passing anything to `two_power_n()` always returns false for me. – kuldarim Oct 30 '13 at 17:07
@Boris: is does make a lot of sense to use `sum/3` because this illustrates how a single predicate can serve multiple purposes whereas `half` suggest a very moded reading. – false Oct 30 '13 at 18:30
@Riku it works with s(0) instead of s(nul). Just replace 0 with nul in the definition or nul with 0 in the query. – Oct 30 '13 at 18:32

Nicholas Carey · Answer 2 · 2013-10-30T21:25:37.423

Figuring out if a fixed-point, twos-complement integer is a power of two is easy, utilizing a property of the twos-complement representation used for signed integers in computers:

pow2( X ) :-     % X is a power of 2, if...
  X > 0 ,        % - X is > 0 , and ...
  X is X /\ (-X) % - A bitwise AND of X and its 2s complement yields X
  .              % Easy!

No recursion necessary, just bit-twiddling.

Given that, the solution is easy. Just traverse the nested structure s/1 and compute its depth/length. Then determine whether that is a power of 2 or not.

IsPowerOf2( S ) :- nested_depth(S,0,D) , pow2(D) .

nested_depth( nul  , D , D ).
nested_depth( s(X) , T , D ) :-
  T1 is T+1 ,
  nested_depth(X)
  .

score 0 · Answer 3 · answered Oct 30 '13 at 15:29

0

Boris' answer is surely more complete/correct (+1), and I predate his half/2 predicate. But the solution to your question appears simpler in this way:

pow_of_two(s(nul)).
pow_of_two(X) :-
    half(X, H),
    pow_of_two(H).

answered Oct 30 '13 at 15:29

CapelliC

59,646
5
47
90

It will go into an endless loop with `pow_of_two(nul)` (the way I have defined it at the moment, but this can be fixed). And the only reason why I have the extra predicate is that this solution is non-deterministic. – Oct 30 '13 at 15:39

Prolog, check if term is power of 2

3 Answers3