Prolog, check if term is power of 2

0
votes

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.

3
prologsuccessor-arithmetics
variables start with Uppercase ! – CapelliC
What do you mean a degree of 2? 0, 2, 4, 8, 16, ...? – user1812457
yes, it is these numbers that you have written down. I don't know how to call it correctly in English – kuldarim
So what is the formula for it? 2^n sort of makes sense, but 2^0 is 1, not 0.... – user1812457
@Riku, that would be a "power of 2". And by "therm" you probably mean "term". :) – lurker

3 Answers

2
votes

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.

2
votes

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)
  .
0
votes

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