/* 
 * TEST program to test root(a).
 * cc a.c -O3 -Wall -S
 *
 * Fold the root checking for 3, 5, 7 into a single loop
 * and exploit the concepts 3**n < 5**n < 7**n, and odd**n is odd.
 * And also odd power can not be even.
 * So number of multiplications will become less.
 */

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>

static inline int test_root(int a, int b)
{
	int num = b;

	while(a > num)
		num *= b;

	return (num == a);
}

/* loop algorithm folded, shortcut 3*logn multiplications.  */
static inline int test_root2(int a)
{
	int num3 = 3, num5 = 5, num7 = 7;

	if  (num5 == a || num7 == a)
		return 1;

	if  (!(a & 1))
		return 0;

	while (a > num3) {
		num3 *= 3;

		if (a < num5)
			continue;
		num5 *= 5;
		if (num5 == a)
			return 1;

		if (a < num7)
			continue;
		num7 *= 7;
		if (num7 == a)
			return 1;
	}
	return (num3 == a);
}

/* 6*loglogn multiplications */
int test_root3(int a, int b)
{
	int factor, power = 1, guess = b;

	while (a >= guess)  {
		for (factor = b; a >= guess; factor *= factor) {
			power = guess;
			guess = guess * factor;
		}
		guess = power * b;
	}

	return (power == a);
}

int main(int argc, char *argv[])
{
	int a, b, d, ret = 0;

	if (argc < 3) {
		printf("Usage: %s num1 method\n", argv[0]);
		return 1;
	}
	a = atoi(argv[2]);  b = atoi(argv[1]);
	if (a != 1 && a != 2) {
		printf("%s: Method is one of the 1, 2 or 3.\n", argv[0]);
		return 1;
	}

	for (d = 1; d <10000000; d++) {
		switch(a) {
		case 1:
			ret = test_root(b, 3)
				|| test_root(b, 5)
				|| test_root(b, 7);
			break;
		case 2:
			ret = test_root2(b);
			break;
		}
	}

	switch(a) {
	case 1:
		printf("\nunfolded Alg:");
		break;
	case 2:
		printf("\nfolded   Alg:");
		break;
	}
	printf("%u is %s sparse\n", b, ret?"":"not");
	return 0;
}