:- module(_, [exp/3], [assertions, regtypes, nativeprops]).

:- entry exp(N, Exp, Res) : num * num * var.
:- pred exp(N, Exp, Res) : num * num * var.

exp(N, Exp, R) :-
%        write('Naively calculating '), write(N),
%        write('^'), write(Exp), write(' = '), flush_output,
        exponential_naive(N, Exp,R),
%        write(R), nl,
%        write('Divide-and-conquer calculating '), write(N),
%        write('^'), write(Exp), write(' = '), flush_output,
        exponential_div(N, Exp, Res),
%        write(Res), nl,
	R = Res,
	true.

:- pred exponential_div(B, E, R) : num * num * var => num * num * num.
%% exponential(Base, Exp, Res): Be smart and split Exp in halves
exponential_div(_Base, 0, 1) :- !.
exponential_div(Base, Exp, Res):-
        Exp > 0,
        HalfExp is Exp // 2,
        exponential_div(Base, HalfExp, HalfRes),
        exponential_div_2(Base, Exp, HalfRes, Res).

exponential_div_2(_, Exp, HalfRes, Res) :-
        ExpMod2 is Exp mod 2,
        ExpMod2 =:= 0, !,
        Res is HalfRes*HalfRes.
exponential_div_2(Base, _, HalfRes, Res) :-
        Res is HalfRes*HalfRes*Base.

:- pred exponential_naive(B, E, R) : num * num * var => num * num * num.
exponential_naive(_Base, 0, 1) :- !.
exponential_naive(Base, Exp, Res):-
        Exp > 0,
        NewExp is Exp - 1,
        exponential_naive(Base, NewExp, PartRes),
        Res is PartRes * Base.
