// file:    rp.rex
// author:  Robert Keller
// purpose: Raising a number to a power using the Russian Peasants method


// rp(M, N) raises M to the Nth power, where N is any natural number

rp(M, N) => rp(M, N, 1);


// rp(M, N, Acc) is the tail-recursive auxiliary function for rp above

rp(M, 0, Acc) => Acc;

rp(M, N, Acc) => N%2 == 1 ? rp(M*M, N/2, M*Acc);

rp(M, N, Acc) => rp(M*M, N/2, Acc);



// Test program

test() = myTest(7, 16384);


// myTest(Base, Hi) tests raising Base to successively doubling powers, up
// to Hi as the highest power.

myTest(Base, Hi) = show(testRange(Base, 1, Hi));


// testRange runs tests raising Base to Lo, followed by testRange on the
// next higher power of 2.

testRange(Base, Lo, Hi) => Lo > Hi? [];

testRange(Base, Lo, Hi) => [rp(Base, Lo) | testRange(Base, 2*Lo, Hi)];

		
// show formats the results one per line, with a blank line in between each.

show([]) => "\n";

show([A | L]) => concat(make_string(A), "\n", "\n", show(L));