/* ipow.c - integer power function.
 * Jon Mayo - April 14, 2011 - PUBLIC DOMAIN
 *
 * Montgomery's Ladder Technique
 * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.4956&rep=rep1&type=pdf
 * HISTORY:
 * 2011-04-14 : creation
 */
#include <stdio.h>
#include <limits.h>

static unsigned long long ipow(unsigned g, unsigned k)
{
	unsigned long long r0, r1;
	unsigned j;
	r0 = 1;
	r1 = g;
	/* you can also set j to the position of the top most 1 bit */
	j = sizeof(k) * CHAR_BIT;
	while (j--) {
		/*
		fprintf(stderr, "\t[%d] r0 = %llu; r1 = %llu\n", j, r0, r1);
		*/
		if ((k >> j) & 1) {
			r0 = r0 * r1;
			r1 = r1 * r1;
		} else {
			r1 = r0 * r1;
			r0 = r0 * r0;
		}
	}
	return r0;
}

static void ipow_test(unsigned g, unsigned k)
{
	unsigned long long r;
	r = ipow(g, k);
	fprintf(stdout, "%u^%u = %llu\n", g, k, r);
}

int main()
{
	ipow_test(3, 30);
	ipow_test(64, 7);
	ipow_test(11, 5);
	return 0;
}