/* author: Michael Codish
   date:    March 2003

 log2(X,Y) :- Y equals the integer log base 2 of X.

 Namely, the largest integer smaller or equal to the 
 log base 2 of X
*/

:- log2(o,i).

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


% log2(X,H,A,Y) :- computes Y equals the integer log base 2 of X.
% H accumulates "half" of X and A accumulates the number of times
% X was halved.

log2(s(s(X)),Half,Acc,Y) :- log2(X,s(Half),Acc,Y).

log2(X,s(s(Half)),Acc,Y) :- small(X), log2(Half,s(0),s(Acc),Y).

log2(X,Half,Y,Y) :- small(X),small(Half).

small(0). 
small(s(0)).


/*

    ?- log2(s(s(s(s(s(s(s(s(0)))))))), Y).
    Y = s(s(s(0)))

    ?- log2(s(s(s(s(s(s(s(s(s(s(0)))))))))), Y).
    Y = s(s(s(0)))

*/